數(shù)字信號處理實驗實驗1基2-FFT算法實現(xiàn)實驗目的掌握基2-FFT的原理及具體實現(xiàn)方法。編程實現(xiàn)基2-FFT算法。加深理解FFT算法的特點。實驗設備與環(huán)境計算機、MATLAB軟件環(huán)境。實驗基礎理論FFT是DFT的一種快速算法，能使DFT的計算大大簡化，運算時間縮短。FFT利用了WNnk的三個固有特性，即對稱性、周期性和可約性，將長序列的DFT分解為短序列的DFT，合并了DFT運算中的某些項，從而減少了FFT算法基本上可以分為兩大類，即按時間抽取法和按頻率抽取法。在實現(xiàn)FFT算法時，要重點考慮兩個問題，注意數(shù)據(jù)的讀取和存儲：（1）輸入輸出的排序；（2）碟形運算的實現(xiàn)。按時間抽取算法中輸入反序輸出順序，按頻率抽取算法中輸入順序輸出反序；運算過程中的每一級都由N/2個碟形運算構(gòu)成，每一個碟形運算單元中，兩個節(jié)點變量運算后得到的結(jié)果為下一列相同位置的節(jié)點變量，而和其他節(jié)點變量無關(guān)，可以采用原位運算，節(jié)省存儲單元。另外，碟形運算中的復系數(shù)WNnk可以存儲為能及時查閱的系數(shù)表，這樣可以節(jié)約計算量，但是需要MATLAB中提供了用于計算FFT的函數(shù)fft，可將實驗中所得到的結(jié)果與利用MATLAB中fft函數(shù)計算的結(jié)果相比較，以此驗證結(jié)果的正確性。實驗內(nèi)容1.編程實現(xiàn)序列長度為N=8的按時間抽取的基2-FFT算法。給定一個8點序列，采用編寫的程序計算其DFT，并與MATLAB中fft函數(shù)計算的結(jié)果相比較，以驗證結(jié)果的正確性。2.編程實現(xiàn)序列長度為N=8的按頻率抽取的基2-FFT算法。給定一個8點序列，采用編寫的程序計算其DFT，并與MATLAB中fft函數(shù)計算的結(jié)果相比較，以驗證結(jié)果的正確性。3.將上述FFT程序推廣到序列長度為N=2v的情況，要求利用原位運算。實驗代碼及分析實驗代碼：>>x=[1+2j0.5+3j5+4j-2+3j6-3j5+1j9-1-2j];>>n=bin2dec(fliplr((dec2bin([1:8]-1,3))))+1;>>x0=x;>>forl=1:3 form=1:2^(l-1) fork=1:2^(3-l) t=x0(k+(m-1)*2^(4-l)+2^(3-l));x0(k+(m-1)*2^(4-l)+2^(3-l))=(x0(k+(m-1)*2^(4-l))-t)*exp(-2*1j*pi*(k-1)/(8/2^(l-1))); x0(k+(m-1)*2^(4-l))=x0(k+(m-1)*2^(4-l))+t; end endend>>y1=fft(x)>>fori=1:8 y0(i)=x0(n(i));end>>y0y1=Columns1through523.5000+8.0000i1.4749+10.7678i-4.0000-13.5000i-1.5754+7.0104i18.5000-2.0000iColumns6through8-3.4749+7.2322i-10.0000+3.5000i-16.4246-5.0104iy0=Columns1through523.5000+8.0000i1.4749+10.7678i-4.0000-13.5000i-1.5754+7.0104i18.5000-2.0000iColumns6through8-3.4749+7.2322i-10.0000+3.5000i-16.4246-5.0104i分析：y0和y1兩者結(jié)果完全相同，說明結(jié)果正確。實驗代碼：>>x=[1+2j0.5+3j5+4j-2+3j6-3j5+1j9-1-2j];>>n=bin2dec(fliplr((dec2bin([1:8]-1,3))))+1;>>x0=x;>>forl=1:3 form=1:2^(l-1) fork=1:2^(3-l) t=x0(k+(m-1)*2^(4-l)+2^(3-l));x0(k+(m-1)*2^(4-l)+2^(3-l))=(x0(k+(m-1)*2^(4-l))-t)*exp(-2*1j*pi*(k-1)/(8/2^(l-1))); x0(k+(m-1)*2^(4-l))=x0(k+(m-1)*2^(4-l))+t; end endend>>y1=fft(x)>>fori=1:8 y0(i)=x0(n(i));end>>y0y1=Columns1through523.5000+8.0000i1.4749+10.7678i-4.0000-13.5000i-1.5754+7.0104i18.5000-2.0000iColumns6through8-3.4749+7.2322i-10.0000+3.5000i-16.4246-5.0104iy0=Columns1through523.5000+8.0000i1.4749+10.7678i-4.0000-13.5000i-1.5754+7.0104i18.5000-2.0000iColumns6through8-3.4749+7.2322i-10.0000+3.5000i-16.4246-5.0104i分析：兩種算法的結(jié)果相同，說明結(jié)果相同。實驗代碼：（1）按時間抽取>>xn=[1,4,7,5,9,2,3,8,6,5,2,7,6,4,13,2];>>M=nextpow2(length(xn));>>N=2^M;>>form=0:N/2-1WN(m+1)=exp(-j*2*pi/N)^m;end>>DF1=[xn,zeros(1,N-length(xn))];>>H=0;>>forI=0:N-1;ifI<H;T=DF1(I+1);DF1(I+1)=DF1(H+1);DF1(H+1)=T;end>>K=N/2;>>whileH>=K;H=H-K;K=K/2;end>>H=H+K;end>>forG=1:M;F=2^(G-1);forS=0:F-1;P=2^(M-G)*S;forK=S:2^G:N-2;T=DF1(K+1)+DF1(K+F+1)*WN(P+1);DF1(K+F+1)=DF1(K+1)-DF1(K+F+1)*WN(P+1);DF1(K+1)=T;endendend>>DF1DF1=Columns1through1084.0000-5.0057-7.8833-5.0141-3.0131-5.2100-7.9867-5.006010.0000-4.5526Columns11through16-8.1429-4.9962-2.9869-5.2093-7.9872-5.0060>>F1=fft(xn)F1=Columns1through1084.0000-5.0057-7.8833-5.0141-3.0131-5.2100-7.9867-5.006010.0000-4.5526Columns11through16-8.1429-4.9962-2.9869-5.2093-7.9872-5.0060（2）按頻率抽取>>xn=[1,4,7,5,9,2,3,8,6,5,2,7,6,4,13,2];>>M=nextpow2(length(xn));>>N=2^M;>>M=log2(N);>>fork1=0:M-1D=2^k1;E=N/2^k1;F=N/2^(k1+1);G=N/2^(k1+1)-1;Wn=exp(-j*2*pi/E);forg=1:DH1=(g-1)*E;H2=(g-1)*E+F;forr=0:G;k=r+1;xn(k+H1)=xn(k+H1)+xn(k+H2);xn(k+H2)=[xn(k+H1)-xn(k+H2)-xn(k+H2)]*Wn^r;endendend>>n1=fliplr(dec2bin([0:N-1]));>>n2=[bin2dec(n1)];>>fori=1:NXk(i)=xn(n2(i)+1);end>>XkXk=Columns1through1084.0000-5.0057-7.8833-5.0141-3.0131-5.2100-7.9867-5.006010.0000-4.5526Columns11through16-8.1429-4.9962-2.9869-5.2093-7.9872-5.0060>>F2=fft(xn)F2=Columns1through1084.0000-5.0057-7.8833-5.0141-3.0131-5.2100-7.9867-5.006010.0000-4.5526Columns11throug