離散傅立葉變換的快速傅立葉變換

離散傅立葉變換的快速傅立葉變換

快速傅立葉變換（fft）是一種快速的算法，用于分散傅立葉變換（dft）。該函數用于數字處理器的場合。一般來說，當需要計算頻帶時，首先考慮使用fft。如果你在使用fft時發(fā)現它有一些局限性，并且dft是否能夠避免這些局限性，那么它是安全的。通過對實際應用的再分析和比較，驗證結果是安全的。1fft算法的基本原理DFT是連續(xù)傅立葉變換的離散形式,其計算公式為X(k)=∑n=0N?1x(n)WnkN?k=0?1???N?1(1)X(k)=∑n=0Ν-1x(n)WΝnk?k=0?1???Ν-1(1)式中x(n)為輸入信號的時域采樣序列,X(k)為計算輸出信號的頻域采樣序列,其中Wnk=e-j2πk/N=cos(2πnk/N)-jsin(2πnk/N).從DFT的計算公式可看出對N點的DFT需計算N2個復數乘和N2個復數加運算.FFT是DFT的快速算法,其原理是將長序列DFT根據其內在的對稱性和周期性分解為短序列的DFT之和.N點的DFT先分解為2個N/2點的DFT,每個N/2點的DFT又分解為N/4點的DFT.最小變換的點數即所謂FFT的“基數”.因此,基數為2的FFT最小變換是2點DFT(或稱蝶形運算).在基數為2的N點FFT中,設N=2M,則總共可分成M級運算,每級中有N/2個蝶算,則N點FFT總共有(N/2)log2N個蝶算,而1個蝶算只需一個復數乘法,2個復數加法,因此對N點FFT需計算(N/2)log2N個復數乘法、Nlog2N個復數加法.2比較dft和fft(1)fft和dft比較一般來說,FFT比DFT運算量小得多,N點的FFT需要做(N/2)log2N次乘法運算,而N點DFT需要做N2次乘法運算,由此看來N點DFT運算量大約是FFT的2N/log2N倍,例如對1024點的變換,DFT大約是FFT的200倍.然而實際應用時存在下列情況:①實際應用時DFT中的乘法可以是實數和復數相乘,原因是輸入信號可以是實數,而FFT只能是復數和復數的乘法,原因是FFT是分級運算的,中間運算過程都是復數運算,由此來看DFT的運算量大約是FFT的Nlog2N倍,而不是2N/log2N倍.②實際應用時往往只關心整個頻譜中的某一部分,甚至是只關心某些個別頻點的譜線.DFT的特點是可按式(1)單獨計算某一部分的譜線,而直接進行FFT的算法必須計算整個頻譜后才能得到需要的那一部分頻譜,實際上已造成了浪費.如果N點的變換中只關心其中的M個頻點或稱M條譜線,那么實際DFT的運算量大約是FFT的M/N·N/log2N倍,即Mlog2N倍.例如對1024點的變換,只需關心10條譜線,那么直接用DFT和用FFT的運算量是相同的.因此,實際應用時DFT與FFT相比可能并沒有那么慢,甚至有可能比FFT快.(2)fft的變換特點對DFT來講,其變換點數可任意選定,如實際應用時采樣率已確定為1000Hz,如選變換點數為1000點,那么每條譜線正好可落在整數頻點上.FFT的變換點數必須是有規(guī)律的,如基數為2算法的FFT其點數必須是2M,如1024點、4096點等.在實際應用時為分析方便,采樣率往往要定為變換點數的倍數,如2048Hz、8192Hz,以避免變換后的頻譜落在復雜的帶小數點的頻點上.因此實際應用時FFT在變換點數選擇或采樣率選擇上可能會帶來局限性.(3)fft和lfts轉換算法都具有實時性DFT運算可以用采一點后立即進行相乘、累加運算的方法,即可以采一點算一點,從采樣結束到DFT變換結束只需要一個點的運算時間.而FFT運算必須在全部點采集結束后才能開始進行計算,因此從某種角度講DFT的實時性優(yōu)于FFT.(4)bft比fft更省數據高效對N點DFT來講,如只需其中的M個頻點,那么在計算時至少需2M個單元的數據內存,對N點FFT來講則至少需2N個單元的數據內存,另外現有的FFT程序一般需要將系數放在數據內存區(qū),因此需另選N個單元的數據內存,故DFT有可能比FFT更節(jié)省數據內存.(5)程序的復雜性DFT計算程序非常簡單而且可以非常方便地在非DFT專用芯片上實現,而FFT程序較為復雜.(6)p處理器輸出信號的溢出控制設計在定點運算的場合,DFT較FFT更容易實現多精度的運算,例如在TI公司的16位定點DSP處理器中,采用的數據和系數為16位,而相乘并累加的結果可設為雙字節(jié)即32位,一般來講設計合理的話不會產生計算溢出的現象,免去了復雜的溢出控制,同時輸入輸出信號可保持較好的動態(tài)范圍.FFT在程序中有防溢出的措施,然而在定點運算的場合點數越多輸入信號的動態(tài)范圍越小.3點的頻率譜線時dft與fft的比較在某些具體的應用場合,DFT與它的快速算法FFT相比可能更有優(yōu)勢,而FFT卻存在某些局限性.在只需要求出部分頻點的頻率譜線時DFT的運算時間大為減少,所需的數據內存量也大為減小.DFT與FFT相比還具有變換點數或采樣率選擇更靈活、