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

1、無(wú) 一、實(shí)驗(yà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)稱(chēng) IFFT）還原為時(shí)域序列，即得到輸出 y(n)。 現(xiàn)以FFT求有限長(zhǎng)序列間的卷積及求有限長(zhǎng)度序列與較長(zhǎng)序列間的卷積為例來(lái)討論FFT的快速卷積方法。 （1）序列x(n)和h(n)的長(zhǎng)差不多。設(shè)x(n)的長(zhǎng)為 N1，h(n)的長(zhǎng)為N2，要求 10)()()()()(Nm

2、mnxmhnynxny 用 FFT 完成這一卷積的具體步驟如下： 為使兩有限長(zhǎng)序列的線性卷積可用其循環(huán)卷積代替而不發(fā)生混疊，必須選擇循環(huán)卷積長(zhǎng)度121NNN，若采用基 2-FFT 完成卷積運(yùn)算，要求mN2（m為整數(shù)） 。 用補(bǔ)零方法使 x(n)和h(n)變成列長(zhǎng)為 N 的序列。 1010)()(11NnNNnnxnx 1010)()(22NnNNnnhnh 用 FFT 計(jì)算 x(n)和h(n)的 N 點(diǎn)離散傅里葉變換 完成 X(k)和 H(k)乘積，)()()(kHkXkY 用 FFT 計(jì)算 Y(k)的離散傅里葉反變換得 *10*10)(1)(1)(NknkNnkNNkWkYNWkYNny （

3、2）當(dāng) x(n)長(zhǎng)度很長(zhǎng)時(shí)，即21NN ，通常不允許等 x(n)全部采集齊后再進(jìn)行卷積，否則使輸出相對(duì)于輸入有較長(zhǎng)的延時(shí)，另外，若121 NN太大，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)，便是總的輸出。 無(wú) 二、實(shí)驗(yàn)內(nè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é)果。 數(shù)字濾波器的脈沖響應(yīng)為 h(n)=(-

4、),()212nRNn ,N 可自定，本實(shí)驗(yàn)取 N =17 輸入序列 x(n)可選下列幾種情況： X(n)=R(n),N 可自取 16 x(n)=cos()()211nRnNN,N =16 X(n)=(n)31 R(n), N =16 實(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ò)程三、實(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)=0)&a

5、mp;(all(imag(h)=0) yn=real(yn); end y=conv(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 快速); 無(wú) 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); if all(imag(

6、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); 無(wú) 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); if all(imag(xn)=0)&(all(imag(hn)=0) yn=real(yn); end x=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); 無(wú) HK=fft(hn,N); YK=XK