序列的卷积与快速卷积运算的编程实现

.../课程设计任务书学生姓名：韩新颖专业班级：电信1203班指导教师：阙大顺王虹工作单位：信息工程学院题目:序列的卷积和快速卷积运算的编程实现初始条件：Matlab6.5以上版本软件；课程设计辅导资料："Matlab语言基础及使用入门"、"数字信号处理原理与实现"、"Matlab及在电子信息课程中的应用"等；先修课程：信号与系统、数字信号处理、Matlab应用实践及信号处理类课程等。要求完成的主要任务：〔包括课程设计工作量及其技术要求,以及说明书撰写等具体要求课程设计时间：1周〔课内实践；课程设计内容：序列的卷积和快速卷积运算的编程实现,具体包括：直接卷积及应用、快速卷积方法及实现、两者的比较分析等；本课程设计统一技术要求：研读辅导资料对应章节,对选定的设计题目进行理论分析,针对具体设计部分的原理分析、建模、必要的推导和可行性分析,画出程序设计框图,编写程序代码〔含注释,上机调试运行程序,记录实验结果〔含计算结果和图表,并对实验结果进行分析和总结；课程设计说明书按学校"课程设计工作规范"中的"统一书写格式"撰写,具体包括：目录；与设计题目相关的理论分析、归纳和总结；与设计内容相关的原理分析、建模、推导、可行性分析；程序设计框图、程序代码〔含注释、程序运行结果和图表、实验结果分析和总结；课程设计的心得体会〔至少500字；参考文献；其它必要内容等。指导教师签名：年月日系主任〔或责任教师签名：年月日摘要卷积在数字信号处理中有着重要的作用。然而直接计算卷积的运算量非常大,它与序列长度的平方成反比,因此制约了卷积的应用。快速卷积是实现卷积的一种快速算法,减少了运算量,节约了时间。通过分析我们可在MATLAB里编程实现。关键词：卷积；快速卷积；MATLAB。目录1、直接卷积及应用11.1卷积的定义11.2、卷积的运用12、快速卷积方法及实现22.1快速卷积运算原理22.2实现方法3重叠相加法3重叠保留法33、直接卷积和快速卷积的分析比较44、程序设计及仿真结果分析45、心得体会116、参考文献121、直接卷积及应用1.1卷积的定义设:f<x>,g<x>是R1上的两个可积函数,作积分：可以证明,关于几乎所有的实数x,上述积分是存在的。这样,随着x的不同取值,这个积分就定义了一个新函数h<x>,称为函数f与g的卷积,记为h<x>=<f*g><x>。1.2、卷积的运用卷积是数字信号处理中最常见,也是最重要的运算之一,利用卷积可以实现相关计算和FIR滤波等等,正因为卷积如此重要,所以半个世纪以来,学者们提出了多种不同卷积实现结构。设输入信号为x〔t,其频谱函数为X〔jΩ该信号通过滤波器h〔t后,其输出信号y〔t的频谱函数Y〔jΩ是频谱函数x〔jΩ与滤波器的频谱函数H〔jΩ的乘积,即：Y〔jΩ=X〔jΩH〔jΩ而在时域,输出信号y<t>实际是输入信号x<t>与滤波器h<t>的卷积,就是说频谱函数的乘积相当于时间函数的卷积,反之亦然,即：y<t>=x<t>*h<t>在数字信号处理系统中,无论在时域还是频域都离不开卷积运算和快速傅里叶运算,Matlab具有强大的矩阵运算能力。方便实用的绘图功能和语言的高度集成性。在DSP开发中,使用Matlab可以快速对系统进行仿真运算。2、快速卷积方法及实现2.1快速卷积运算原理在信号处理中,许多具体的应用是以线性卷积为基础的。当满足一定条件时,可以用圆周卷积来计算线性卷积。由圆周卷积定理知道,圆周卷积可以借助DFT来运算,因此DFT的快速算法FFT就可以用来计算线性卷积。设x1〔n与x2〔n分别是长度为N与M的有限长序列,它们的线性卷积为yl〔n,L点的圆周卷积为yc〔n,它们的关系为yc〔n=∑yl<n+rL>Rl<n>由上式可知圆周卷积是线性卷积以L为周期进行延拓后,再取主值序列的结果。当满足L>M+N-1时,周期延拓不发生混叠,就可以用圆周卷积来计算线性卷积。由圆周卷积定义可知,可以用FFT分别求出x1〔n与x2〔n的L点DFTX1〔k与X2〔k,即X1〔k=DFT[x1<n],X2〔k=DFT[x2<n>],再用IFFT计算X1<kX2<k>的L点IDFT得yc〔n,也就是x1〔n与x2〔n的线性卷积为yl<n>,即yl<n>=yc<n>=IDFT[X1<k>·X2〔k]下图为上述过程的示意图L点的FFTx1<n>L点的FFTL点的IFFTyc<n=yl<n>L点的IFFTL点的FFTx2<n>L点的FFT2.2实现方法在实际应用中,常遇到的问题是参加卷积的两个序列的长度相差较大,这样长度小的序列就需补很多的零点,这样就需要大的存储量,运算时间也会变长。常用的解决方法有两种,一是重叠相加法,另一种是重叠保留法。重叠相加法设序列x1〔n为无限长序列,序列x2〔n是长度为M的序列,由x1<n>构成长度为N的有限长序列x1k<n>=x1<n>,kN<n<<k+1>N-1=0其他〔式2.1因此x1k<n>=∑x1k<n>〔式2.2将式子代入卷积公式有Y<n>=x1<n>*x2<n>=x2<n>*∑x1k<n>=∑x1k<n>*x2<n>=∑yk<n>〔式2.3式中,yk<n>=x2<n>*xk<n>=∑x2<m>xk<n-m>〔式2.4式〔2.3表示,计算x1<n>与x2〔n的线性卷积y<n>时,可以先分段计算yk<n>,然后再叠加起来即可。因为yk<n>的长度为M+N-1,因此yk〔n的后N-1个值与yk+1<n>的前N-1个值重叠,因此必须把yk<n>的后N-1个值与yk+1〔n前的N-1个值相加,因为称为重叠相加法。重叠保留法为了克服重叠相加法中分段卷积后任然需要相加的缺点,人们提出了重叠保留法。与重叠相加法不同的是,在对无限长序列x1<n>的后M-1个抽样值与后一段xk+1<n>的前M-1个抽样值相同,且分段的长度选圆周卷积的长度L,这样形成的分段序列为然后计算x2〔n与各分段x1k<n>之间的卷积：Yk’=x2<n>*x1k<n>显然,yk’<n>的前M-1个值发生了混叠,不等于x2<n>与x1k<n>的线性卷积。把yk’<n>的前M-1个值舍去,保留yk’<n>没有发生混叠的后N个值,形成序列X1k=x<n+kN-M+1>,0<n<L-1=0其他最后输出序列y<n>=∑yk<n-kN+M-1>3、直接卷积和快速卷积的分析比较卷积是数字信号处理中最常见的,也是最重要的运算之一。利用卷积可以实现相关计算和FIR滤波等等,正因为卷积如此重要,所以半个世纪以来,学者们提出了多种不同卷积实现结构,这些结构各有优点,针对不同应用可以灵活选择,而其中快速卷积无疑是重要的卷积方法之一。顾名思义,快速卷积重点在一个"快",如果对卷积速度要求较高,快速卷积无疑是理想的工具。当然,为了提高速度,就要牺牲面积和功耗4、程序设计及仿真结果分析1、已知线性非移变系统的h<n>=[6,2,3,6,4,2],输入为x<n>=[1,2,3,4,5]；<1>用人工计算系统输出y<n>；<2>编写程序输出y<n>,并作图。人工计算：长度为m的向量序列h和长度为n的向量序列x,卷积w的向量序列长度为〔m+n-1,当不等于n时,应以0补齐阶次低的向量的高位后进行计算y<1>=h<1>*x<1>y<2>=h<1>*x<2>+h<2>*x<1>...y<n>=h<1>*x<n>+h<2>*x<n-1>+...+h<n>*x<1>...y<m+n-1>=h<1>*x<m+n-1>+h<2>*x<m+n-2>+...+h<m+n-1>*x<1>那么根据这个规律人工计算的结果为y<n>=[6,14,25,36,63,50,55,52,28,10]用matlab仿真编程程序如下：h=[6,2,3,6,4,2];x=[1,2,3,4,5];y=conv<h,x>;stem<y>结果如图4.1所示：图4.1由图4.1和自己求出的y<n>函数相比较可以得到,用matlab编写程序得出的系统输出函数与自己人工计算的结果相同。2、用函数conv和FFT计算长为1000序列的卷积,比较其计算时间。在matlab实现卷积的.函数为CONV,对于N值较小的向量,这是十分有效的对于N大的向量卷积可用FFT加快计算速度。若DFT和IDFT均采用FFT和IDFT法,可提高卷积速度。计算x1<n>和x2<n>的线性卷积的FFT算法可由下面步骤实现：1、计算X1<k>=FFT[x1<n>];2、计算X2<k>=FFT[x2<n>];3、Y<k>=X1<k>·X2<k>;4、计算x1<n>×x2<n>=IFFT[Y<k>]在本题目中计算的两个函数分别是x1<n>=2*10^n,x2<n>=cos<n^3>。用Matlab编写的程序如下：L=1000;N=L*2-1;n=1:L;x1=2*<n.^10>;x2=cos<n.^3>;t0=clock;yc=conv<x1,x2>;conv_time=etime<clock,t0>N=pow2<nextpow2<L*2-1>>;t0=clock;yf=ifft<fft<x1,N>.*fft<x2,N>>;fft_time=etime<clock,t0>subplot<221>,stem<x1,'.'>;ylabel<'x<n>'>;subplot<222>,stem<x2,'.'>;ylabel<'h<n>'>;subplot<212>,stem<real<yc>,'.'>;ylabel<'y<n>'>;在Matlab中编程以及得出的完成程序所需的时间如图4.2：图4.2输出结果如图4.3：图4.3该题要求的是对用函数conv和FFT计算1000点的序列卷积所需的时间进行对比,通过图4.2可知,用函数conv计算该卷积需要0.0100s,而用FFT计算该卷积需要0s,由此可以得出：FFT算法所消耗的时间远小于函数conv要消耗的时间。3、用快速卷积法计算和两个序列的卷积；并测试直接卷积和快速卷积的时间。利用快速卷积原理求两个函数的卷积可以用题目二中所用的方法〔先分别对两个函数求傅里叶变换得到X<k>与H<k>,再两个函数傅里叶变换的点乘的结果y<k>,最后直接对y<k>求傅里叶反变换得到y<n>快速卷积,得到所要求的结果。因为在这次题目中与两个函数中M与N没有给出,所以就分别取M=50,N=30和M=1500,N=1100分别求该题目所说并得到结果:所用的程序以及输出结果分别如下图所示：〔1M=50,N=30的情况：图4.4图4.5〔2M=1500,N=1100的情况：图4.6图4.7题目3要求计算两序列的卷积,比较直接卷积和快速卷积的时间对比由上图的结果可知,当说算积分的点数比较少时,快速卷积并不占有优势,反而快速卷积所用时间多于正常的卷积conv函数。只有当积分的点数比较多时才会有快速卷积所用时间少于普通卷积的conv函数。5、心得体会在得到这次课设题目以后,我就开始准备资料了,先是上网查阅基本资料,做一个大概的了解,然后发现此次题目卷积和快速卷积在课本上能找到相关的内容,就再在书上进行寻找,发现了书上有介绍快速卷积的方法就进行阅读并学习,在做好准备后就开始进行课设的三个题目了,第一题很好解答很快也完成了,感觉信心倍增,但是在做第二题时,‘’符号打入Matlab中老是不符合规范,进行了多次改进也没办