FFT算法實現(xiàn)實驗報告

FFT算法實現(xiàn)實驗報告 辛旸PB10210006實驗目的1、加深對快速傅里葉變換的理解。2、掌握FFT算法及其程序的編寫。3、掌握算法性能評測的方法。實驗內容1.編寫自己的FFT算法：代碼如下：function[X]=Sampling(x,N)%myFFT實現(xiàn)FFT時域取樣算法%輸出：生成FFT序列X(k),輸入：欲變換序列x（n），F(xiàn)FT變換長度N（可缺?。﹊f~exist('N','var');%檢查是否有變換長度N輸入N=length(x); %若無，則令N等于序列長度endifN<length(x); %如果N小于序列長度，則對序列進行截短x=x(:,1:N);elsex=[x,zeros(1,N-length(x))]; %如果N大于序列長度，對序列補零進行延長end;fori=1:1:length(x)/2+1; %判斷N是2的多少次方if2^i>=length(x); %若N不是2的整數(shù)冪N=2^i; %增大N為2的整數(shù)冪break;endendx=[x,zeros(1,N-length(x))]; %確保要變換的序列長度為2^ik1=zeros(1,N);X=zeros(1,N);w=zeros(1,N);form=0:1:N-1; %確定反序序列k1和正序序列k的關系k=m;forn=i-1:-1:0; %從高位開始依次將各位移至反序位k1(m+1)=k1(m+1)+fix(k/(2^n))*(2^(i-1-n));k=rem(k,2^n);end;endforl=1:1:N;X(k1(l)+1)=x(l); %生成反序序列w(l)=exp(-1i*2*pi/N*(l-1)); %生成旋轉因子endforl=0:1:i-1; %控制FFT運算級數(shù)form=1:1:N; %每一級中有N/2個蝶形運算ifrem((m-1),2^(l+1))<2^l; %找到蝶形運算的上半部分b=X(m)+X(m+2^l)*w(2^(i-1-l)*rem((m-1),2^l)+1); %將結果暫存至bX(m+2^l)=a(m)-X(m+2^l)*w(2^(i-1-l)*rem((m-1),2^l)+1); X(m)=b; %實現(xiàn)原位運算endendend2.選擇實驗1中的典型信號序列驗證算法的有效性： 為方便比較兩個算法，編寫了myCompare函數(shù)計算兩種算法的運行時間，并繪制頻譜曲線代碼如下：function[t1,t2,e]=myCompare(x,N)%myCompare函數(shù)：比較自己編寫的算法與系統(tǒng)自帶算法的差異%輸入：與變換信號序列x（n）和欲變換長度N%輸出：自己編寫的函數(shù)的執(zhí)行時間t1，系統(tǒng)自帶函數(shù)的執(zhí)行時間t2，兩者計算序列的差異平方和etic;X1=myFFT(x,N);t1=toc;tic;X2=fft(x,N);t2=toc;subplot(1,2,1);plot(abs(X1));xlabel('k');ylabel('X(k');title('ó?×??o±àD′μ?oˉêyμ?μ?μ?±???DòáD?μ?×');subplot(1,2,2);plot(abs(X2));xlabel('k');ylabel('X(k');title('?μí3×?′?FFToˉêyμ?μ?μ?±???DòáD?μ?×');e=sum((X1-X2).^2);end對理想采樣信號A=444.128，α=50*2^(1/2)*π，Ω=50*2^(1/2)*π，T=1/1000，序列長度50，用自己編寫的FFT算法和系統(tǒng)自帶算法做64點FFT變換后繪制頻域序列，如下：對高斯序列，p=8，q=8，序列長度16，用自己編寫的FFT算法和系統(tǒng)自帶算法做16點FFT變換后繪制頻域序列，如下：對衰減正弦序列α=0.01，f=0.05，序列長度100，用自己編寫的FFT算法和系統(tǒng)自帶算法做128點FFT變換后繪制頻域序列，如下：由以上結果可知，自己編寫的算法運行結果與系統(tǒng)自帶算法一致，且可以對信號進行截斷或補零后再做變換。3.對所編制FFT算法進行性能評估：與自己編寫的DFT算法進行性能比較： 對N點序列進行DFT變換需要N2/2次復乘，而對N點序列做基2-FFT只需N/2*log2（N）次復乘，因此運算量減少了很多，且隨著序列長度增加，運算量差異變大。與系統(tǒng)自帶FFT算法進行性能比較：由于系統(tǒng)自帶FFT函數(shù)用C語言實現(xiàn)，無法查看源代碼，只知道效率更高，而且在計算任意點的DFT（不指定變換長度N）時，系統(tǒng)自帶函數(shù)無需采取補零操作，而自己編寫的函數(shù)會先補零再變換，改變了頻域取樣密度，會得到與系統(tǒng)自帶函數(shù)不同的結果。比較自己編寫的DFT算法、自己編寫的FFT算法和系統(tǒng)自帶算法三者運算時間，得到下表：序列myFFTmyDFTfft高斯序列（16點，p=8，q=8）0.0007200.0001970.000014理想采樣序列（64點，參數(shù)同上步）0.0045940.0095670.000047衰減正弦序列（256點，α=0.001，f=0.05）0.0324290.0101270.000054矩形序列（1024點）0.3304530.0326890.018449三角序列（4096點）5.1095390.1104720.039220隨機序列（16384點）溢出0.3777730.086823由此繪制曲線如圖：由比較結果可知，雖然運算時間曲線和理想曲線不完全相同，但三種算法的相對運算時間與理論預期一致。實驗總結及個人結論： 從對實驗的比較結果中可知，自己編寫的FFT算法有效且比自己編寫的DFT算法快很多，但卻始終比系