1、讓京杭變麻天丈名快速傅里葉變換的研究姓名：汪寅鵬2017年4月30日。摘要O-Abstract(English)1.引言2分析3總結4致謝5參考資料目錄0-摘要快速傅里葉變換(FastFourierTransform),即利用計算機計算離散傅里葉變換(DFT)的高效、快速計算方法的統稱，簡稱FFT。本文主要研究信號幾2*11與信號y=1000sin,-300<x<300,的快速傅里葉變換及其逆變換的相關規律，并給出復雜度的相關計算。關鍵詞：快速傅里葉變換0-Abstract(English)FastFouriertransform(FFT)algorithmcomputesthed

2、iscreteFouriertransform(DFT)ofasequence.ThismethodisquickerandmoreefficientthanDFT.ThisessaymainlydealswiththeFastFourierTransformandthereductionofthesignal(n2andy=lOOOsin-,-300<%<300.Atthesametimejtwillshowthecomplexityofthetransform.Keywords:FastFourierTransform(FFT)引言有限長序列可以通過離散傅里葉變換(DFT)將其

3、頻域也離散化成有限長序列。但其計算量太大，很難實時地處理問題，因此引出了快速傅里葉變換(FFT).1965年,Cooley和Tukey提出了計算離散傅里葉變換(DFT)的快速算法，將DFT的運算量減少了幾個數量級。從此，對快速傅里葉變換(FFT)算法的研究便不斷深入，數字信號處理這門新興學科也隨FFT的出現和發展而迅速發展。2-分析的相關分析：原始數據：(MATLAB環境)forx=l:8;y=x*x;plot(xryr1+f,fColor1ffrf);holdon;end345678原始數據圖變換過程:AlXk=八kn/Nn=0AT/2-1=Vg.e-ik(2m)/N.7,人27nc'

4、;7二0N/21£772=0N/2-1Vro4J2;rk(2m+1)/Nm0N/21To-iNxkm/(N/2)+fk/N一"2tt"m/(N/2)42mc丁匕,42m+lcm=0利用左右對稱性:Xi=204;X2=-12.686291501015239+96.568542494923800/;X3=-32+40f;X4=-35.313708498984760+16.568542494923804/;X5=-36;X6=-35.313708498984760-16.568542494923804/;X7=-3240i;XQ=-12.686291501015239-

5、96.568542494923800/；還原時只需按照相反步驟執行即可：7060504030201012340復雜度：需進行12次復數乘法與24次復數加法。2.y=lOOOsiiij,-300<x<300x=linspace(-300,300);y=1000*sin(0.01*x);plot(xry),axis(-300300-10001000);1000acn8004002000200uooW)-aoo-1000M-緘-1000100no130現在從其中等距選取25。個點，并進行FFT變換：(C語言函數原型)voidFFT(void)(unsignedinti,j,k,1;com

6、plextop,bottom,xW:Reverse();for(i=0;i<log2N;i-H-)l=l«i;for(j=0;j<N;j+=2*l)(for(k=0;k<l;k+)(xW=mul(xj+k+l,WNN/(2*l)*k);top=add(xj+k,xW);bottom=sub(xj+k,xW);xj+k=top,xj+k+1=bottom;)采用MATLAB繪制圖形：(由于所給數據量太大，計算機在可計量時間內無法得出答案，故將數據量進行了縮小)代碼：pai=3.14159;t=linspace(-300,300,250);x=1000*sin(0.01

7、*t);y=fft(x);plot(abs(y);fft函數:»helpfftfftDiscreteFouriertransform.fft(X)isthediscreteFouriertransform(DFT)ofvectorX.Formatrices,thefftoperationisappliedtoeachcolumn.ForN-Darrays,thefftoperationoperatesonthefirstnon-singletondimension.fft(X,N)istheN-pointfft,paddedwithzerosifXhaslessthanNpoints

8、andtruncatedifithasmore.fft(X,DIM)orfft(X,N,DIM)appliesthefftoperationacrossthedimensionDIM.ForlengthNinputvectorx,theDFTisalengthNvectorX,withelementsNX(k)=sumx(n)*exp(-j*2*pi*(k-l)*(n-l)/N),1<=k<=N.n=lTheinverseDFT(computedbyIFFT)isgivenbyNx(n)=(1/N)sumX(k)*exp(j*2*pi*(k-1)*(n-l)/N),1<=n&

9、lt;=N.k=l1一0511S22S335，1(/其中橫坐標為頻率，縱坐標為幅值。（該圖繪制的是225個點，因為所給數據量太大，計算機在可計量時間內無法得出答案，故將數據量進行了縮小）其逆變換采用反向的方法可以得到。計算復雜度分析，共進行了25X25。次復數乘法與50X2$°次復數加法，其復雜度分別為mo°2N與NIoN3-總結FFT由于具有計算量小的顯著的優點，使得其在信號處理技術領域獲得了廣泛應用，本次研究課題通過對兩個簡單的例子進行分析，加深了對快速傅里葉變換的理解，并充分體會其優越性。可以說FFT的出現.為數字信號處理學科的發展起了重要的作用。4-致謝感謝楊小遠老師的精彩課程，她的課程內容豐富