数字信号课程设计报告-用FFT实现快速卷积.doc

课 程 设 计 报 告 课程名称 _数字信号处理_ 设计题目 _用FFT实现快速卷积_专 业 _通信工程_ 课 程 设 计 任 务 书设计题目：_用FFT实现快速卷积_设计内容与要求：FFT的出现，使DFT在数字通信、语音信号处理、图像处理、功率谱估计、系统分析与仿真、雷达信号处理、光学、地震及数值分析等各个领域都得到广泛应用。然而，各种应用一般都以卷积和相关运算为依据。在实际应用中，为了分析时域离散LTI系统或者序列滤波时，需要计算两个序列的线性卷积。为了提高运算速度，可以利用FFT来实现。要求：参考课本上第90页的内容（3.4.1 用DFT计算线性卷积），设计并编写程序来实现重叠相加法计算线性卷积。课 程 设 计 评 语 成绩： 指导教师：_ 年 月 日目 录第1章 设计任务31.1 原理41.1.2 算法基本思想5第2章 程序设计72.1 程序设计思路82.1.1 函数juanji(x1,x2,L)设计82.1.2函数chongdie（x,h,N）设计82.2 程序流程图8第3章 分析与测试93.1循环卷积设计103.1.1程序103.1.2 测试103.1.3 分析123.2线性卷积设计123.2.1程序123.2.2测试12第4章 实验结果144.1实验结果14第5章 总结15第6章 参考文献16第1章 设计任务计算1个给定序列与输入序列的卷积。功能： 对给定的数据进行卷积运算，要求分段卷积由循环卷积实现。要求设计有数据导入界面，各种参数从软件界面可以输入，其中给定序列可以由界面输入，对运算前后的数据绘制曲线。 要求：1) 初步完成总体设计，搭好框架，确定人机对话的界面，确定函数功能，控制参数的输入方法；2) 设计线性卷积的实现方案；3) 编写两序列作循环卷积的程序；4) 通过直接做线性卷积来检验最后结果。设计步骤：1) 用结构化设计方法。一个程序划分成若干模块，每一个模块的函数功能要划分好，总体设计应画出流程图；2) 输入输出界面要友好；3) 源程序书写要规范，加必要的注释；4) 要提供通过直接卷积进行检验的结果；5) 程序一定要要能运行起来。1.1 原理 1.1.1 算法产生背景 DFT 是连续傅里叶变换在时域和频域上都离散的形式，将时域信号的采样变换为在离散时间傅里叶变换频域的采样。在形式上，变换两端（时域和频域上）的序列是有限长的。DFT 具备明确且合理的物理含义，适合应用于数字系统，同时可以方便地由计算机进行运算。 对于线性非移变离散系统，可由线性卷积表示时域输入输出关系，即 y(n)=x(n)*h(n) = 通常采用循环卷积降低运算量，但实际中往往无法满足对信号处理的实时性要求。因此，产生了重叠相加法和重叠保留法两种典型的算法，用以快速计算线性卷积，成为了DFT 的一个重要应用。 1.1.2 算法基本思想 重叠相加法是将待过滤的信号分割成长为 N 的若干段，每一段都可以和有限时宽单位取样回应作卷积，再将过滤后的各段重叠相加。 在实际应用中利用FFT来计算两个序列的圆周卷积从而实现计算其线性卷积，但是常遇到的问题是参加卷积的两个序列的长度相差较大，这样长度小的序列就需要补很多的零点，这样就需要大的存储量，运算时间也会变长。所以常用重叠相加法来解决。如以下情况： h(n)长度为N，x(n)长度为无限长 x(n)取M点，且与N尽量接近可采用如下方法来解决 x(n)与h(n)的卷积为图1-1 重叠相加法的卷积示意图重叠相加法的步骤如下（1）将h(n)补零延长到L =M+ N -1，并计算长为L的FFT，得到 H(k)。（2）分别将xk(n)补零延长到L =M+ N -1，并计算长为L的FFT，得到 Xk(k)（3）计算，并求长为L的反变换，即（4）将yk(n)的重叠部分相加，最后得到结果为第2章 程序设计2.1 程序设计思路2.1.1 函数juanji(x1,x2,L)设计（1） x1(n)进行N点快速傅里叶变换得X1k（2） x2(n)进行N点快速傅里叶变换得X2k（3） 进行频域相乘Yk=X1k*X2k（4） 对Yk进行反变换得到时域卷积结果y(n)2.1.2函数chongdie（x,h,N）设计（1）首先取圆周卷积的周期L（即进行L点的快速傅里叶变换）（2）计算每一分段的大小N（3）填充序列使得循环中对序列的索引不会超出范围（4）计算分段数K（5）对序列进行分段调用juanji()函数计算圆周卷积（6）各段重叠相加（7）取出实际的输出序列2.2 程序流程图开始对x1(n)进行FFT运算对x(2)进行FFT运算频域相乘Yk=X1k*X2k对Yk进行反变换得到时域结果y(n)结束开始取圆周卷积的周期L计算每一分段的大小N将序列按要求填充计算分段数K调用卷积函数将各段处理的结果重叠相加输出最终结果结束重叠相加法卷积 图2-1 程序流程图第3章 分析与测试3.1循环卷积设计3.1.1程序function y =xhConv(h,X) M = length(hn);if N M N = M+1; endL = M+N-1; Lx = length(x); T = ceil(Lx/N); t = zeros(1,M-1); x = x,zeros(1,(T+1)*N-Lx); y = zeros(1,(T+1)*N); for i=0:1:T xi=i*N+1; x_seg = x(xi:xi+N-1); X1k = fft(x_seg,L); X2k = fft(h,L); Yk = X1k.*X2k; y_seg = ifft(Yk); y_seg(1:M-1)=y_seg(1:M-1)+t(1:M-1); t(1:M-1) = y_seg(N+1:L); y(xi:xi+N-1)=y_seg(1:N); endy=y(1:Lx+M-1) 3.1.2 测试设N=4 h=1,2,3,4 X=1,2,3,4,5,6,7,8,9调用系统函数fftfilt(h,x,N)对比生成图像图3-1-1 设计函数图形图3-1-2 系统函数fftfilt(h,x,N)3.1.3 分析 设计函数与系统函数前7个点一样，系统函数没有后4-1=3个点，4为h(n)长度。设计函数符合要求。3.2线性卷积设计3.2.1程序function z = myConv(A, B) Lx=length(A)+length(B)-1; l1=length(A)-1;l2=length(B)-1;A=zeros(1,l2) A zeros(1,l2); B=fliplr(B); B=B,zeros(1,l1+l2); for i=1:Lx z(i)=A(1)*B(1); for k=2:length(B) z(i)=z(i)+A(k)*B(k); end t=B(length(B); for j=length(B):-1:2 B(j)=B(j-1); end B(1)=t;end 3.2.2测试设h=1,3,5,7 X=9,8,7,6,5,4,3,2,1调用系统函数conv(h,x)对比生成图像图3-2-1 设计函数图形图3-2-2 系统函数conv(h,x)第4章 实验结果4.1实验结果图4-1 实验结果第5章 总结作为电子信息工程系的学生，数字信号处理这门课程是其他很多课程的基础，所以学好学通数字信号处理这门课程对我们来说是非常重要的。而MATLAB这款软件对数字信号处理的建模、编程、分析、实现有极大的帮助作用，所以我们应该掌握使用MATLAB编程来实现对数字信号的处理。此次我得到的课设题目是：通过重叠相加法计算卷积。拿到课设题目后，我仔细研究了与题目相关的原理，包括线性卷积、周期卷积、圆周卷积、重叠相加法、离散傅里叶变换DFT、快速傅里叶变换FFT等原理知识，弄清楚了它们之间的关系。通过这次课程设计，我不仅顺利完成课程设计的要求，而且在课程设计过程中通过对相关原理的回顾，对各相关原理之间的关系有了脱胎换骨般的认识，让我意识到此前学到的知识是多么的浅薄。在和同组同学一起讨论研究通基于重叠相加法的圆周卷积原理后，我开始了利用MATLAB来实现这个功能。在编写程序的过程中，我查阅了很多有关MATLAB的编程知识，通过整合所查阅到的编程知识，结合先前研究的基于重叠相加法的圆周卷积原理，我设计了具有此功能的MATLAB函数。在设计时我遇到了不少的问题，刚开始时我先设定分段长度N，然后由N来求卷积周期L。但是在程序运行过程中我发现算法具有很大的局限性。通过仔细揣摩这其中的问题，原来是我忽略了FFT运算的条件。所以我制定了第二个方案，先设定卷积的周期L，然后由L来求分段长度N，这样程序的适用范围就扩大了。为了提高程序的适用性，我不断的对程序进行修改和测试，以求能够达到更好的效果，这个过程让我体会到了编程解决问题的乐趣。通过这次课程设计，让我加深了对书本知识的理解，并应用课本的理论知识，结合相关软件，设计解决问题的算法。从而提高了由知识转换为技能的能力，提高了自己的实践能力。通过与同学的互相沟通，不仅使各自的知识得到了扩充，而且从中得到了很多的启示，这次课程设计让人受益匪浅。第6章 参考文献【1】高西全、丁玉美.数字信号处理 第三版.西安电子科技大学出版社.2008.【2】罗建军、杨琦.精讲多练MATLAB.西安：西安交通大学出版社.2002.【