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

1、课程设计名称：数字信号处理课程设计课程设计题目：序列的卷积和快速卷积运算的编程实现初始条件：1. Matlab6.5以上版本软件；2. 课程设计辅导资料：“Matlab语言基础及使用入门”、“数字信号处理原理与实现”、“Matlab及在电子信息课程中的应用”等；3. 先修课程：信号与系统、数字信号处理、Matlab应用实践及信号处理类课程等。要求完成的主要任务：（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1. 课程设计时间：1周（课内实践）；2. 课程设计内容：序列的卷积和快速卷积运算的编程实现，具体包括：直接卷积及应用、快速卷积方法及实现、两者的比较分析等；3. 本课程设计统

2、一技术要求：研读辅导资料对应章节，对选定的设计题目进行理论分析，针对具体设计部分的原理分析、建模、必要的推导和可行性分析，画出程序设计框图，编写程序代码（含注释），上机调试运行程序，记录实验结果（含计算结果和图表），并对实验结果进行分析和总结；4. 课程设计说明书按学校“课程设计工作规范”中的“统一书写格式”撰写，具体包括： 目录； 与设计题目相关的理论分析、归纳和总结； 与设计内容相关的原理分析、建模、推导、可行性分析； 程序设计框图、程序代码（含注释）、程序运行结果和图表、实验结果分析和总结； 课程设计的心得体会（至少500字）； 参考文献； 其它必要内容等。附具体设计内容：1. 已知线性

3、非移变系统的h(n)=6,2,3,6,4,2，输入为x(n)=1,2,3,4,5；（1） 用人工计算系统输出y(n)；（2） 编写程序输出y(n)，并作图。2. 用函数conv和FFT计算长为1000序列的卷积，比较其计算时间。3. 用快速卷积法计算和两个序列的卷积；并测试直接卷积和快速卷时间。 摘要卷积在数字信号处理中有着重要的作用。然而直接计算卷积的运算量非常大，它与序列长度的平方成反比，因此制约了卷积的应用。快速卷积是实现卷积的一种快速算法，减少了运算量，节约了时间。通过分析我们可在MATLAB里编程实现。关键词：卷积；快速卷积；MATLAB。目录一、直接卷积及应用11、卷积的定义12、

4、卷积的运用1二、快速卷积方法及实现21、快速卷积运算原理22、实现方法3（1）重叠相加法3（2）重叠保留法3三、直接卷积和快速卷积的分析比较4四、程序设计及仿真结果分析4五、心得体会11六、参考文献12一、直接卷积及应用1、卷积的定义设:f(x),g(x)是R1上的两个可积函数，作积分：可以证明，关于几乎所有的实数x，上述积分是存在的。这样，随着x的不同取值，这个积分就定义了一个新函数h(x)，称为函数f与g的卷积，记为h(x)=(f*g)(x)。2、卷积的运用 卷积是数字信号处理中最常见，也是最重要的运算之一，利用卷积可以实现相关计算和FIR滤波等等，正因为卷积如此重要，所以半个世纪以来，学

5、者们提出了多种不同卷积实现结构。设输入信号为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可以快速对系统进行仿真运算。二、快速卷积

6、方法及实现1、快速卷积运算原理在信号处理中，许多具体的应用是以线性卷积为基础的。当满足一定条件时，可以用圆周卷积来计算线性卷积。由圆周卷积定理知道，圆周卷积可以借助DFT来运算，因此DFT的快速算法FFT就可以用来计算线性卷积。设x1（n）与x2（n）分别是长度为N与M的有限长序列，它们的线性卷积为yl（n），L点的圆周卷积为yc（n），它们的关系为 yc（n）=yl(n+rL)Rl(n)由上式可知圆周卷积是线性卷积以L为周期进行延拓后，再取主值序列的结果。当满足LM+N-1时，周期延拓不发生混叠，就可以用圆周卷积来计算线性卷积。由圆周卷积定义可知，可以用FFT分别求出x1（n）与x2（n）的

7、L点DFT X1（k）与X2（k），即 X1（k）=DFT x1(n）, X2（k）=DFT x2(n) ,再用IFFT计算X1(k）X2(k)的L点IDFT得yc（n），也就是x1（n）与x2（n）的线性卷积为yl(n),即 yl(n)=yc(n)=IDFTX1(k)X2（k）下图为上述过程的示意图L点的FFTx1(n)L点的IFFTyc(n）=yl(n)L点的FFTx2(n)2、实现方法在实际应用中，常遇到的问题是参加卷积的两个序列的长度相差较大，这样长度小的序列就需补很多的零点，这样就需要大的存储量，运算时间也会变长。常用的解决方法有两种，一是重叠想加法，另一种是重叠保留法。（1）重叠相

8、加法 设序列x1（n）为无限长序列，序列x2（n）是长度为M的序列，由x1(n)构成长度为N的有限长序列 x1k(n)= x1(n), kNn(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

9、，因此yk（n）的后N-1个值与yk+1(n)的前N-1个值重叠，因此必须把yk(n)的后N-1个值与yk+1（n）前的N-1个值相加，因为称为重叠相加法。（2）重叠保留法 为了克服重叠相加法中分段卷积后任然需要相加的缺点，人们提出了重叠保留法。与重叠相加法不同的是，在对无限长序列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个值

10、舍去，保留yk(n)没有发生混叠的后N个值，形成序列 X1k= x(n+kN-M+1), 0nL-1 = 0 其他最后输出序列 y(n)= yk(n-kN+M-1)三、直接卷积和快速卷积的分析比较卷积是数字信号处理中最常见的，也是最重要的运算之一。利用卷积可以实现相关计 算和FIR滤波等等，正因为卷积如此重要，所以半个世纪以来，学者们提出了多种不同卷积实现结构，这些结构各有优点，针对不同应用可以灵活选择，而其中快速卷积无疑是重要的卷积方法之一。顾名思义，快速卷积重点在一个“快”，如果对卷积速度要求较高，快速卷积无疑是理想的工具。当然，为了提高速度，就要牺牲面积和功耗四、程序设计及仿真结果分析1

11、、已知线性非移变系统的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)那么根据这个规律人工计算的结果为

12、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)和

13、x2(n)的线性卷积的FFT算法可由下面步骤实现： 1、计算X1(k)=FFTx1(n); 2、计算X2(k)=FFTx2(n); 3、Y(k)=X1(k)X2(k); 4、计算x1(n)x2(n)=IFFTY(k) 在本题目中计算的两个函数分别是x1(n)=2*10n,x2(n)=cos(n3)。用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;

14、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计算

15、该卷积需要0s，由此可以得出：FFT算法所消耗的时间远小于函数conv要消耗的时间。3、用快速卷积法计算和两个序列的卷积；并测试直接卷积和快速卷积的时间。利用快速卷积原理求两个函数的卷积可以用题目二中所用的方法（先分别对两个函数求傅里叶变换得到X(k)与H(k)，再两个函数傅里叶变换的点乘的结果y(k)，最后直接对y(k)求傅里叶反变换得到y(n)）快速卷积，得到所要求的结果。 因为在这次题目中与 两个函数中M与N没有给出，所以就分别取M=50，N=30和M=1500，N=1100分别求该题目所说并得到结果: 所用的程序以及输出结果分别如下图所示：（1）M=50，N=30的情况：图4.4图4.

16、5（2）M=1500，N=1100的情况：图4.6 图4.7题目3要求计算两序列的卷积，比较直接卷积和快速卷积的时间对比由上图的结果可知，当说算积分的点数比较少时，快速卷积并不占有优势，反而快速卷积所用时间多于正常的卷积conv函数。只有当积分的点数比较多时才会有快速卷积所用时间少于普通卷积的conv函数。五、心得体会在得到这次课设题目以后，我就开始准备资料了，先是上网查阅基本资料，做一个大概的了解，然后发现此次题目卷积和快速卷积在课本上能找到相关的内容，就再在书上进行寻找，发现了书上有介绍快速卷积的方法就进行阅读并学习，在做好准备后就开始进行课设的三个题目了，第一题很好解答很快也完成了，感觉

17、信心倍增，但是在做第二题时，符号打入Matlab中老是不符合规范，进行了多次改进也没办法，于是就在网上找到了类似的借用了一下，过程中也发现了问题，快速傅里叶计算所花费的时间比直接卷积的时间花费更多，这是个遗留问题，对程序进行了很多改进，但是结果每次出来都不一样，但是多几次就会发现规律，还是快速傅里叶变化时间短的次数更多，第三题用第二题的方法类似的方法进行，虽然也遇到了类似的问题但是还是多次实验取数目得到规律使实验完成，这次课设让我收获了很多，从书本走到了实际这是长足的进步，也让我对知识有了更深得的理解，纸上得来终觉浅，只有真正实际操作过，才能有所得，所以我觉得课设还是要自己做才有意义，一是多多锻炼自己，二是巩固知识