快速傅里葉變換fft算法與其應(yīng)用_------

《快速傅里葉變換fft算法與其應(yīng)用_------》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

1、快速傅里葉變換FFT算法及其應(yīng)用快速傅里葉變換FFT算法及其應(yīng)用摘要本文較為系統(tǒng)地闡述了快速傅里葉變換的算法原理及其在數(shù)字信號處理等工程技術(shù)中的應(yīng)用。根據(jù)抽取方法的不同，一維基2FFT算法分為兩種：頻域抽取的FFT算法和時(shí)頻域抽取的FFT算法。第1節(jié)闡述了這兩種FFT算法的原理。第2節(jié)給出了兩種算法的編程思想和步驟。第3節(jié)闡述了一維非基2FFT的兩種算法：Cooley-tukeyFFT算法和素因子算法(PrimeFactorAlgorithm)的思想原理，給出了在把一維非基2DFT的多層分解式轉(zhuǎn)化為二層分解的過程中

2、，如何綜合運(yùn)用這兩種算法以達(dá)到總運(yùn)算次數(shù)最少的方案；并以20點(diǎn)DFT為例描述了非基2FFT算法實(shí)現(xiàn)的一般步驟。第4節(jié)介紹了一維FFT算法在計(jì)算連續(xù)時(shí)間信號的傅里葉變換、離散信號的線性卷積、離散信號壓縮和濾波等數(shù)字信號處理中的典型應(yīng)用。第5節(jié)把一維FFT變換推廣到二維FFT變換，并在一維FFT算法的基礎(chǔ)上，給出了二維FFT算法的原理和實(shí)現(xiàn)過程。最后在附錄中給出了一維DFT的基2FFT算法（包括頻域抽取的FFT和IFFT算法、時(shí)域抽取的FFT和IFFT算法），一維任意非基2FFT算法，二維DFT的基2FFT算法以及二維

3、DFT的任意非基2FFT算法的詳細(xì)的VisualC++程序。本文通過各種流程圖和表格，較為深入系統(tǒng)地闡述了FFT的算法原理；運(yùn)用Matlab編程，通過大量生動的實(shí)例，圖文并茂地列舉出了FFT算法的各種應(yīng)用，并在每個(gè)實(shí)例中都附上了完整的Matlab程序，可供讀者參考。由于篇幅所限，本文未涉及FFT變換以及其應(yīng)用的數(shù)學(xué)理論背景知識。關(guān)鍵詞：FFT算法的應(yīng)用，一維基2FFT算法，頻域抽取，時(shí)域抽取，非基2FFT算法，Cooley-Tukey算法，素因子算法，線形卷積，信號壓縮和濾波，二維FFT算法67快速傅里葉變換FFT

4、算法及其應(yīng)用67快速傅里葉變換FFT算法及其應(yīng)用目錄摘要1目錄21一維DFT的快速算法—FFT41.1頻域抽取的基2算法41.1.1正變換的計(jì)算41.1.2逆變換的計(jì)算71.2時(shí)域抽取的基2算法82一維基2FFT算法編程103一維任意非基2FFT算法143.1Cooley-TukeyFFT算法143.2素因子算法（PFA）143.3一維任意非基2FFT算法164一維FFT算法的應(yīng)用204.1利用FFT計(jì)算連續(xù)時(shí)間信號的傅里葉變換204.2利用FFT計(jì)算離散信號的線性卷積234.3利用FFT進(jìn)行離散信號壓縮254.4

5、利用FFT對離散信號進(jìn)行濾波284.5利用FFT提取離散信號中的最強(qiáng)正弦分量315二維DFT的快速變換算法及應(yīng)用簡介365.1二維FFT變換及其算法介紹365.2二維FFT變換算法的應(yīng)用37參考文獻(xiàn)38附錄391．一維DFT的基2FFT算法VisualC++程序39（1）頻域抽取的FFT和IFFT算法39（2）時(shí)域抽取的FFT和IFFT算法442．一維任意非基2FFT算法VisualC++程序4967快速傅里葉變換FFT算法及其應(yīng)用3．二維DFT的基2FFT算法VisualC++程序544．二維DFT的任意非基2F

6、FT算法VisualC++程序621一維DFT的快速算法—FFT當(dāng)序列的點(diǎn)數(shù)不超過時(shí)，它的點(diǎn)定義為（1）反變換定義為（2）二者形式相似，快速算法的原理一樣，這里先就其正變換進(jìn)行討論。令，當(dāng)依次取為時(shí)，可表示為如下的方程組：（3）由上式可見，直接按照定義計(jì)算點(diǎn)序列的點(diǎn)時(shí)，每行含個(gè)復(fù)乘和個(gè)加，從而直接按定義計(jì)算點(diǎn)的總計(jì)算量為個(gè)復(fù)乘和個(gè)加。當(dāng)較大時(shí)，很大，計(jì)算量過大不僅耗時(shí)長，還會因字長有限而產(chǎn)生較大的誤差，甚至造成計(jì)算結(jié)果不收斂。所謂快速傅里葉變換就是能大大減少計(jì)算量而完成全部點(diǎn)計(jì)算的算法。下面介紹兩種經(jīng)典的的快速算法

7、：頻域抽取的算法和時(shí)域抽取的算法。67快速傅里葉變換FFT算法及其應(yīng)用1.1頻域抽取的基2算法1.1.1正變換的計(jì)算這里僅介紹基2算法，即是2的整次冪的情況。由定義（4）把分成兩半，即和，代入（4）式得（5）由于（5）式兩項(xiàng)又可合并為（6）當(dāng)為偶數(shù)時(shí)，注意到，，（6）式變?yōu)椋?）當(dāng)為奇數(shù)時(shí)，，（6）式變?yōu)椋?）這樣就把一個(gè)點(diǎn)序列（）的點(diǎn)（）計(jì)算化成了兩個(gè)點(diǎn)序列（和）的點(diǎn)（和）計(jì)算。由劃分成和的計(jì)算量為個(gè)加，即和和個(gè)乘，即67快速傅里葉變換FFT算法及其應(yīng)用由于算出的點(diǎn)，是的點(diǎn)（）中為偶數(shù)的那一半，由算出的則是為偶數(shù)

8、的那一半，故需要把偶數(shù)的抽出來放在一起作為的（）輸出，同時(shí)把奇數(shù)的抽出來放在一起作為的（）輸出。由于是頻域變量，故這種算法稱為頻域抽取的算法。接著，兩個(gè)點(diǎn)仍可用上述方法各經(jīng)個(gè)乘個(gè)加劃分成兩個(gè)點(diǎn)（同時(shí)還要做相應(yīng)的頻域抽?。瑥亩矂澐殖?個(gè)點(diǎn)，總劃分計(jì)算量仍是個(gè)加和個(gè)乘。這樣的劃分可一步步做下去，不難看出，每步的總劃分計(jì)算量都是個(gè)加和個(gè)乘。經(jīng)過步的劃分后就劃成