数字信号处理课程设计利用循环卷积实现快速卷积运算.doc

燕山大学课 程 设 计 说 明 书题目： 利用循环卷积实现快速卷积运算 学院（系）：07级电气工程学院 年级专业： 工业自动化仪表 学 号： 学生姓名： 指导教师： 教师职称： 燕山大学课程设计（论文）任务书院（系）：电气工程学院 基层教学单位： 学 号学生姓名专业（班级）工业自动化仪表设计题目利用循环卷积实现快速卷积运算设计技术参数以四点和256点为例进行循环卷积和线性卷积运算设计要求 利用Matlab分别设计循环卷积和线性卷积程序，比较算法的计算速度；利用FFT-IFFT实现快速循环卷积卷积，并利用其实现现行卷积，计算系统输出。工作量工作计划1-2天：查资料。3-5天：进行设计编写程序。6-9天：运行、调试完成说明书。10天：答辩。参考资料1.信号处理原理及应用 机械工业出版社 谢平 林洪彬 王娜 2.数字信号处理基础及MATLAB实现 中国林业出版社 周辉 董正宏3. 指导教师签字 谢平 林洪彬基层教学单位主任签字谢平说明：此表一式四份，学生、指导教师、基层教学单位、系部各一份。2010 年 7 月 4 日 燕山大学课程设计评审意见表指导教师评语：成绩： 指导教师： 2010 年 7 月 16 日答辩小组评语： 成绩： 评阅人： 2010 年 7 月 16 日课程设计总成绩：答辩小组成员签字： 2010 年 7 月16 日摘 要信号处理技术已经几乎涉及到所有工程技术领域。信号处理的目的就是对被观测到的信号进行分析，变换，综合，估计和识别等，使之容易为人们所使用。数字信号处理可以用硬件和软件两种方法来实现。目前，数字信号处理的技术已日趋成熟，其应用领域几乎涵盖了所有领域。在信号处理技术中，无论时域还是频域都离不开卷积运算和傅立叶运算，本文主要介绍了利用循环卷积实现快速卷积运算的方法，并利用Matlab分别设计循环卷积和线性卷积程序，比较算法的计算速度，此外，由于快速傅里叶变换（FFT）算法可以使运算工作量大大减少,运算速度大大的提高，我们利用FFT-IFFT实现快速循环卷积卷积，并利用其实现线性卷积，来计算系统输出。目 录序 言 摘要 1第一章 概 述 3第二章 设计思想及系统功能 3一 设计思想3二 系统功能3第三章 离散时间信号卷积的实现 4一 线性卷积41 定义及计算步骤42 性质及作用5二 循环卷积6三 利用FFT计算循环卷积7四 利用FFT计算线性卷积7第四章 连续时间信号卷积的实现 8第五章 程序源代码及结果分析8一 四点循环卷积及线性卷积程序代码81 四点循环卷积的程序源代码82 用FFT计算四点循环卷积的程序源代码93 四点线性卷积的程序源代码 104 用FFT计算四点线性卷积的程序源代码11二 256点循环卷积及线性卷积程序代码121256点循环卷积的程序源代码122 用FFT计算256点循环卷积的程序源代码133256点线性卷积的程序源代码144 用FFT计算256点线性卷积的程序源代码15三 小节16第六章 总结 16第七章 参考文献17第一章 概述在数字信号处理(DSP)系统中,无论在时域或频域都离不开卷积运算和快速傅里叶(FFT)运算。其中，离散卷积在数字信号处理中是很重要的一种运算,因为离散时间系统的输出响应等于输入激励与系统单位冲激响应的离散卷积,所以离散卷积运算被广泛应用。然而，在离散时间信号处理过程中,线性卷积的运量大,运算速度慢,而时域圆周卷积在频域上等于两序列的DFT(离散傅里叶变换)相乘,由DFT可采用快速算法,计算速度要大大优于线性积。目前，快速卷积运算的研究方向大致有三个：一是应用多项式留数定理，将两个很长数列的卷积转化成求若干较短数列的卷积；第二是先将一维卷积多项式转化成多维多项式的乘积，再以一种有效的方式来计算此多维多项式乘积；最后是应用FFT的快速卷积运算。本文主要介绍了利用循环卷积实现快速卷积运算的方法，并利用Matlab分别设计循环卷积和线性卷积程序，比较算法的计算速度，此外，由于快速傅里叶变换（FFT）算法可以使运算工作量大大减少,运算速度大大的提高。我们利用FFT-IFFT实现快速循环卷积，并利用其实现线性卷积，计算系统输出。第二章 设计思想及系统功能一 设计思想1 描述线性非时不变连续时间系统的数学模型是线性常系数微分方程。为了确定一个线性非时不变系统在给定下的完全响应y(t)，就要对该系统列写微分方程表示式，并求出满足初始条件的解。 2 系统的全响应可分为零输入响应与零状态响应。零输入响应是激励为零时仅由系统初始状态所产生的响应，用rzi(t)表示；零状态响应是系统初始状态为零仅由激励所引起的响应，用rzs(t)表示。于是，可以把激励信号与初始状态两种不同因素引起的响应区分开来分别进行计算，然后再叠加，即 r(t)= rzi(t) + rzs(t)3 卷积不仅作为一种数学运算方式，它还反映了求解系统响应的物理过程。4 卷积的图解法 a、 自变量t换成 ；b、反褶；c、平移；d、相乘； e、积分。5 卷积的性质：a、交换律; b、分配律;c、结合律;d、时移;e、卷积的微分与积分;f、与的卷积二 系统功能利用循环卷积实现快速卷积运算的方法，并利用Matlab分别设计循环卷积和线性卷积程序，比较算法的计算速度，此外，由于快速傅里叶变换（FFT）算法可以使运算工作量大大减少,运算速度大大的提高。我们利用FFT-IFFT实现快速循环卷积，并利用其实现线性卷积，计算系统输出。第三章 离散时间信号卷积的实现在科学技术飞速发展的今天，现代通信技术正在蓬勃发展，如何快速、准确、方便、易行地进行远距离信息传递，这是我们人类追求的目标。要实现这一目标必须进行离散信号卷积的计算。一 线性卷积1 定义及计算步骤设系统输入x（n）=，系统输出y（n）的初始状态为零，定义这种条件下系统输出称为系统的单位取样响应，用h（n）表示，换句话说，单位取样响应即是系统对于的零状态响应。用公式表示为 设系统的输入用表示，按照式(3.2.3)表示成单位采样序列移位加权和为 那么系统输出为根据线性系统的叠加性质又根据时不变性质式中的符号“*”代表卷积运算，由式可见，这类卷积运算中有翻转、位移、相乘和相加，因此称这类卷积为线性卷积，简称卷积。式表示线性时不变系统的输出等与输入序列和该系统的单位取样响应的卷积。只要知道系统的单位取样响应，由公式可知，对于任意输入x（n）都可以求出系统的输出。计算离散信号卷积时，最常见的方法是图解法，通过对信号h（n）的翻转、平移、乘积、取和等步骤完成计算。下面介绍图解法计算线性卷积的具体步骤：首先应该将x（n）和h（n）中的变量n用变量m 替换，得到x（m）和h（m）。依据离散信号卷积运算过程（包括翻转，平移，乘积及取和），然后根据信号h(m)的图形作其翻转信号h(-m)的图形和平移信号h(n-m)的图形，当n>0时，序列右移；当n<0时，序列左移。然后将x（m）和h（n-m）相同m的序列值对应相乘后，再相加。按照以上三个步骤可以得到卷积结果y(n)。为计算所有的y（n），必须对所有的n，重复上述步骤。2 性质及作用 线性时不变系统的线性卷积服从交换律、结合律和分配律。它们分别用公式表示如下： (3.3.3) (3.3.4) (3.3.5)设和分别是两个系统的单位取样响应，表示输入序列。按照式(3.3.4)的右端，信号通过系统后再通过系统，等效于按照式(3.3.4)左端，信号通过一个系统，该系统的单位取样响应为，如图3.3.2(a)、(b)所示。该式还表明两系统级联，其等效系统的单位取样响应等于两系统分别的单位取样响应的卷积。按照式(3.3.5)，信号同时通过两个系统后相加，等效于信号通过一个系统，该系统的单位取样响应等于两个系统分别的单位取样响应之和，如图3.3.2(c)和(d)所示。换句话说，系统并联的等效系统的单位取样响应，等于两个系统分别的单位取样响应之和。(a)(b)(c)(d)图3.3.2 卷积的结合律和分配律再考查式(3.2.3)，它也是一个线性卷积公式，它表示序列本身与单位取样序列的线性卷积等于序列本身，表示如下： (3.3.6)对于延时的离散时间时移系统，当输入为时，输出为，即 (3.3.7)进一步，如果两个离散时间时移系统级联，其中一个系统延时，另一个系统延时，则系统总的延时为，即 (3.3.8)若，则有 (3.3.9)二 循环卷积两序列离散傅里叶变换的乘积等于此两序列的循环卷积的离散傅里叶变换，即x1（n）和x2（n）满足式的条件，且，N>=maxN1,N2，则 一般称此式所表示的运算为x1(n)和x2(n)的循环卷积，还可记为 线性卷积是求离散系统响应的主要方法之一，许多重要应用都建立在这一理论基础上，如卷积滤波等。循环卷积，又称圆周卷积，它的计算速度要远远快于线性卷积，如果选择圆周卷积的长度LN1+N2-1，则可以用圆周卷积取代线性卷积。方法如下：(1)定义圆周卷积的长度：选择L=N1+N2-1。(2)将两个序列的长度都补足为L：将长为N1的序列x（n）延长到L，补LN1个零，将长为N2的序列h（n）)延长到L，补LN2个零。(3)反转x（n），周期延拓为序列，取主周期。(4)循环移位：与线性卷积不同，圆周卷积运算中采用的是循环移位，有限长序列x（n）的循环移位定义为： 其含义如下：表示x（n）的周期延拓序列的移位：表示对移位的周期序列取主值序列，所以，f（n）仍然是一个长度为N的有限长序列。(5)将序列z与h进行循环移位生成的矩阵H的转置矩阵相乘，即完成将z(m)和h(nm)所有对应项相乘之后相加，完成圆周卷积。三 利用FFT计算循环卷积由DFT的循环卷积定理可知，若 则由时域循环定理有由此可见，循环卷积既可以在时域直接计算，也可以转换到频域计算。当N很大时，在频域的计算速度要比时域快得多，因而常用FFT计算循环卷积。四 利用FFT计算线性卷积FFT计算线性卷积的方法如下：(1)定义长度：选择N=N1+N2-1。(2)求两个要卷积序列的N点频谱函数：求X(k)=FFTx(n) 求H(k)=FFTh(n)(3)将两个频谱函数相乘：求Y（k)=H(k)X(k)(4)对乘积进行N点快速傅里叶反变换(IFFT)：求y(n)=IFFTY(k)可见，只要进行二次FFT，一次IFFT就可完成线性卷积计算。在x（n），h（n）两序列长度比较接近或相等的情况，当运算的序列长度N>32时，上述计算线性卷积的方法比直接计算线性卷积有明显的优越性，长度值越大优势越明显。其流程图如下：IFFTFFTFFT第四章 连续时间信号卷积的实现计算机高度发展的今天, 将MALAB 软件用于“信号与系统”课程, 是该课程未来发展的一种必然趋势, 两个离散时间信号相卷积, 可直接利用MA TLAB M 文件中的conv 函数; 两个连续时间信号相卷积若采用数值解, 首先要对连续时间信号采样得到离散信号f 1 和f 2, 再用conv (f 1, f 2) 进行卷积运算得到离散时刻上的卷积结果, 最后将这些离散时刻上的结果相连(插值) 来近似连续函数的卷积结果。其具体步骤如下：1 将两个连续时间信号f1(t)与f2(t)以时间间隔进行抽样,得到离散序列和;2 构造与和相对应的时间向量k1和k2;3 调用conv( )函数计算卷积积分f(t)的近似向量4 构造对应的时间向量k.此处不做详细分析。第五章 程序源代码及结果分析一 四点循环卷积及线性卷积程序代码1 四点循环卷积的程序源代码x1=1,2,3,4;x2=5,6,7,8;subplot(2,2,1);stem(x1);title('序列x1');subplot(2,2,2);stem(x2);title('序列x2');t0 = clock;N=max(length(x1),length(x2);x1=x1 zeros(1,N-length(x1); %若长度不够补零x2=x2 zeros(1,N-length(x2); %若长度不够补零m=0:1:N-1;x2=x2(mod(-m,N)+1);H=zeros(N,N);for n=1:1:N H(n,:)=cirshift(x2,n-1,N); endy=x1*H'c=etime(clock,t0)subplot(2,2,3);stem(y);title('循环卷积结果序列y'); 为此定义一个位移函数cirshiftd.m如下:function y=cirshift(x,m,N)x=x zeros(1,N-length(x);n=0:1:N-1;n=mod(n-m,N);y=x(n+1);运行时间及结果图像如下：c = 0.01002 用FFT计算四点循环卷积的程序源代码x1=1,2,3,4;x2=5,6,7,8;subplot(3,2,1);stem(x1);title('序列x1');subplot(3,2,2);stem(x2);title('序列x2');t0 = clock;N=max(length(x1),length(x2);X1=fft(x1,N);X2=fft(x2,N); subplot(3,2,3);stem(X1);title('序列X1');subplot(3,2,4);stem(X2);title('序列X2');Y=X1.*X2;Y=ifft(Y);c=etime(clock,t0)subplot(3,2,5);stem(Y);title('快速循环卷积结果序列Y');运行时间及结果图像如下：c=0.08003 四点线性卷积的程序源代码A=1,2,3,4;B=5,6,7,8;subplot(2,2,1);stem(A);title('序列A');subplot(2,2,2);stem(B);title('序列B');t0 = clock;Lx=length(A)+length(B)-1; %线性卷积长度l1=length(A)-1;l2=length(B)-1;A=zeros(1,l2) A zeros(1,l2); %A序列前后补零B=fliplr(B); %反转BB=B,zeros(1,l1+l2); %B序列后面补零 与A长度相等for i=1:Lx %计算z(i) z(i)=A(1)*B(1); for k=2:length(B) z(i)=z(i)+A(k)*B(k); end t=B(length(B); %保存B序列最后一个数 for j=length(B):-1:2 %B序列依次向后移位 B(j)=B(j-1); end B(1)=t;end c=etime(clock,t0)subplot(2,2,3);stem(z);title('线性卷积结果序列z');运行时间及结果图像如下：c = 0.02004 用FFT计算四点线性卷积的程序源代码x1=1,2,3,4;x2=5,6,7,8;subplot(3,2,1);stem(x1);title('序列x1');subplot(3,2,2);stem(x1);title('序列x2');t0 = clock;L=length(x1)+length(x2)-1;X1=fft(x1,L);X2=fft(x2,L);subplot(3,2,3);stem(X1);title('序列X1');subplot(3,2,4);stem(X2);title('序列X2');Y=X1.*X2;Y=ifft(Y,L);c=etime(clock,t0)subplot(3,2,5);stem(Y);title('快速线性卷积结果序列Y');运行时间及结果图像如下：c = 0.1200二 256点循环卷积及线性卷积程序代码1256点循环卷积的程序源代码clear;x1=randn(1,256); x2= randn(1,256);subplot(2,2,1);stem(x1);title('序列x1');subplot(2,2,2);stem(x2);title('序列x2');t0 = clock;N=max(length(x1),length(x2);x1=x1 zeros(1,N-length(x1); %若长度不够补零x2=x2 zeros(1,N-length(x2); %若长度不够补零m=0:1:N-1;x2=x2(mod(-m,N)+1);H=zeros(N,N);for n=1:1:N H(n,:)=cirshift(x2,n-1,N); endy=x1*H'c=etime(clock,t0)subplot(2,2,3);stem(y);title('循环卷积结果序列y');运行时间及结果图像如下：c = 0.04002 用FFT计算256点循环卷积的程序源代码x1=randn(1,256); x2= randn(1,256);subplot(3,2,1);stem(x1);title('序列x1');subplot(3,2,2);stem(x2);title('序列x2');t0 = clock;N=max(length(x1),length(x2);X1=fft(x1,N);X2=fft(x2,N); subplot(3,2,3);stem(X1);title('序列X1');subplot(3,2,4);stem(X2);title('序列X2');Y=X1.*X2;Y=ifft(Y);c=etime(clock,t0)subplot(3,2,5);stem(Y);title('快速循环卷积结果序列Y');运行时间及结果图像如下：c =0.06003256点线性卷积的程序源代码clear;A=randn(1,256); B= randn(1,256);subplot(2,2,1);stem(A);title('序列A');subplot(2,2,2);stem(B);title('序列B');t0 = clock;Lx=length(A)+length(B)-1; %线性卷积长度l1=length(A)-1;l2=length(B)-1;A=zeros(1,l2) A zeros(1,l2); %A序列前后补零B=fliplr(B); %反转BB=B,zeros(1,l1+l2); %B序列后面补零 与A长度相等for i=1:Lx %计算z(i) z(i)=A(1)*B(1); for k=2:length(B) z(i)=z(i)+A(k)*B(k); end t=B(length(B); %保存B序列最后一个数 for j=length(B):-1:2 %B序列依次向后移位 B(j)=B(j-1); end B(1)=t;end c=etime(clock,t0)subplot(2,2,3);stem(z);title('线性卷积结果序列z');运行时间及结果图像如下：c =1.26004 用FFT计算256点线性卷积的程序源代码clear;x1=randn(1,256); x2= randn(1,256);subplot(3,2,1);stem(x1);title('序列x1');subplot(3,2,2);stem(x1);title('序列x2');t0 = clock;L=length(x1)+length(x2)-1;X1=fft(x1,L);X2=fft(x2,L);subplot(3,2,3);stem(X1);title('序列X1');subplot(3,2,4);stem(X2);title('序列X2');Y=X1.*X2;Y=ifft(Y,L);c=etime(clock,t0)subplot(3,2,5);stem(Y);title('快速线性卷积结果序列Y');运行时间及结果图像如下：c =0.1600三 小节表 卷积变化所需时间循环卷积快速循环卷积线性卷积快速线性卷积四点c = 0.0200c=0.0100c = 0.1200c = 0.0800256点c = 0.0400c =0.0600c =1.2600c =0.1600 由上面表格可知，在点数相对较少时，快速傅里叶变换并没有体现出其优越性，没有明显的比非快速傅里叶变换速度快。但当点数相对来说较大时，无论是在循环卷积还是线性卷积中，快速傅里叶变换明显具有一定的优越性，速度要比非快速傅里叶变换快。由此可知，FFT可以减少运算量，提高运行速度，为我们计算提高了效率，应用较广。第六章 总结数字信号处理技术是一门技术性很强的学科，知识面非常广。循环卷积和线性卷积则是其中的一个重要分支，有着极其重要的作用。通过本次课程设计，我们对数字信号处理应用方面有了很大程度的了解，并且掌握了部分设计中常用的基础知识。通过对循环卷积和线性卷积相关知识的初步学习，了解了一些关于利用循环卷积实现快速卷积运算的方法，并学会了基本的利用Matlab设计循环卷积和线性卷积程序的步骤。此外，了解了利用FFT-IFFT实现快速循环卷积卷积，并利用其实现线性卷积，来计算系统输出的一些方法。初次接触matlab软件，并对其一些基本编程方法有了初步了解。总之，这次课设通过查阅多方资料，动手设计程序及修改错误，与同学们的积极讨论，让我对数字信号处理这门课程也有了更加详细的认识，这比课堂上学的灵活深刻了不少，相信通过这次课设会对以后的学习和生活有很大的帮助。第七章 参考文献1. 信号处理原理及应用 机械工业出版社 谢平 林洪彬 王娜2. 数字信号处理基础及MATLAB实现 中国林业出版社 周辉 董正宏3. 信号、系统与信号处理的软硬件实现 电子工业出版社 吴湘淇 肖熙 郝晓丽4. 基于Matlab的离散卷积 现代电子技术2009年第5期 刘国良5. 卷积在连续时间系统中的应用及其Matlab实现 天中学刊2006年 庞建丽 高丽娜6. 基于计算机的信号处理实践 电子工业出版社 James H.McClellan7. MATLAB 6.x信号处理 清华大学出版社 邹鲲 袁俊泉8. MATLAB信号处理详解 人民邮电出版社 陈亚勇9. 信号与系统 电子工业出版社 吴新余 周井泉 沈元隆10. 数字信号处理原理与实践 清华大学出版社 周勇