利用FFT实现快速卷积

一、实验原理应用FFT实现数字滤波器实际上就是用FFT来快速计算有限长度序列的线性卷积。这种方法就是先将输入信号x(n)通过FFT变换为它的频谱采样值X(k)，然后再和FIR滤波器的频响采样值H(k)相乘，H(k)可事先存放在存储器中，最后再将乘积H(k)X(k)通过快速傅里叶变换（简称IFFT）还原为时域序列，即得到输出y(n)。现以FFT求有限长序列间的卷积及求有限长度序列与较长序列间的卷积为例来讨论FFT的快速卷积方法。（1）序列x(n)和h(n)的长差不多。设x(n)的长为N1，h(n)的长为N2，要求10)()()()()(Nmmnxmhnynxny用FFT完成这一卷积的具体步骤如下：①为使两有限长序列的线性卷积可用其循环卷积代替而不发生混叠，必须选择循环卷积长度121NNN，若采用基2-FFT完成卷积运算，要求mN2（m为整数）。②用补零方法使x(n)和h(n)变成列长为N的序列。1010)()(11NnNNnnxnx1010)()(22NnNNnnhnh③用FFT计算x(n)和h(n)的N点离散傅里叶变换④完成X(k)和H(k)乘积，)()()(kHkXkY⑤用FFT计算Y(k)的离散傅里叶反变换得*10*10)(1)(1)(NknkNnkNNkWkYNWkYNny（2）当x(n)长度很长时，即21NN，通常不允许等x(n)全部采集齐后再进行卷积，否则使输出相对于输入有较长的延时，另外，若121NN太大，h(n)要补上太多的零点，很不经济，且FFT的计算时间也要很长。为此，采用分段卷积的方法，即把x(n)分成长度与h(n)相仿的一段段，分别求出每段卷积的结果，然后用相应的方式把它们结合起来，便是总的输出。二、实验内容与要求⑴给定两个序列x(n)=[2,1,1,2],h(n)=[1,-1,-1,1]。首先直接在时域计算两者的线性卷积；其次用FFT快速计算二者的线性卷积，验证结果。⑵数字滤波器的脉冲响应为h(n)=(-),()212nRNn,N2可自定，本实验取N2=17输入序列x(n)可选下列几种情况：①X(n)=R1N(n),N1可自取16②x(n)=cos()()211nRnNN,N1=16③X(n)=(n)31R1N(n),N1=16⑶实验前，预先编制一个应用FFT实现数字滤波器的通用程序。⑷上机独立调试，并打印或记录实验结果。⑸将实验结果与预先笔算的结果比较，验证其正确性。三、实验过程x=[2,1,1,2];h=[1-1-11];XK=fft(x,N);HK=fft(h,N);YK=XK.*HK;yn=ifft(YK,N);ifall(imag(x)==0)&(all(imag(h)==0))yn=real(yn);endy=conv(x,h);n=0:N-1;subplot(2,1,1);stem(n,y);ylabel('时域计算');subplot(2,1,2);stem(n,yn,'.');ylabel('FFT快速');n=[0:1:15];m=[0:1:16];N1=length(n);N2=length(m);xn=ones(1,N1);hn=(-0.5).^m;N=N1+N2-1;XK=fft(xn,N);HK=fft(hn,N);YK=XK.*HK;yn=ifft(YK,N);ifall(imag(xn)==0)&(all(imag(hn)==0))yn=real(yn);stem(x,yn,'.');n=[0:1:15];m=[0:1:16];N1=length(n);N2=length(m);xn=cos(2*pi*n/N1);hn=(-0.5).^m;N=N1+N2-1;XK=fft(xn,N);HK=fft(hn,N);YK=XK.*HK;yn=ifft(YK,N);ifall(imag(xn)==0)&(all(imag(hn)==0))yn=real(yn);endx=0:N-1;stem(x,yn,'.');n=[0:1:15];m=[0:1:16];N1=length(n);N2=length(m);xn=(1/3).^n;hn=(-0.5).^m;N=N1+N2-1;XK=fft(xn,N);HK=fft(hn,N);YK=XK.*HK;yn=ifft(YK,N);ifall(imag(xn)==0)&(all(imag(hn)==0))yn=real(yn);endx=0:N-1;stem(x,yn,'.');