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

《序列的卷积和快速卷积运算的编程实现.pdf》由会员分享，可在线阅读，更多相关《序列的卷积和快速卷积运算的编程实现.pdf（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-课程设计任务书课程设计任务书学生：新颖专业班级：电信学生：新颖专业班级：电信 12031203 班班指导教师：阙大顺王虹工作单位：信息工程学院指导教师：阙大顺王虹工作单位：信息工程学院题目题目:序列的卷积和快速卷积运算的编程实现序列的卷积和快速卷积运算的编程实现初始条件初始条件：1.Matlab6.5 以上版本软件；2.课程设计辅导资料：“Matlab 语言根底及使用入门、“数字信号处理原理与实现、“Matlab 及在电子信息课程中的应用等；3.先修课程：信号与系统、数字信号处理、Matlab 应用实践及信号处理类课程等。要求完成的主要任务：要求完成的主要任务：包括课程设计工作量及其技术要求

2、，以及说明书撰写等具体要求1.课程设计时间：1 周课实践；2.课程设计容：序列的卷积和快速卷积运算的编程实现，具体包括：直接卷积及应用、快速卷积方法及实现、两者的比拟分析等；3.本课程设计统一技术要求：研读辅导资料对应章节，对选定的设计题目进展理论分析，针对具体设计局部的原理分析、建模、必要的推导和可行性分析，画出程序设计框图，编写程序代码 含注释，上机调试运行程序，记录实验结果含计算结果和图表，并对实验结果进展分析和总结；4.课程设计说明书按学校“课程设计工作规中的“统一书写格式撰写，具体包括：目录；与设计题目相关的理论分析、归纳和总结；与设计容相关的原理分析、建模、推导、可行性分析；程序设

3、计框图、程序代码含注释、程序运行结果和图表、实验结果分析和总结；课程设计的心得体会至少500 字；参考文献；其它必要容等。指导教师签名：年月日指导教师签名：年月日系主任或责任教师签名：年月日系主任或责任教师签名：年月日-word.zl-摘要摘要卷积在数字信号处理中有着重要的作用。然而直接计算卷积的运算量非常大，它与序列长度的平方成反比，因此制约了卷积的应用。快速卷积是实现卷积的一种快速算法，减少了运算量，节约了时间。通过分析我们可在 MATLAB 里编程实现。关键词：卷积；快速卷积；MATLAB。-word.zl-1、直接卷积及应用 11.1 卷积的定义 11.2、卷积的运用 12、快速卷积方

4、法及实现 12.1 快速卷积运算原理 12.2 实现方法 22.2.1 重叠相加法 32.2.2 重叠保存法 33、直接卷积和快速卷积的分析比拟 44、程序设计及仿真结果分析 45、心得体会 126、参考文献 13-目录目录-word.zl-word.zl-1 1、直接卷积及应用、直接卷积及应用1.11.1 卷积的定义卷积的定义设:f(x),g(x)是 R1 上的两个可积函数，作积分：可以证明，关于几乎所有的实数 x，上述积分是存在的。这样，随着 x 的不同取值，这个积分就定义了一个新函数 h(x)，称为函数 f 与 g 的卷积，记为 h(x)=(f*g)(x)。1.21.2、卷积的运用、卷积

5、的运用卷积是数字信号处理中最常见，也是最重要的运算之一，利用卷积可以实现相关计算和 FIR 滤波等等，正因为卷积如此重要，所以半个世纪以来，学者们提出了多种不同卷积实现构造。设输入信号为 xt,其频谱函数为 Xj该信号通过滤波器 ht后，其输出信号yt的频谱函数 Yj是频谱函数 xj与滤波器的频谱函数 Hj的乘积，即：Yj=XjHj而在时域，输出信号 y(t)实际是输入信号 x(t)与滤波器 h(t)的卷积，就是说频谱函数的乘积相当于时间函数的卷积，反之亦然，即：y(t)=x(t)*h(t)在数字信号处理系统中，无论在时域还是频域都离不开卷积运算和快速傅里叶运算，Matlab 具有强大的矩阵运

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

7、卷积是线性卷积以 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下列图为上述过程的示意图x1(n)yc(n=yl(n)x2(n)L 点的 FFTL 点的 FFTL 点的 IFFT2.22.2 实现方法实现

8、方法在实际应用中，常遇到的问题是参加卷积的两个序列的长度相差较大，这样长度小的序列就需补很多的零点，这样就需要大的存储量，运算时间也会变长。常用的解决方法有两种，一是重叠相加法，另一种是重叠保存法。-word.zl-2.2.12.2.1 重叠相加法重叠相加法设序列 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(

9、n)=x2(n)*xk(n)=x2(m)xk(n-m)式 2.4式2.3表示，计算 x1(n)与 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 个值相加，因为称为重叠相加法。2.2.22.2.2 重叠保存法重叠保存法为了克制重叠相加法中分段卷积后任然需要相加的缺点，人们提出了重叠保存法。与重叠相加法不同的是，在对无限长序列x1(n)的后 M-1 个抽样值与后一段 xk+1(n)的前 M-1 个

10、抽样值一样，且分段的长度选圆周卷积的长度 L，这样形成的分段序列为然后计算 x2n与各分段 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),0nL-1-word.zl-=0其他最后输出序列y(n)=yk(n-kN+M-1)3 3、直接卷积和快速卷积的分析比拟、直接卷积和快速卷积的分析比拟卷积是数字信号处理中最常见的，也是最重要的运算之一。利用卷积可以实现相关计算和 FIR 滤波

11、等等，正因为卷积如此重要，所以半个世纪以来，学者们提出了多种不同卷积实现构造，这些构造各有优点，针对不同应用可以灵活选择，而其中快速卷积无疑是重要的卷积方法之一。顾名思义，快速卷积重点在一个“快，如果对卷积速度要求较高，快速卷积无疑是理想的工具。当然，为了提高速度，就要牺牲面积和功耗4 4、程序设计及仿真结果分析、程序设计及仿真结果分析1 1、线性非移变系统的、线性非移变系统的 h(n)=6,2,3,6,4,2h(n)=6,2,3,6,4,2，输入为，输入为 x(n)=1,2,3,4,5x(n)=1,2,3,4,5；(1)用人工计算系统输出 y(n)；(2)编写程序输出 y(n)，并作图。人工

12、计算：长度为 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;-word.z

13、l-x=1,2,3,4,5;y=conv(h,x);stem(y)结果如图 4.1 所示：图 4.1由图 4.1 和自己求出的 y(n)函数相比拟可以得到，用 matlab 编写程序得出的系统输出函数与自己人工计算的结果一样。2 2、用函数、用函数 convconv 和和 FFTFFT 计算长为计算长为 10001000 序列的卷积，比拟其计算时间。序列的卷积，比拟其计算时间。在 matlab 实现卷积的.函数为 CONV，对于 N 值较小的向量，这是十分有效的对于 N大的向量卷积可用 FFT 加快计算速度。假设 DFT 和 IDFT 均采用 FFT 和 IDFT 法，可提高卷积速度。计算 x

14、1(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);-word.zl-t0=clock;yc=conv(x1,x2);conv_time=etime(clock,t0)N=pow2(nextpow2(L*2-1);

15、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：-word.zl-图 4.3该题要求的是对用函数 conv 和 FFT 计算 1000 点的序列卷积所需的时间进展比照，通过图4.2 可知，用函数co

16、nv 计算该卷积需要 0.0100s，而用FFT 计算该卷积需要 0s，由此可以得出：FFT 算法所消耗的时间远小于函数 conv 要消耗的时间。3 3、用快速卷积法计算用快速卷积法计算x(n)0.9nRM(n)和和h(n)RN(n)两个序列的卷积；两个序列的卷积；并测试直接卷积和快速并测试直接卷积和快速卷积的时间。卷积的时间。利用快速卷积原理求两个函数的卷积可以用题目二中所用的方法先分别对两个函数求傅里叶变换得到 X(k)与 H(k)，再两个函数傅里叶变换的点乘的结果 y(k)，最后直接对 y(k)求傅里叶反变换得到 y(n)快速卷积，得到所要求的结果。因为在这次题目中x(n)0.9nRM(

17、n)与h(n)RN(n)两个函数中 M 与 N 没有给出，所以就分别取 M=50，N=30 和 M=1500，N=1100 分别求该题目所说并得到结果:所用的程序以及输出结果分别如下列图所示：1M=50，N=30 的情况：-word.zl-图 4.4-word.zl-图 4.52M=1500，N=1100 的情况：-word.zl-图 4.6-word.zl-图 4.7题目 3 要求计算两序列的卷积，比拟直接卷积和快速卷积的时间比照由上图的结果可知，当说算积分的点数比拟少时，快速卷积并不占有优势，反而快速卷积所用时间多于正常的卷积 conv 函数。只有当积分的点数比拟多时才会有快速卷积所用时间

18、少于普通卷积的conv 函数。-word.zl-5 5、心得体会、心得体会在得到这次课设题目以后，我就开场准备资料了，先是上网查阅根本资料，做一个大概的了解，然后发现此次题目卷积和快速卷积在课本上能找到相关的容，就再在书上进展寻找，发现了书上有介绍快速卷积的方法就进展阅读并学习，在做好准备后就开场进展课设的三个题目了，第一题很好解答很快也完成了，感觉信心倍增，但是在做第二题时，符号打入 Matlab 中老是不符合规，进展了屡次改良也没方法，于是就在网上找到了类似的借用了一下，过程中也发现了问题，快速傅里叶计算所花费的时间比直接卷积的时间花费更多，这是个遗留问题，对程序进展了很多改良，但是结果每

19、次出来都不一样，但是多几次就会发现规律，还是快速傅里叶变化时间短的次数更多，第三题用第二题的方法类似的方法进展，虽然也遇到了类似的问题但是还是屡次实验取数目得到规律使实验完成，这次课设让我收获了很多，从书本走到了实际这是长足的进步，也让我对知识有了更深得的理解，纸上得来终觉浅，只有真正实际操作过，才能有所得，所以我觉得课设还是要自己做才有意义，一是多多锻炼自己，二是稳固知识加深记忆，遇到问题想方法克制问题，这是很重要的一步，也是自身能力的表达，我希望以后的课设都能靠自己的力量去完成得到更多的东西！-word.zl-6 6、参考文献、参考文献1 泉等.数字信号处理原理与实现第 2 版M.：电子工

20、业，2009.2 丁玉美等.数字信号处理M.：电子科技大学，2001.3 怀琛等.MATLAB 及在电子信息课程中的应用M.：电子工业，2003.4 程佩青.数字信号处理教程M.：清华大学，2008.5 建新等.现代通信系统分析与仿真-MATLAB 通信工具箱M.：电子科技大学-word.zl-附表一：本科生课程设计成绩评定表附表一：本科生课程设计成绩评定表XXXX专业、班级专业、班级课程设计题目：课程设计题目：课程设计辩论或质疑记录：课程设计辩论或质疑记录：电信电信 12031203 班班性别性别男男-word.zl-成绩评定依据：成绩评定依据：最终评定成绩以优、良、中、及格、不及格评定最终评定成绩以优、良、中、及格、不及格评定指导教师指导教师签字：签字：-word.zl-