實(shí)驗(yàn)3利用FFT計(jì)算線性卷積

實(shí)驗(yàn)3利用FFT計(jì)算線性卷積一、實(shí)驗(yàn)?zāi)康?.掌握利用FFT計(jì)算線性卷積的原理及具體實(shí)現(xiàn)方法。2.加深理解重疊相加法和重疊保留法。3.考察利用FFT計(jì)算線性卷積各種方法的適用圍。的長度為L+M-1的長度為L+M-1。計(jì)算機(jī)、matlab軟件環(huán)境。三、實(shí)驗(yàn)基礎(chǔ)理論1.線型卷積和圓周卷積設(shè)x(n)為L點(diǎn)序列，h(n)為M點(diǎn)序列，x(n)和h(n)的線性卷積為x(n)和h(n)的N點(diǎn)圓周卷積為圓周卷積與線性卷積相等而不產(chǎn)生交疊的必要條件為圓周卷積定理：根據(jù)DFT的性質(zhì)，x(n)和h(n)的N點(diǎn)圓周卷積的DFT等于它們DFT的乘積2.快速卷積快速卷積算法用圓周卷積實(shí)現(xiàn)線性卷積，根據(jù)圓周卷積定理利用FFT算法實(shí)現(xiàn)圓周卷積。可以將快速卷積的步驟歸納如下：(1)為了使線性卷積可以用圓周卷積來計(jì)算，必須選擇 ;同時(shí)為了能使用基-2FFT完成卷積運(yùn)算，要求 。采用補(bǔ)零的辦法使x(n)和h(n)的長度均為N。(2)計(jì)算x(n)和h(n)的N點(diǎn)FFT(3)組成乘積(4)利用IFFT計(jì)算Y(K)的IDFT，得到線性卷積y(n)3.分段卷積我們考察單位取樣響應(yīng)為h(n)的線性系統(tǒng)，輸入為x(n),輸出為y(n)，則當(dāng)輸入序列x(n)極長時(shí)，如果要等x(n)全部集齊時(shí)再開始進(jìn)行卷積，會(huì)使輸出相對(duì)輸入有較大的延時(shí)，再者如果序列太長，需要大量存貯單元。為此我們把x(n)分段，分別求出每段的卷積，合在一起得到最后總的輸出。這種方法稱為分段卷積分段卷積可細(xì)分為重疊保留法和重疊相加法。長度，則第i段(n長度，則第i段(n)()的數(shù)據(jù)為M-1個(gè)零。計(jì)算每一段與h(n)的圓周卷積，則其每段卷積結(jié)果的前M-1個(gè)樣本不等于線性卷積值，不是正確的樣本值。所以我們將每段卷積結(jié)果的前M-1個(gè)樣本社區(qū)，只保留后面的N-M+1個(gè)正確輸出樣本，把這些輸出樣本合起來，得到總輸出。利用FFT實(shí)現(xiàn)重疊保留發(fā)的步驟如下：在x(n)前面填充M-1個(gè)零，擴(kuò)大以后的序列為將x(n)分為若干N點(diǎn)子段，設(shè)L=N-M+1為每一段的有效數(shù)據(jù)計(jì)算每一段與h(n)的N點(diǎn)圓周卷積，利用FFT計(jì)算圓周卷積：舍去每一段卷積結(jié)果的前M-1個(gè)樣本，連接剩下樣本，得到卷積結(jié)果y(n)。重疊相加法：設(shè)h(n)長度為M，將信號(hào)x(n)分解成長為L的子段，建議L選擇與的M數(shù)量級(jí)相同，以(n)表示沒每段信號(hào)，則每一段卷積 的長度為L+M-1,所以在做求和時(shí)，相鄰兩段序列有M-1個(gè)樣本重疊，即前一段的最后M-1個(gè)樣本喝下一段的前M-1個(gè)序列重疊，這個(gè)重疊部分相加，再與不重疊部分共同組成輸出y(n)。利用FFT實(shí)現(xiàn)重疊保留法的步驟如下：(2)計(jì)算每一段與h(n)的卷積，根據(jù)快速卷積算法利用FFT計(jì)算卷積。四、實(shí)驗(yàn)容(1)將x(n)分為若干(1)將x(n)分為若干L點(diǎn)子段(n)。(3)將各段相加，得到輸出y(n)h(n)=cos(0.2n),0<=n<=M的線性卷積，完成以下實(shí)驗(yàn)容1.設(shè)L=M，根據(jù)線性卷積的表達(dá)式和快速卷積的原理，分別編程實(shí)現(xiàn)計(jì)算兩個(gè)序列線性卷積的方法，比較當(dāng)序列長度分別為8,16,32,64,256,512,1024時(shí)，兩種方法計(jì)算線性卷積所需時(shí)間。實(shí)驗(yàn)代碼及結(jié)果：程序Exp3_1代碼L=input('L=');M=input('M=');xn=linspace(1,1,L);hn=cos(0.2*pi*[0:M-1]);yn1=zeros(1,L+M-1);ticfork=0:L+M-1forn=max([0k-M+1]):min([kL-1])yn1(k+1)=yn1(k+1)+xn(n+1)*hn(k-n+1);endendtocticXk=fft(xn,L+M-1);Hk=fft(hn,L+M-1);Yk=Xk.*Hk;yn2=ifft(Yk);toc>>Exp3_1L=8M=8Elapsedtimeis0.000136seconds.Elapsedtimeis0.000033seconds.>>Exp3_1L=16M=16Elapsedtimeis0.000205seconds.Elapsedtimeis0.000030seconds.>>Exp3_1L=32M=32Elapsedtimeis0.000419seconds.Elapsedtimeis0.000056seconds.>>Exp3_1L=64M=64Elapsedtimeis0.000911seconds.Elapsedtimeis0.000117seconds.>>Exp3_1L=256M=256Elapsedtimeis0.005773seconds.Elapsedtimeis0.000261seconds.>>Exp3_1L=512M=512Elapsedtimeis0.017060seconds.Elapsedtimeis0.000190seconds.>>Exp3_1L=1024M=1024Elapsedtimeis0.055688seconds.Elapsedtimeis0.000524seconds.由此可見，線性卷積慢得多2.當(dāng)L=2048且M=256時(shí)，比較直接計(jì)算線性卷積和快速卷積所需時(shí)間，進(jìn)一步考察當(dāng)L=4096且M=256時(shí)兩種算法所需的時(shí)間。實(shí)驗(yàn)代碼及結(jié)果：>>Exp3_1L=2048M=256Elapsedtimeis0.035421seconds.Elapsedtimeis0.000448seconds.由此可見，快速卷積快>>Exp3_1L=4096M=256Elapsedtimeis0.069497seconds.Elapsedtimeis0.001463seconds.由此可見，快速卷積快3.編程實(shí)現(xiàn)利用重疊相加法計(jì)算兩個(gè)序列的線性卷積，考察L=2048且M=256時(shí)計(jì)算線性卷積的時(shí)間，與第二題的結(jié)果進(jìn)行比較。實(shí)驗(yàn)代碼及結(jié)果：程序Exp3_3代碼L=input('L=');M=input('M=');xn=linspace(1,1,L);hn=cos(0.2*pi*[0:M-1]);ticXk=fft(xn,L+M-1);Hk=fft(hn,L+M-1);Yk=Xk.*Hk;yn2=ifft(Yk);tocyn=[];ticx1n=[linspace(0,0,M-1)xn];Hk=fft(hn,2*M);iend=floor(length(x1n)/(M+1))+1;fori=0:iendxin=x1n(i*(M+1)+1:min([length(x1n)i*(M+1)+2*M]));Xik=fft(xin,2*M);Yik=Xik.*Hk;yin=ifft(Yik);yn=[ynyin(M:2*M)];endyn=yn(1:L+M-1);toc>>Exp3_3L=2048M=256Elapsedtimeis0.000340seconds.Elapsedtimeis0.000513seconds.>>Exp3_3L=8192M=256Elapsedtimeis0.003971seconds.Elapsedtimeis0.002105seconds.分析：當(dāng)L=2048M=256 時(shí)，重疊相加比較慢，原因是程序控制流耗時(shí)較多。但是，隨著序列L的增長，重疊相加變得較快4.編程實(shí)現(xiàn)利用重疊保留法計(jì)算兩個(gè)序列的線性卷積，考察L=2048且M=256時(shí)計(jì)算線性卷積的時(shí)間，與第二題的結(jié)果進(jìn)行比較。實(shí)驗(yàn)代碼及結(jié)果：程序Exp3_4代碼L=input('L=');M=input('M=');xn=linspace(1,1,L);hn=cos(0.2*pi*[0:M-1]);ticXk=fft(xn,L+M-1);Hk=fft(hn,L+M-1);Yk=Xk.*Hk;yn2=ifft(Yk);toc%?±?ó?????í?yticHk=fft(hn,2*M-1);iend=floor(length(xn)/M);i=0;xin=xn(i*M+1:min([(i+1)*Mlength(xn)]));Xik=fft(xin,2*M-1);Yik=Xik.*Hk;yin=ifft(Yik);yn=yin;%μúò?′?????fori=1:iendxin=xn(i*M+1:min([(i+1)*Mlength(xn)]));Xik=fft(xin,2*M-1);Yik=Xik.*Hk;yin=ifft(Yik);yn=[yn(1:(length(yn)-M+1))yn((length(yn)-(M-2)):length(yn))+yin(1:M-1)yin(M:2*M-1)];%?′?óDòáDendyn=yn(1:L+M-1);toc>>Exp3_4L=2048M=256Elapsedtimeis0.000441seconds.Elapsedtimeis0.001055seconds.>>Exp3_4L=32768M=1024Elapsedtimeis0.018384seconds.Elapsedtimeis0.016179seconds.分析：當(dāng)L=2048M=256