資源描述:
《快速傅里葉變換fft算法和其應用_————》由會員上傳分享,免費在線閱讀,更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、快速傅里葉變換FFT算法及其應用快速傅里葉變換FFT算法及其應用摘要本文較為系統(tǒng)地闡述了快速傅里葉變換的算法原理及其在數(shù)字信號處理等工程技術(shù)中的應用。根據(jù)抽取方法的不同,一維基2FFT算法分為兩種:頻域抽取的FFT算法和時頻域抽取的FFT算法。第1節(jié)闡述了這兩種FFT算法的原理。第2節(jié)給出了兩種算法的編程思想和步驟。第3節(jié)闡述了一維非基2FFT的兩種算法:Cooley-tukeyFFT算法和素因子算法(PrimeFactorAlgorithm)的思想原理,給出了在把一維非基2DFT的多層分解式轉(zhuǎn)化為二層分解的過程中,如何綜合運用這兩種算法以達到總運算次數(shù)最少的方案;并以20點
2、DFT為例描述了非基2FFT算法實現(xiàn)的一般步驟。第4節(jié)介紹了一維FFT算法在計算連續(xù)時間信號的傅里葉變換、離散信號的線性卷積、離散信號壓縮和濾波等數(shù)字信號處理中的典型應用。第5節(jié)把一維FFT變換推廣到二維FFT變換,并在一維FFT算法的基礎(chǔ)上,給出了二維FFT算法的原理和實現(xiàn)過程。最后在附錄中給出了一維DFT的基2FFT算法(包括頻域抽取的FFT和IFFT算法、時域抽取的FFT和IFFT算法),一維任意非基2FFT算法,二維DFT的基2FFT算法以及二維DFT的任意非基2FFT算法的詳細的VisualC++程序。本文通過各種流程圖和表格,較為深入系統(tǒng)地闡述了FFT的算法原理;
3、運用Matlab編程,通過大量生動的實例,圖文并茂地列舉出了FFT算法的各種應用,并在每個實例中都附上了完整的Matlab程序,可供讀者參考。由于篇幅所限,本文未涉及FFT變換以及其應用的數(shù)學理論背景知識。關(guān)鍵詞:FFT算法的應用,一維基2FFT算法,頻域抽取,時域抽取,非基2FFT算法,Cooley-Tukey算法,素因子算法,線形卷積,信號壓縮和濾波,二維FFT算法67快速傅里葉變換FFT算法及其應用67快速傅里葉變換FFT算法及其應用目錄摘要1目錄21一維DFT的快速算法—FFT41.1頻域抽取的基2算法41.1.1正變換的計算41.1.2逆變換的計算71.2時域抽取的
4、基2算法82一維基2FFT算法編程103一維任意非基2FFT算法143.1Cooley-TukeyFFT算法143.2素因子算法(PFA)143.3一維任意非基2FFT算法164一維FFT算法的應用204.1利用FFT計算連續(xù)時間信號的傅里葉變換204.2利用FFT計算離散信號的線性卷積234.3利用FFT進行離散信號壓縮254.4利用FFT對離散信號進行濾波284.5利用FFT提取離散信號中的最強正弦分量315二維DFT的快速變換算法及應用簡介365.1二維FFT變換及其算法介紹365.2二維FFT變換算法的應用37參考文獻38附錄391.一維DFT的基2FFT算法Visu
5、alC++程序39(1)頻域抽取的FFT和IFFT算法39(2)時域抽取的FFT和IFFT算法442.一維任意非基2FFT算法VisualC++程序4967快速傅里葉變換FFT算法及其應用3.二維DFT的基2FFT算法VisualC++程序544.二維DFT的任意非基2FFT算法VisualC++程序621一維DFT的快速算法—FFT當序列的點數(shù)不超過時,它的點定義為(1)反變換定義為(2)二者形式相似,快速算法的原理一樣,這里先就其正變換進行討論。令,當依次取為時,可表示為如下的方程組:(3)由上式可見,直接按照定義計算點序列的點時,每行含個復乘和個加,從而直接按定義計算點
6、的總計算量為個復乘和個加。當較大時,很大,計算量過大不僅耗時長,還會因字長有限而產(chǎn)生較大的誤差,甚至造成計算結(jié)果不收斂。所謂快速傅里葉變換就是能大大減少計算量而完成全部點計算的算法。下面介紹兩種經(jīng)典的的快速算法:頻域抽取的算法和時域抽取的算法。67快速傅里葉變換FFT算法及其應用1.1頻域抽取的基2算法1.1.1正變換的計算這里僅介紹基2算法,即是2的整次冪的情況。由定義(4)把分成兩半,即和,代入(4)式得(5)由于(5)式兩項又可合并為(6)當為偶數(shù)時,注意到,,(6)式變?yōu)椋?)當為奇數(shù)時,,(6)式變?yōu)椋?)這樣就把一個點序列()的點()計算化成了兩個點序列(和)的點
7、(和)計算。由劃分成和的計算量為個加,即和和個乘,即67快速傅里葉變換FFT算法及其應用由于算出的點,是的點()中為偶數(shù)的那一半,由算出的則是為偶數(shù)的那一半,故需要把偶數(shù)的抽出來放在一起作為的()輸出,同時把奇數(shù)的抽出來放在一起作為的()輸出。由于是頻域變量,故這種算法稱為頻域抽取的算法。接著,兩個點仍可用上述方法各經(jīng)個乘個加劃分成兩個點(同時還要做相應的頻域抽?。?,從而共劃分成4個點,總劃分計算量仍是個加和個乘。這樣的劃分可一步步做下去,不難看出,每步的總劃分計算量都是個加和個乘。經(jīng)過步的劃分后就劃成