DFT與FFT在實(shí)際應(yīng)用時(shí)的性能比較

DFT與FFT在實(shí)際應(yīng)用時(shí)的性能比較許磊(通信2班)摘要:分析了離散傅立葉變換(DFT)和它的快速算法(FFT)的計(jì)算，對(duì)DFT和FFT在應(yīng)用時(shí)的特點(diǎn)作了深入的比較，提出在某些實(shí)際應(yīng)用場(chǎng)合DFT比它的快速算法FFT更有優(yōu)勢(shì).關(guān)鍵詞:離散傅立葉變換;快速傅立葉變換;頻譜分析快速傅立葉變換(FFT)是離散傅立葉變換(DFT)的快速算法,FFT已在數(shù)字信號(hào)處理的場(chǎng)合中得到非常廣泛的應(yīng)用.一般情況下在需要計(jì)算頻譜的時(shí)候,往往首先會(huì)考慮采用FFT,假如在使用FFT時(shí)會(huì)發(fā)現(xiàn)它在某些情況下存在一些局限性，則會(huì)退一步考慮DFT是否可以避免這些局限性,通過進(jìn)一步分析比較及實(shí)際應(yīng)用表明其答案是肯定的.1DFT與FFT的算法[1]DFT是連續(xù)傅立葉變換的離散形式,其計(jì)算公式為X(k)=Ex(n)WnkN, k=0,1，…,N-1n=0,1,…,N-1式中x(n)為輸入信號(hào)的時(shí)域采樣序列，X(k)為計(jì)算輸出信號(hào)的頻域采樣序列，其中Wnk=j2nnk/N=cos(2nnk/N)-jsin(2nnk/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ù)加法.2DFT與FFT的比較(1)運(yùn)算量一般來說,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)點(diǎn)數(shù)或采樣率的可選性對(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ì)帶來局限性.實(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.數(shù)據(jù)內(nèi)存開銷對(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)動(dòng)態(tài)范圍或抗溢出性在定點(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結(jié)論在某些具體的應(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ù)或采樣率選擇更靈活、實(shí)時(shí)性更好、更容易控制溢出和動(dòng)態(tài)范圍、運(yùn)算編程簡(jiǎn)單、可方便地在非DSP芯片中編程實(shí)現(xiàn)等優(yōu)點(diǎn).因此在實(shí)際應(yīng)用中可以從具體條件出發(fā)來比較、選擇DFT或FFT,W不應(yīng)片面地由于FFT是所謂的DFT的快速算法而只選用FFT.參考文獻(xiàn)：吳湘淇.數(shù)字信號(hào)處理技術(shù)及應(yīng)用[M].北京:中國(guó)鐵道出版社,1986.332-516.張雄偉.DSP芯片的原理與開發(fā)應(yīng)用