實驗1基2-FFT算法實現一、實驗目的1.掌握基2-FFT的原理及具體實現方法。2.編程實現基2-FFT算法。3.深刻理解FFT算法的特點。二、實驗基礎理論FFT是DFT的一種快速算法，能使DFT的計算大大簡化，運算時間縮短。FFT利用了的三個固有特性。即對稱性，周期性和可約性，將長序列的DFT分解為短序列的DFT，合并了DFT運算中的某些項，從而減少了DFT的運算量。FFT算法基本上可分為兩大類，即按時間抽取法和按頻率抽取法。N=8按照時間抽取的基2-FFT運算流圖和N=8按照頻率抽取的基2-FFT運算流圖如下圖。N=8按照時間抽取的基2-FFT運算流圖N=8按照頻率抽取的基2-FFT運算流圖在實現FFT算法時，要重點考慮兩個問題，注意數據的讀取和存儲：(1)輸入輸出的排序；（2）蝶形運算的實現。按時間抽取算法中輸入反序輸出順序，按頻率抽取算法中輸入順序輸出反序；運算過程中的每一級都有N/2個蝶形運算構成，每一個蝶形運算單元中，兩個節點變量運算后得到的結果為下一列相同位置的節點變量，而和其他節點變量無關，可以采用原位運算，節省存儲單元。另外，蝶形運算中的復系數可以存儲為能及時查閱的系數表，這樣可以借閱運算量，但是需要N/2個復數存儲器。MATLAB中提供了用于計算FFT的函數fft，可將實驗中所得到的結果與利用MATLAB中fft函數計算的結果相比較，以此驗證結果的正確性。三、實驗內容及實驗過程1.編程實現序列長度為N=8的按時間抽取的基2-FFT算法。給定一個8點序列，采用編寫的程序計算其DFT，并與MATLAB中fft函數計算的結果相比較，以驗證結果的正確性。①8點按照時間抽取的FFT程序代碼：clear;clc;n=input('N=');v=log2(n);a=[0:0.1:(n-1)*0.1];x=sin(a);xd=bin2dec(fliplr(dec2bin([1:n]-1,v)))+1;y=x(xd);form=1:vnz=2^m;u=1;wn=exp(-2j*pi/nz);forj=1:(nz/2)fork=j:nz:nkp=k+nz/2;t=y(kp)*u;y(kp)=y(k)-t;y(k)=y(k)+t;endu=u*wn;endendfigure(1);subplot(211);stem(a,abs(y));xlabel('x');title('abs:time:dft->fft');subplot(212);prove=fft(x);stem(a,abs(prove));xlabel('x');title('abs:fft');figure(2);subplot(211);stem(a,angle(y));xlabel('x');title('angle:time:dft->fft');subplot(212);stem(a,angle(prove));xlabel('x');title('angle:fft');實驗結果：N=82.編程實現序列長度為N=8的按頻率抽取的基2-FFT算法。給定一個8點序列，采用編寫的程序計算其DFT，并與MATLAB中fft函數計算的結果相比較，以驗證結果的正確性。②8點按照頻率抽取的FFT程序代碼：clear;clc;n=input('N=');v=log2(n);a=[0:0.1:(n-1)*0.1];x=sin(a);prove=fft(x);form=1:vnz=2^(v+1-m);u=1;wn=exp(-2j*pi/nz);forj=1:(nz/2)fork=j:nz:nkp=k+nz/2;t=x(k)+x(kp);x(kp)=(x(k)-x(kp))*u;x(k)=t;endu=u*wn;endendxd=bin2dec(fliplr(dec2bin([1:n]-1,v)))+1;y=x(xd);figure(1);subplot(211);stem(a,abs(y));xlabel('x');title('abs:frequency:dft->fft');subplot(212);stem(a,abs(prove));xlabel('x');title('abs:fft');figure(2);subplot(211);stem(a,angle(y));xlabel('x');title('angle:frequency:dft->fft');subplot(212);stem(a,angle(prove));xlabel('x');title('angle:fft');實驗結果：N=83.將上述FFT程序推廣大序列長度為N=2v的情況，要求利用原位運算。③的按照時間抽取的FFT實驗代碼：與①代碼相同。N=1024實驗結果：③按照頻率抽取的FFT實驗代碼：與②相同N=1024實驗結果：四、實驗心得對于整個實驗是利用快速算法實現DFT——FFT。對于FFT的兩種算法的MATLAB實現。對于基2-FFT按照時間抽取和基2-FFT按照頻率抽取這兩種方法是我們理論學習中的重點，也是我們必須掌握和熟練計算和畫出8點和16點的結果和蝶形運算圖。所以對于這個實驗，首先在理論上沒有什么難度，都能很好的理解整個運算過程。真正的難點是怎么通過MATLAB來實現這一個功能。對于整個設計過程中，我們先分析這個蝶形運算中的純數學關系，得到了一個數學上的各個變量的關系，這樣我們就可以進行相關的程序設計了。對于旋轉因子、相同旋轉因子的間隔、兩個運算關系之間的間隔，我們得到他們與級數的關系。這樣就順利的解決了多層循環之間的關系，那么我們的運算程序也就出來了。將運算流圖轉成程序思想這是一個困難之處，當解決了這個問題的時候，自然整個問題也解決了。對于基2-FFT算法的實現，使得我掌握FFT兩種算法的數字信號處理的理論知識。能夠熟練的計算出8點和16點的DFT，并且能夠正確的畫出他們關于基2-FFT按照時間抽取和基2-FF