利用FFT實現(xiàn)快速卷積

1、利用FFT實現(xiàn)快速卷積一、實驗原理應(yīng)用FFT實現(xiàn)數(shù)字濾波器實際上就是用 FFT來快速計算有限長度序列的線性卷積。這種方法 就是先將輸入信號x(n)通過FFT變換為它的頻 譜采樣值X(k)，然后再和FIR濾波器的頻響采 樣值H(k)相乘，H(k)可事先存放在存儲器中， 最后再將乘積H(k)X(k)通過快速傅里葉變換(簡 稱IFFT)還原為時域序列，即得到輸出y(n)。現(xiàn)以FFT求有限長序列間的卷積及求有限長度序列與較長序列間的卷積為例來討論FFT的快速卷積方法。(1)序列x(n)和h(n)的長差不多。設(shè)x(n) 的長為N，h(n)的長為N2，要求N 1y(n) x(n) y(n)h(m)x (n

2、 m)m 0用FFT完成這一卷積的具體步驟如下： 為使兩有限長序列的線性卷積可用其循環(huán) 卷積代替而不發(fā)生混疊，必須選擇循環(huán)卷積長度N Ni N2 1，若采用基2-FFT完成卷積運算，要求 N 2m ( m為整數(shù))。 用補零方法使x(n)和h(n)變成列長為N的 序列。x(n)h(n)x(n)0nNi10N1nN1h(n)0nN210N2nN1 用FFT計算x(n)和h(n)的N點離散傅里葉 變換 完成X(k)和H(k)乘積， Y(k) X(k)H (k) 用FFT計算Y(k)的離散傅里葉反變換得N 1N 11nk1*nky(n)k0 NY(k)WNk0 NY(k)WN(2)當x(n)長度很長時

3、，即N! N2，通常不允 許等x(n)全部采集齊后再進行卷積，否則使輸 出相對于輸入有較長的延時，另外，若N! N2 1太 大，h(n)要補上太多的零點，很不經(jīng)濟，且 FFT 的計算時間也要很長。為此，采用分段卷積的方 法，即把x(n)分成長度與h(n)相仿的一段段， 分別求出每段卷積的結(jié)果，然后用相應(yīng)的方式把它們結(jié)合起來，便是總的輸出。二、實驗內(nèi)容與要求給定兩x(n)=2,1,1,2,h(n)=1,-1,-1,1 在時域計算兩者的線性卷積；個序列。首先直接 其次用FFT快速計算二者的線性卷積，驗證結(jié)果數(shù)字濾波器的脈沖響應(yīng)為h(n)=(- 2)%(" ,N 2可自定，本實驗取 2=1

4、7輸入序列x(n)可選下列幾種情況： X( n)=RN,( n),N 1 可自取 16 x(n)=cos( j %(n) ,Ni=16N i X(n)=( 丁 Rni(n), N i=163實驗前，預(yù)先編制一個應(yīng)用FFT實現(xiàn)數(shù)字濾 波器的通用程序。上機獨立調(diào)試，并打印或記錄實驗結(jié)果。將實驗結(jié)果與預(yù)先筆算的結(jié)果比較，驗證其 正確性。三、實驗過程x=2,1,1,2;h=1 -1 -1 1;XK=fft(x,N);HK=fft(h,N);Y K=XK.*HK;yn=ifft( YK,N);if all(imag(x)=O)&(all(imag(h)=O)yn=real( yn);end y=

5、c on v(x,h); n=0:N-1; subplot(2,1,1); stem( n,y);ylabel('時域計算')； subplot(2,1,2); stem( n,y n,'.'); ylabel('FFT 快速');n=0:1:15; m=0:1:16; 2= le ngth( n); N2=le ngth(m); xn=on es(1,N1); hn=(-0.5).Am;N=N1+N2-1; XK=fft(x n,N);HK=fft(h n,N);Y K=XK.*HK;yn=ifft( YK,N);if all(imag(x n

6、)=0)&(all(imag(h n)=0) yn=real( yn);stem(x,y n,'.');n=0:1:15; m=0:1:16; N1=le ngth( n);N2=le ngth(m);xn=cos(2*pi* n/N1);hn=(-0.5).Am;N=N1+N2-1;XK=fft(x n,N);HK=fft(h n,N);Y K=XK.*HK;yn=ifft( YK,N);if all(imag(x n)=0)&(all(imag(h n)=0) yn=real( yn);endx=0:N-1;stem(x,y n,'.');n=0:1:15; m=0:1:16;2= le ngth( n);N2=le ngth(m); xn=(1/3)八 n; hn=(-0.5).Am; N=N1+N2-1; XK=fft(x n,N);r°'?05101520253035HK=fft(h n,N);Y K=XK.*HK;yn=ifft( YK,N);i