实验八 利用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)?h(m)x(n?m)????
或
y(n)?h(n)*x(n)?m???
当h(n)是一个有限长序列，即h(n)是FIR滤波器，且0?n?N?1时
y(n)??h(m)x(n?m)m?0N?1
在数字网络（见图6.1）类的FIR滤波器中，普遍使用的横截型结构（见下图6.2）就是按这个卷积公式构成的。
x(n) H(Z) h(n) y(n)
图6.1 滤波器的数字网络实现方法
x(n) Z-1 Z-1 Z-1 Z-1
h(1) h(0) h(2) 图6.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)如图6.3所示。
图6.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
iii.
用FFT计算x(n),h(n)的N点离散傅里叶变换 FFTx(n)????X(k)
FFTh(n)????H(k)
iv. v.
做X(k)和H(k)乘积，Y(k)?X(k)?H(k)
用FFT计算Y(k)的离散傅里叶反变换得
??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)N?1*要补上太多的零点，很不经济，且FFT的计算时间也要很长。为此，采用分段卷积的方法，即把x(n)分成长度与h(n)相仿的一段段，分别求出每段卷积的结果，然后用相应的方式把它们结合起来，便是总的输出。分段卷积方法主要有两种，即重叠相加法和重叠保留法。具体内容请参考教材中“快速离散傅里叶变换”一章中的线性卷积的FFT算法部分，本实验这部分不作重点要求。
三、 实验任务
（1）用FFT实现以下两序列的线性卷积。
?0.8nx(n)???0?1h(n)???0n=[0:1:11]; m=[0:1:5]; N1=length(n); N2=length(m);
0?n?11 其它0?n?5其它
xn=0.8.^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,'.')
title('2015167111(1)??D??í?y');