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

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

2、0用FFT完成這一卷積的具體步驟如下: 為使兩有限長(zhǎng)序列的線性卷積可用其循環(huán)卷積代替而不發(fā)生混疊，必須選擇循環(huán)卷積長(zhǎng)度N _ N,N2 -1，若采用基2-FFT完成卷積運(yùn)算，要求 N =2m ( m為整數(shù))。 用補(bǔ)零方法使x(n)和h(n)變成列長(zhǎng)為N的序列。x(n)0 蘭 n 蘭 N, 1x( n)=丿i 0 N,蘭 n 蘭 N 1h(n) 0 蘭 n 蘭 N2 _1h(n)=丿0 N2 蘭 n 蘭 N 1 用FFT計(jì)算x(n)和h(n)的N點(diǎn)離散傅里葉變換 完成 X(k)和 H(k)乘積，丫(k) = X (k)H (k) 用FFT計(jì)算Y(k)的離散傅里葉反變換得N Ay(n)k =9(2

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

4、，本實(shí)驗(yàn)取 N2 =172 2輸入序列x(n)可選下列幾種情況： X( n)=RNl( n),N 1 可自取 162 x( n)=cos(n)RN1 (門)，2=16N11 X(n )=()n Rn1 (n), N 1=163實(shí)驗(yàn)前，預(yù)先編制一個(gè)應(yīng)用FFT實(shí)現(xiàn)數(shù)字濾波器的通用程序。上機(jī)獨(dú)立調(diào)試，并打印或記錄實(shí)驗(yàn)結(jié)果。將實(shí)驗(yàn)結(jié)果與預(yù)先筆算的結(jié)果比較，驗(yàn)證其正確性。三、實(shí)驗(yàn)過(guò)程x=2,1,1,2;h=1 -1 -1 1;XK=fft(x,N);HK=fft(h,N);YK=XK.*HK;yn=ifft(YK,N);if all(imag(x)=O)&(all(imag(h)=O) yn=r

5、eal( yn);endy=c on v(x,h);n=0:N-1;subplot(2,1,1);stem( n, y);ylabel('時(shí)域計(jì)算'); subplot(2,1,2);stem( n,yn,'.');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)4m;N=N1+N2-1;XK=fft(x n, N);HK=fft(h n, N);YK=XK.*HK;yn=ifft(YK,N);if all(imag(

6、x n)=0)&(all(imag(h n)=0) yn=real( yn);stem(x,y n,'.');n=0:1:15; m=0:1:16; 2= le ngth( n); N2=le ngth(m); xn=cos(2*pi* n/N1);hn=(-0.5)4m;N=N1+N2-1;XK=fft(x n, N);HK=fft(h n, N);YK=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).A n; hn=(-0.5)皿； N=N1+N2-1; XK=fft(x n, N);HK=fft(h n, N);YK=XK.*HK;yn=