序列的卷积和快速卷积运算的编程实现.doc

《序列的卷积和快速卷积运算的编程实现.doc》由会员分享，可在线阅读，更多相关《序列的卷积和快速卷积运算的编程实现.doc（10页珍藏版）》请在课桌文档上搜索。

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

2、目进展理论分析，针对具体设计局部的原理分析、建模、必要的推导和可行性分析，画出程序设计框图，编写程序代码含注释，上机调试运行程序，记录实验结果含计算结果和图表，并对实验结果进展分析和总结；4. 课程设计说明书按学校课程设计工作规中的统一书写格式撰写，具体包括： 目录； 与设计题目相关的理论分析、归纳和总结； 与设计容相关的原理分析、建模、推导、可行性分析； 程序设计框图、程序代码含注释、程序运行结果和图表、实验结果分析和总结； 课程设计的心得体会至少500字； 参考文献； 其它必要容等。指导教师签名：年月日系主任或责任教师签名：年月日摘要卷积在数字信号处理中有着重要的作用。然而直接计算卷积的运

3、算量非常大，它与序列长度的平方成反比，因此制约了卷积的应用。快速卷积是实现卷积的一种快速算法，减少了运算量，节约了时间。通过分析我们可在MATLAB里编程实现。关键词：卷积；快速卷积；MATLAB。目录1、直接卷积及应用21.1卷积的定义21.2、卷积的运用22、快速卷积方法及实现22.1快速卷积运算原理22.2实现方法2重叠相加法2重叠保存法23、直接卷积和快速卷积的分析比拟24、程序设计及仿真结果分析25、心得体会26、参考文献2. z.-1、直接卷积及应用1.1卷积的定义设:f(x),g(x)是R1上的两个可积函数，作积分：可以证明，关于几乎所有的实数x，上述积分是存在的。这样，随着x的

4、不同取值，这个积分就定义了一个新函数h(x)，称为函数f与g的卷积，记为h(x)=(f*g)(x)。1.2、卷积的运用卷积是数字信号处理中最常见，也是最重要的运算之一，利用卷积可以实现相关计算和FIR滤波等等，正因为卷积如此重要，所以半个世纪以来，学者们提出了多种不同卷积实现构造。设输入信号为xt,其频谱函数为Xj该信号通过滤波器ht后，其输出信号yt的频谱函数Yj是频谱函数xj与滤波器的频谱函数Hj的乘积，即： Yj=XjHj而在时域，输出信号y(t)实际是输入信号x(t)与滤波器h(t)的卷积，就是说频谱函数的乘积相当于时间函数的卷积，反之亦然，即： y(t)=x(t)*h(t)在数字信号

5、处理系统中，无论在时域还是频域都离不开卷积运算和快速傅里叶运算，Matlab具有强大的矩阵运算能力。方便实用的绘图功能和语言的高度集成性。在DSP开发中，使用Matlab可以快速对系统进展仿真运算。2、快速卷积方法及实现2.1快速卷积运算原理在信号处理中，许多具体的应用是以线性卷积为根底的。当满足一定条件时，可以用圆周卷积来计算线性卷积。由圆周卷积定理知道，圆周卷积可以借助DFT来运算，因此DFT的快速算法FFT就可以用来计算线性卷积。设x1n与x2n分别是长度为N与M的有限长序列，它们的线性卷积为yln，L点的圆周卷积为ycn，它们的关系为 ycn=yl(n+rL)Rl(n)由上式可知圆周卷

6、积是线性卷积以L为周期进展延拓后，再取主值序列的结果。当满足LM+N-1时，周期延拓不发生混叠，就可以用圆周卷积来计算线性卷积。由圆周卷积定义可知，可以用FFT分别求出x1n与x2n的L点DFT X1k与X2k，即 X1k=DFT x1(n, X2k=DFT x2(n) ,再用IFFT计算X1(kX2(k)的L点IDFT得ycn，也就是x1n与x2n的线性卷积为yl(n),即 yl(n)=yc(n)=IDFTX1(k)X2k下列图为上述过程的示意图L点的FFTx1(n)L点的IFFTyc(n=yl(n)L点的FFTx2(n)2.2实现方法在实际应用中，常遇到的问题是参加卷积的两个序列的长度相差

7、较大，这样长度小的序列就需补很多的零点，这样就需要大的存储量，运算时间也会变长。常用的解决方法有两种，一是重叠相加法，另一种是重叠保存法。重叠相加法设序列x1n为无限长序列，序列x2n是长度为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)与

8、x2n的线性卷积y(n)时，可以先分段计算yk(n),然后再叠加起来即可。因为yk(n)的长度为M+N-1，因此ykn的后N-1个值与yk+1(n)的前N-1个值重叠，因此必须把yk(n)的后N-1个值与yk+1n前的N-1个值相加，因为称为重叠相加法。重叠保存法为了克制重叠相加法中分段卷积后任然需要相加的缺点，人们提出了重叠保存法。与重叠相加法不同的是，在对无限长序列x1(n)的后M-1个抽样值与后一段xk+1(n)的前M-1个抽样值一样，且分段的长度选圆周卷积的长度L，这样形成的分段序列为然后计算x2n与各分段x1k(n)之间的卷积： Yk=x2(n)*x1k(n)显然，yk(n)的前M-

9、1个值发生了混叠，不等于x2(n)与x1k(n)的线性卷积。把yk(n)的前M-1个值舍去，保存yk(n)没有发生混叠的后N个值，形成序列 X1k= x(n+kN-M+1), 0nL-1 = 0 其他最后输出序列 y(n)= yk(n-kN+M-1)3、直接卷积和快速卷积的分析比拟卷积是数字信号处理中最常见的，也是最重要的运算之一。利用卷积可以实现相关计算和FIR滤波等等，正因为卷积如此重要，所以半个世纪以来，学者们提出了多种不同卷积实现构造，这些构造各有优点，针对不同应用可以灵活选择，而其中快速卷积无疑是重要的卷积方法之一。顾名思义，快速卷积重点在一个快，如果对卷积速度要求较高，快速卷积无疑

10、是理想的工具。当然，为了提高速度，就要牺牲面积和功耗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

11、-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

12、和IDFT均采用FFT和IDFT法，可提高卷积速度。计算x1(n)和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)

13、 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可知

14、，用函数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分别求该题目所说并得到结果:所用的程序以及输出结果分别如下列图

15、所示：1M=50，N=30的情况：图4.4图4.52M=1500，N=1100的情况：图4.6图4.7题目3要求计算两序列的卷积，比拟直接卷积和快速卷积的时间比照由上图的结果可知，当说算积分的点数比拟少时，快速卷积并不占有优势，反而快速卷积所用时间多于正常的卷积conv函数。只有当积分的点数比拟多时才会有快速卷积所用时间少于普通卷积的conv函数。5、心得体会在得到这次课设题目以后，我就开场准备资料了，先是上网查阅根本资料，做一个大概的了解，然后发现此次题目卷积和快速卷积在课本上能找到相关的容，就再在书上进展寻找，发现了书上有介绍快速卷积的方法就进展阅读并学习，在做好准备后就开场进展课设的三个

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

17、觉得课设还是要自己做才有意义，一是多多锻炼自己，二是稳固知识加深记忆，遇到问题想方法克制问题，这是很重要的一步，也是自身能力的表达，我希望以后的课设都能靠自己的力量去完成得到更多的东西！6、参考文献1 泉等.数字信号处理原理与实现第2版M.：电子工业，2009. 2 丁玉美等.数字信号处理M.：电子科技大学，2001. 3 怀琛等.MATLAB及在电子信息课程中的应用M.：电子工业，2003. 4 程佩青.数字信号处理教程M.：清华大学，2008. 5 建新等.现代通信系统分析与仿真-MATLAB通信工具箱M.：电子科技大学附表一：本科生课程设计成绩评定表XX性别男专业、班级电信1203班课程设计题目：课程设计辩论或质疑记录：成绩评定依据：最终评定成绩以优、良、中、及格、不及格评定指导教师签字：. z.