数字信号处理课程设计-用fft实现快速卷积大学论文.doc

洛 阳 理 工 学 院

课 程 设 计 报 告

课程名称 数字信号处理课程设计
设计题目 用FFT实现快速卷积
专 业 通信工程
班 级
学 号
姓 名
完成日期 2015.06.15

课 程 设 计 任 务 书
设计题目： 用FFT实现快速卷积
设计内容与要求：
FFT的出现，使DFT在数字通信、语音信号处理、图像处理、功率谱估计、系统分析与仿真、雷达信号处理、光学、地震及数值分析等各个领域都得到广泛应用。然而，各种应用一般都以卷积和相关运算为依据。在实际应用中，为了分析时域离散LTI系统或者序列滤波时，需要计算两个序列的线性卷积。为了提高运算速度，可以利用FFT来实现。
要求：参考课本上第90页的内容（3.4.1 用DFT计算线性卷积），设计并编写程序来实现重叠相加法计算线性卷积。

课 程 设 计 评 语

成绩：
指导教师：_______________
年 月 日

洛 阳 理 工 学 院 课 程 设 计 报 告
目 录

第1章 概述 1
1.1Matlab简介 1
1.2设计目的 2
1.3设计原理 2
1.3.1算法产生背景 2
1.3.2算法基本思想 2
第2章 程序设计 5
第3章 分析与测试 7
3.1循环卷积设计 7
3.2 线性卷积设计 9
3.3 设计结果 11
第4章 心得体会 12
参考文献 13

13
第1章 概述
随着信息时代和数字世界的到来，数字信号处理已成为当今一门极其重要的学科和技术领域，数字信号处理在通信、语音、图像、自动控制、医疗和家用电器等众多领域得到了广泛的应用。任意一个信号都具有时域与频域特性，信号的频谱完全代表了信号，因而研究信号的频谱就等于研究信号本身。通常从频域角度对信号进行分析与处理，容易从信号的特性获得更加深入的了解。因此，信号的频谱分析是数字信号处理技术中一种较为重要的工具。

1.1 Matlab简介
Matlab语言是当今国际上科学界最具影响力、也是最有活力的软件。它起源于矩阵运算，并已经发展成一种高度集成的计算机语言。它是由美国Math Works公司于1982年推出的软件产品，取名来源于Matrix Laboratory,简称“Matlab”。Matlab是一个完整的、可扩展的、高性能数值计算的可视化软件，是一种进行科学工程计算的交互式程序设计语言。它提供了强大的科学运算、灵活的程序设计流程、高质量的图形可视化与界面设计、便捷的与其他程序和语言接口的功能。
Matlab 语言在各国高校与研究单位起着重大的作用，MatLab控制系统仿真软件是当今国际控制界公认的标准计算软件，1999年春MatLab 5.3版问世，使MATLAB拥有更丰富的数据类型和结构、更友善的面向对象、更加快速精良的图形可视、更广博的数学和数据分析资源、更多的应用开发工具。特别是Simulink这一个交互式操作的动态系统建模、仿真、分析集成环境的出现，使人们有可能考虑许多以前不得不做简化假设的非线性因素、随机因素，从而即使学生没有对非线性动态系统进行分析研究的数学基础，仍可通过仿真来认知非线性对系统动态的影响。它的信号处理工具箱包含了各种经典的和现代数字信号处理技术，是一个非常优秀的算法研究与辅助设计工具。

1.2 设计目的
1.加深理解FFT在实现快速卷积中的重要作用，更好地利用FFT进行数字信号处理。
2.进一步掌握利用重叠相加法计算线性卷积的方法。

1.3 设计原理
1.3.1算法产生背景
DFT 是连续傅里叶变换在时域和频域上都离散的形式，将时域信号的采样变换为在离散时间傅里叶变换频域的采样。在形式上，变换两端（时域和频域上）的序列是有限长的。DFT 具备明确且合理的物理含义，适合应用于数字系统，同时可以方便地由计算机进行运算。  
对于线性非移变离散系统，可由线性卷积表示时域输入输出关系，即

y(n) = x(n) * h(n)

通常采用循环卷积降低运算量，但实际中往往无法满足对信号处理的实时性要求。因此，产生了重叠相加法和重叠保留法两种典型的算法，用以快速计算线性卷积，成为了DFT 的一个重要应用。

1.3.2算法基本思想
重叠相加法是将待过滤的信号分割成长为 N 的若干段，，每一段都可以和有限时宽单位取样回应作卷积，再将过滤后的各段重叠相加。  
在实际应用中利用FFT来计算两个序列的圆周卷积从而实现计算其线性卷积，但是常遇到的问题是参加卷积的两个序列的长度相差较大，这样长度小的序列就需要补很多的零点，这样就需要大的存储量，运算时间也会变长。所以常用重叠相加法来解决。 
如以下情况： 
        h(n)长度为N，x(n)长度为无限长  ；    
  x(n)取M点，且与N尽量接近；
可采用如下方法来解决：

x(n)与h(n)的卷积为：

重叠相加法示意图：
重叠相加法的步骤如下 
（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程序设计思路

1.函数juanji(x1,x2,L)设计 ：
（1） x1(n)进行N点快速傅里叶变换得X1k 
（2） x2(n)进行N点快速傅里叶变换得X2k 
（3） 进行频域相乘Yk=X1k*X2k 
（4） 对Yk进行反变换得到时域卷积结果y(n) 

2.函数chongdie（x,h,N）设计 ：
（1）首先取圆周卷积的周期L（即进行L点的快速傅里叶变换） 
（2）计算每一分段的大小N 
（3）填充序列使得循环中对序列的索引不会超出范围 
（4）计算分段数K 
（5）对序列进行分段调用juanji()函数计算圆周卷积 
（6）各段重叠相加 
（7）取出实际的输出序列

2.2程序流程图

卷积： 重叠相加法：

第3章 分析与测试
3.1循环卷积设计
 1、 程序 
     M = length(h); 
if N <M        %为N选择合适的值保证运算正确     
 N = M+1;  
end 
L = M+N-1;     %循环卷积与线性卷积结果相同时需要进行运算的最少点
数 
Lx = length(x);          
T = ceil(Lx/N);      %确定分段数
T t = zeros(1,M-1);        %初始化序列t(n)
 x = [x,zeros(1,(T+1)*N-Lx)];      %不足的分段补零  
y = zeros(1,(T+1)*N);           %生成输出序列y(n),长度足够长  
for i=0:1:T      
xi=i*N+1; 
     x_seg = x(xi:xi+N-1);        %选择低点数计算时的分段x(n)     
X1k = fft(x_seg,L);          %x_seg做L点FFT    
 X2k = fft(h,L);              %h做L点FFT   
  Yk = X1k.*X2k;               %频域相乘
y_seg = ifft(Yk);            %FFT反变换得循环卷积结果     
y_seg(1:M-1)=y_seg(1:M-1)+t(1:M-1); %完成重叠相加  
     t(1:M-1) = y_seg(N+1:L);     %重新对t(n)赋值为保留的后M-1点      
y(xi:xi+N-1)=y_seg(1:N);     %直接输出前N个点 
 end 
y=y(1:Lx+M-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 设计函数图像

图3-2 系统函数fftfilt(h,x,N)
3、分析 
  设计函数与系统函数前7个点一样，系统函数没有后4-1=3个点， 4为h(n)长度。设计函数符合要求。

3.2 线性卷积设计 
1、程序 
Lx=length(A)+length(B)-1;   %线性卷积长度 
l1=length(A)-1; l2=length(B)-1; 
A=[zeros(1,l2) A zeros(1,l2)];   %A序列前后补零 
B=fliplr(B); %反转B 
B=[B,zeros(1,l1+l2)];   %B序列后面补零 与A长度相等 
for i=1:Lx    %计算z(i)     
z(i)=A(1)*B(1);
for k=2:length(B)         
  z(i)=z(i)+A(k)*B(k);         
end
t=B(length(B));     %保存B序列最后一个数     
for j=length(B):-1:2    %B序列依次向后移位          
 B(j)=B(j-1);             
end     
B(1)=t; 
end
2、测试 
设h=[1,3,5,7] 
  X=[9,8,7,6,5,4,3,2,1] 
调用系统函数conv(h,x) 
对比生成图像

图3-3 设计函数图像

图3-4 系统函数conv(h,x)

3.3 设计结果
重叠相加法实现卷积：

第4章 心得体会
数字信号处理作为我们的主要专业课之一，虽然在大三开学初我对这门课并没有什么兴趣，觉得那些程序和公式枯燥乏味，但在这次课程设计后我发现自己在一点一滴的努力中对数字信号处理的兴趣也在逐渐增加。
在设计课程过程中遇到问题是很正常的，但我们应该将每次遇到的问题记录下来，并分析清楚，以免下次再碰到同样的问题的课程设计结束了，但是从中学到的知识会让我受益终身。发现、提出、分析、解决问题和实践能力的提高都会受益于我在以后的学习、工作和生活中。设计过程，好比是我们人类成长的历程，常有一些不如意，但毕竟这是第一次做，难免会遇到各种各样的问题。在设计的过程中发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固。我们通过查阅大量有关资料，并在小组中互相讨论，交流经验和自学，若遇到实在搞不明白的问题就会及时请教老师，使自己学到了不少知识，也经历了不少艰辛，但收获同样巨大。通过这次课程设计我也发现了自身存在的不足之处，虽然感觉理论上已经掌握，但在运用到实践的过程中仍有意想不到的困惑，经过一番努力才得以解决。这也激发了我今后努力学习的兴趣，我想这将对我以后的学习产生积极的影响。通过这次设计，我懂得了学习的重要性，了解到理论知识与实践相结合的重要意义，学会了坚持、耐心和努力，这将为自己今后的学习和工作做出了最好的榜样。我觉得作为一名通信专业的学生，数字信号的课程设计是很有意义的。更重要的是如何把自己平时所学的东西应用到实际中。虽然自己对于这门课懂的并不多，很多基础的东西都还没有很好的掌握，觉得很难，也没有很有效的办法通过自身去理解，但是靠着这一个多礼拜的“学习”，在小组同学的帮助和讲解下，渐渐对这门课逐渐产生了些许的兴趣，自己开始主动学习并逐步从基础慢慢开始弄懂它。我认为这个收获应该说是相当大的。觉得课程设计反映的是一个从理论到实际应用的过程，但是更远一点可以联系到以后毕业之后从学校转到踏上社会的一个过程。小组人员的配合﹑相处，以及自身的动脑和努力，都是以后工作中需要的。
最后，对给过我帮助的所有同学和各位指导老师再次表示忠心的感谢！

参考文献
[1]刘泉、阙大顺、郭志强，《数字信号处理》，电子工业出版社，2009
[2]Ingle.V.K，《数字信号处理(MATLAB版)(第2版)》，西安交通大学出版社,2008
[3]张德丰 ,《详解MATLAB 数字信号处理》, 电子工业出版社,2010
[4]程佩青，《数字信号处理教程(第3版)》，清华大学出版社，2008
[5]张志涌，《MATLAB教程》，北京航天航空大学出版社，2005