利用FFT实现快速卷积

———————————————————————————————— 作者： ———————————————————————————————— 日期:

ﻩ

一、实验原理

应用FFT实现数字滤波器实际上就是用FFＴ来快速计算有限长度序列的线性卷积。这种方法就是先将输入信号ｘ(n)通过FFT变换为它的频谱采样值X（k)，然后再和FＩR滤波器的频响采样值H(k)相乘,H（k）可事先存放在存储器中，最后再将乘积H(k）X(ｋ）通过快速傅里叶变换（简称ＩFFT）还原为时域序列,即得到输出ｙ(n)。

现以FFT求有限长序列间的卷积及求有限长度序列与较长序列间的卷积为例来讨论FＦT的快速卷积方法。

（1)序列x(n)和ｈ(ｎ)的长差不多。设ｘ(n)的长为N1，h（n)的长为N2,要求

N1y(n)x(n)y(n)h(m)x(nm)

m0用FＦT完成这一卷积的具体步骤如下：

①为使两有限长序列的线性卷积可用其循环卷积代替而不发生混叠,必须选择循环卷积长度NN1N21,若采用基2-FFT完成卷积运算,要求N2(m为整数)。

m②用补零方法使x（ｎ)和ｈ(n)变成列长为N的序列。

x(n)0nN11 x(n)N1nN10h(n)0nN21 h(n)0NnN12③用FFＴ计算x(n)和ｈ(ｎ)的N点离散傅里叶变换 ④完成Ｘ(ｋ)和H(k)乘积,Y(k)X(k)H(k) ⑤用FFT计算Y(k)的离散傅里叶反变换得

*1nkN11*nky(n)Y(k)WNY(k)WN

k0Nk0N

（2）当x(ｎ)长度很长时，即N1N2,通常不允许等ｘ（ｎ）全部采集齐后再进行卷积，否则使输出相对于输入有较长的延时,另外，若N1N21太大，h(n)要补上太多的零点，很不经济,且FＦT的计算时间也要很长。为此，采用分段卷积的方法，即把x(n)分成长度

与h(n)相仿的一段段，分别求出每段卷积的结果，然后用相应的方式把它们结合起来,便是总的输出。

N1

二、实验内容与要求

⑴给定两个序列x（n）＝[２，1,1,2］,h（n)=[1，-1,-１,1]。首先直接在时域计算两者的线性卷积；其次用FFT快速计算二者的线性卷积，验证结果。

ﻩ⑵数字滤波器的脉冲响应为h(n）=(-)RN2(n), ,N2可自定,本实验取N2=17 输入序列x(ｎ)可选下列几种情况: ﻩ①X（n）＝ＲN1(n),N1可自取16

②ｘ(n)＝cos(

12n2n)RN1(n),N1＝16 N1ﻩ③X(n）=() ＲN1(n), N1=16

ﻩ⑶实验前，预先编制一个应用FＦT实现数字滤波器的通用程序。 ⑷上机独立调试,并打印或记录实验结果。

⑸将实验结果与预先笔算的结果比较，验证其正确性。

13n

三、实验过程

x＝[2,1，1,2];

h＝［1 -1 -１ 1]; XK＝ffｔ(x,N）； HK=fft(h,N）； YK=XK.*ＨＫ； yn=ifft(YK,N);

if all(imａg（x)=＝0)&（alｌ(imag(h)==0)) yｎ=rｅal(yｎ); enｄ

ｙ=coｎv(ｘ,ｈ); ｎ＝０：N-1; subpｌot(2，1,1); steｍ（n，y）;

ylabel（'时域计算'）; subｐｌｏt(2，1，2)； sｔem(n，yｎ,'.＇);

ｙlabeｌ（'FFＴ快速＇);

ｎ=[0：１:15]; ｍ＝［0:１:１6］; N1=ｌｅｎｇth(n）; Ｎ2=lenｇtｈ(m); xn=onｅs(1,N1); hn=(-0.5).^m; Ｎ=N1＋N2-1; XＫ=fｆt(xn，N); ＨK=fft(hｎ,N); YK=XK.*HK;

yn=ｉfｆt(YK,N）;

ｉf all(imaｇ(xｎ)=＝0)&（all(imag(ｈn)＝=0)) yn＝real(yn)； stem(x,ｙn,'.');

n＝[0：1:15];

ｍ=[０:１:１6]； N1=ｌengｔｈ(n）； N2＝lｅngtｈ(m）;

xn=cos(2*pi＊n/N1)； hn＝(-0.５).^ｍ; N＝Ｎ1+Ｎ2-1； XＫ=fft(xｎ,N); HK=ffｔ（hn,N); YK＝XK．*HK；

yn＝iffｔ(YＫ，N);

if ａll(imaｇ（xｎ)＝=０)&（all(iｍag(hｎ)==0)） ｙn＝real(yn); enｄ

x=０：N-１; ｓtｅm(x，ｙn，＇.');

ｎ=[0:1:15］； m=［0：１:１6］; N1=length(n）; N２=lengｔh(m); xn=(1/３).^n; hn=(-0.5）．＾m； N=Ｎ1+Ｎ２-1； ＸＫ=fft（xn，N);

HK=ffｔ（hn,Ｎ）; YK=ＸK.*ＨＫ；

yn=iｆft(YＫ,N)；

iｆ ａll（imag（xn）==0）&(all(imａｇ（hn）==0)） yn=reaｌ(ｙn）； ｅnd

ｘ＝０:Ｎ-1; stem(x,ｙn,'.'）；