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

1、利用FFT實(shí)現(xiàn)快速卷積一、實(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)為N2，要求N 1y(n) x(n) y(n)h(m)x (n

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

3、，即N! N2，通常不允 許等x(n)全部采集齊后再進(jìn)行卷積，否則使輸 出相對(duì)于輸入有較長(zhǎng)的延時(shí)，另外，若N! N2 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)容與要求給定兩x(n)=2,1,1,2,h(n)=1,-1,-1,1 在時(shí)域計(jì)算兩者的線性卷積；個(gè)序列。首先直接 其次用FFT快速計(jì)算二者的線性卷積，驗(yàn)證結(jié)果數(shù)字濾波器的脈沖響應(yīng)為h(n)=(- 2)%(" ,N 2可自定，本實(shí)驗(yàn)取 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實(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);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('時(shí)域計(jì)算')； 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