數(shù)字信號處理實驗報告-實驗1 基2-FFT算法實現(xiàn)

數(shù)字信號處理實驗數(shù)字信號處理實驗（基于MATLAB語言）實驗1基2-FFT算法實現(xiàn)實驗目的掌握基2-FFT的原理及具體實現(xiàn)方法。編程實現(xiàn)基2-FFT算法。加深理解FFT算法的特點。實驗設(shè)備與環(huán)境計算機、MATLAB軟件環(huán)境。實驗基礎(chǔ)理論FFT是DFT的一種快速算法，能使DFT的計算大大簡化，運算時間縮短。FFT利用了WNnkFFT算法基本上可以分為兩大類，即按時間抽取法和按頻率抽取法。在實現(xiàn)FFT算法時，要重點考慮兩個問題，注意數(shù)據(jù)的讀取和存儲：（1）輸入輸出的排序；（2）碟形運算的實現(xiàn)。按時間抽取算法中輸入反序輸出順序，按頻率抽取算法中輸入順序輸出反序；運算過程中的每一級都由N/2個碟形運算構(gòu)成，每一個碟形運算單元中，兩個節(jié)點變量運算后得到的結(jié)果為下一列相同位置的節(jié)點變量，而和其他節(jié)點變量無關(guān)，可以采用原位運算，節(jié)省存儲單元。另外，碟形運算中的復系數(shù)WNMATLAB中提供了用于計算FFT的函數(shù)fft，可將實驗中所得到的結(jié)果與利用MATLAB中fft函數(shù)計算的結(jié)果相比較，以此驗證結(jié)果的正確性。圖1-1N=8按時間抽取的基-2FFT運算流圖圖1-2N=8按頻率抽取的基-2FFT運算流圖實驗內(nèi)容1.編程實現(xiàn)序列長度為N=8的按時間抽取的基2-FFT算法。給定一個8點序列，采用編寫的程序計算其DFT，并與MATLAB中fft函數(shù)計算的結(jié)果相比較，以驗證結(jié)果的正確性。實驗過程與實驗結(jié)果：設(shè)序列為{0,1,2,3,4,5,6,7}編程實現(xiàn)序列長度為N=8的按時間抽取的基2-FFT算法%輸入數(shù)據(jù)并計算常量xn=[0,1,2,3,4,5,6,7];M=nextpow2(length(xn)),N=2^M,form=0:N/2-1;WN(m+1)=exp(-j*2*pi/N)^m;endA=[xn,zeros(1,N-length(xn))];%數(shù)據(jù)倒序操作J=0;forI=0:N-1;ifI<J;T=A(I+1);A(I+1)=A(J+1);A(J+1)=T;endK=N/2;whileJ>=K;J=J-K;K=K/2;endJ=J+K;end%分級按序依次進行蝶形運算forL=1:M;B=2^(L-1);forR=0:B-1;P=2^(M-L)*R;forK=R:2^L:N-2;T=A(K+1)+A(K+B+1)*WN(P+1);A(K+B+1)=A(K+1)-A(K+B+1)*WN(P+1);A(K+1)=T;endendendXk=A運行結(jié)果為：Xk=Columns1through528.0000-4.0000+9.6569i-4.0000+4.0000i-4.0000+1.6569i-4.0000Columns6through8-4.0000-1.6569i-4.0000-4.0000i-4.0000-9.6569i②調(diào)用函數(shù)fft計算：>>fftxn=fft(xn,N)運行結(jié)果為：fftxn=Columns1through528.0000-4.0000+9.6569i-4.0000+4.0000i-4.0000+1.6569i-4.0000Columns6through8-4.0000-1.6569i-4.0000-4.0000i-4.0000-9.6569i實驗結(jié)果分析：兩種計算方法結(jié)果一樣，結(jié)果正確。2.編程實現(xiàn)序列長度為N=8的按頻率抽取的基2-FFT算法。給定一個8點序列，采用編寫的程序計算其DFT，并與MATLAB中fft函數(shù)計算的結(jié)果相比較，以驗證結(jié)果的正確性。實驗過程與實驗結(jié)果：設(shè)序列為{7,6,5,4,3,2,1,0}編程實現(xiàn)序列長度為N=8的按頻率抽取的基2-FFT算法xn=[7,6,5,4,3,2,1,0];N=8;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;endendendn1=fliplr(dec2bin([0:N-1]));n2=[bin2dec(n1)];fori=1:NXk(i)=xn(n2(i)+1);endXk運行結(jié)果為：Xk=Columns1through528.00004.0000-9.6569i4.0000-4.0000i4.0000-1.6569i4.0000Columns6through84.0000+1.6569i4.0000+4.0000i4.0000+9.6569i調(diào)用函數(shù)fft計算：>>fftxn=fft(xn,N)運行結(jié)果為：fftxn=Columns1through528.00004.0000-9.6569i4.0000-4.0000i4.0000-1.6569i4.0000Columns6through84.0000+1.6569i4.0000+4.0000i4.0000+9.6569i實驗結(jié)果分析：兩種計算方法結(jié)果一樣，結(jié)果正確。3.將上述FFT程序推廣到序列長度為N=2v的情況，要求利用原位運算。實驗過程與實驗結(jié)果：按時間抽?。簒n=[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15];M=nextpow2(length(xn));N=2^M;form=0:N/2-1WN(m+1)=exp(-j*2*pi/N)^m;endDF1=[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;endK=N/2;whileH>=K;H=H-K;K=K/2;endH=H+K;endforG=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;endendendDF1運行結(jié)果為：DF1=1.0e+02*Columns1through51.2000-0.0800+0.4022i-0.0800+0.1931i-0.0800+0.1197i-0.0800+0.0800iColumns6through10-0.0800+0.0535i-0.0800+0.0331i-0.0800+0.0159i-0.0800-0.0800-0.0159iColumns11through15-0.0800-0.0331i-0.0800-0.0535i-0.0800-0.0800i-0.0800-0.1197i-0.0800-0.1931iColumn16-0.0800-0.4022i按頻率抽取：xn=[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15];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;endendendn1=fliplr(dec2bin([0:N-1]));n2=[bin2dec(n1)];fori=1:NXk(i)=xn(n2(i)+1);endXk運行結(jié)果為：Xk=1.0e+02*Columns1through51.2000-0.0800+0.4022i-0.0800+0.1931i-0.0800+0.1197i-0.0800+0.0800iColumns6through10-0.0800+0.0535i-0.0800+0.0331i-0.0800+0.0159i-0.0800-0.0800-0.0159iColumns