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

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

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