loading实验七 利用FFT实现快速卷积
一、 实验目的
1、通过这一实验，加深理解FFT在实现数字滤波（或快速卷积）中的重要作用，更好的利用FFT进行数字信号处理。
2、进一步掌握循环卷积和线性卷积两者之间的关系。 二、实验原理
数字滤波器根据系统的单位脉冲响应h(n)是有限长还是无限长可分为有限长单位脉冲响应（Finite Impulse Response）系统（简记为FIR系统）和无限长单位脉冲响应（Infinite Impulse Response）系统（简记为IIR系统）。
对于FIR滤波器来说，除了可以通过数字网络来实现外，也可以通过FFT的变换来实现。
一个信号序列x(n)通过FIR滤波器时，其输出应该是x(n)与h(n)的卷积：
y(n)?x(n)*h(n)?m????x(m)h(n?m)
??
或
y(n)?h(n)*x(n)?m????h(m)x(n?m)??当h(n)是一个有限长序列，即h(n)是FIR滤波器，且0?n?N?1时
y(n)??h(m)x(n?m)m?0N?1
在数字网络（见图7.1）类的FIR滤波器中，普遍使用的横截型结构（见下图7.2）就是按这个卷积公式构成的。
x(n) H(Z) h(n) y(n)
图7.1 滤波器的数字网络实现方法
x(n) Z-1 Z-1 Z-1 Z-1
h(1) h(0) h(2) 图7.2 FIR滤波器横截型结构
h(N-1) h(N-2) y(n)
应用FFT实现数字滤波器实际上就是用FFT来快速计算有限长度列间的线性卷积。
粗略地说，这种方法就是先将输入信号x(n)通过FFT变换为它的频谱采样 值X(k)，然后再和FIR滤波器的频响采样值H(k)相乘，H(k)可事先存放在存储器中，最后再将乘积H(k)X(k)通过快速傅里叶变换（简称IFFT）还原为时域序列，即得到输出y(n)如图7.3所示。
图7.3 数字滤波器的快速傅里叶变换实现方法
现以FFT求有限长序列间的卷积及求有限长度列与较长序列间的卷积为例来讨论FFT的快速卷积方法。
1、序列x(n)和h(n)的列长差不多。设x(n)的列长为N1，h(n)的列长为N2，要求
y(n)?x(n)N
N?1r?0x(n) FFT X(k) X IFFT y(n)
{H(k)} H(k) H(k)X(k) h(n)?x(n)*h(n)??x(r)h(n?r)
用FFT完成这一卷积的具体步骤如下： i.
为使两有限长序列的线性卷积可用其循环卷积代替而不发生混叠，必须选择循环卷积长度N?N1?N2?1，若采用基2-FFT完成卷积运
m算，要求N?2（m为整数）。
用补零方法使x(n)，h(n)变成列长为N的序列。
ii.
?x(n)0?n?N1?1x(n)??N1?n?N?1 ?0?h(n)0?n?N2?1h(n)??N2?n?N?1 ?0用FFT计算x(n),h(n)的N点离散傅里叶变换
iii.
FFTx(n)????X(k)
FFT?H(k) h(n)???iv. 做X(k)和H(k)乘积，Y(k)?X(k)?H(k)
v.
用FFT计算Y(k)的离散傅里叶反变换得
N?1*??1??nk?N?1?1?y(n)???Y(k)?Wx????Y*(k)?Wxnk???k?0?N?k?0?N?
2、当x(n)长度很长时，即N1??N2，通常不允许等x(n)全部采集齐后再进行卷积，否则使输出相对于输入有较长的延时，另外，若N1?N2?1太大，h(n)要补上太多的零点，很不经济，且FFT的计算时间也要很长。为此，采用分段卷积的方法，即把x(n)分成长度与h(n)相仿的一段段，分别求出每段卷积的结果，然后用相应的方式把它们结合起来，便是总的输出。分段卷积方法主要有两种，即重叠相加法和重叠保留法。具体内容请参考教材中“快速离散傅里叶变换”一章中的线性卷积的FFT算法部分，本实验这部分不作重点要求。 三、实验方法
yc(n)?x1(n)Nx2(n)，若序列x1(n)、x2(n)为长度分别为N1、N2的有限长序列，yl(n)?x1(n)*x2(n)。由DFT的性质可知：当N?N1?N2?1时有yl(n)?yc(n)?IDFT[DFT[x1(n)]?DFT[x2(n)]]。序列较长时DFT运算通常用快速算法FFT实现。在MATLAB的信号处理工具箱中函数FFT和IFFT用于快速傅里叶变换和逆变换。函数FFT的调用格式同实验三。 例7.1：用FFT实现下两序列的线性卷积。
?0.8nx(n)???0?1h(n)???0
实现程序： n=[0:1:11]; m=[0:1:5]; N1=length(n); N2=length(m); xn=0.8.^n;
0?n?11其它0?n?5其它
%生成x(n)
%生成h(n)
hn=ones(1,N2); N=N1+N2-1; XK=fft(xn,N); HK=fft(hn,N); YK=XK.*HK;
yn=ifft(YK,N);
if all(imag(xn)==0)&(all(imag(hn)==0)) %实序列的循环卷积仍然为实序列
yn=real(yn); end x=0:N-1; stem(x,yn,’.’) 运行结果：
4321005101520
图6.4 利用FFT实现线性卷积
四、实验内容及要求
1h(n)?()nRN2(n),N22 1、数字滤波器的脉冲响应为可自定，本实验取N2?17
输入序列x(n)可选下列几种情况 i.
x(n)?RN1(n) N1可取16
x(n)?cos2?nRN1(n)N1?16N1
ii.
1x(n)()nRN1(n),N1?163iii.
2、实验前，预先计算好x(n)*h(n)的值。
3、实验前，预先编制一个应用FFT实现数字滤波器的通用程序。 4、上机独立调试，并打印或记录实验结果。
5、将实验结果与预先笔算的结果比较，验证其正确性。
五、思考题
对一个有限长序列进行DFT等价于将该序列周期延拓后进行DFS展开，因为DFS也只是取其中一个周期来计算，所以FFT在一定条件下也可以用以分析周期信号序列。如果实正弦信号sin(2πfn),f=0.1用16点FFT来做DFS运算，得到的频谱时信号本身的真实谱吗？
六、实验报告要求
1、简述实验原理，画出程序框图，并列出实验程序清单，包括必要的程序说明。
2、记录调试运行情况及所遇问题的解决方法。 3、给出实验结果，并对结果作出分析。