快速傅立葉變換-算法及應(yīng)用.pdf

1、離散傅立葉變換(DFT)廣泛應(yīng)用于幾乎所有科學和工程領(lǐng)域。在信號處理領(lǐng)域中，傅立葉變換是最重要的信號處理工具。在通信領(lǐng)域，傅立葉變換大量應(yīng)用于正交頻分復用(OFDM)系統(tǒng)中。然而，直接計算傅立葉變換是一個計算強度很大的工作。所以，高效計算強度小的計算算法是必需的?？焖俑盗⑷~變換(FFT)就是一類高效計算強度小的傅立葉變換的計算算法。
　　麻省理工的Johnson和Frigo教授提出的修正的分裂基FFT(MSRFFT)算法是2014

2、之前計算復雜度最低的算法(2014我們提出2個計算復雜度更低的算法)。為了提高該算法的實用性,通過分析MSRFFT,我們發(fā)現(xiàn)MSRFFT有一組分解不是必需的。另外，通過適當?shù)淖儞Q，可以減少查表訪問旋轉(zhuǎn)因子的次數(shù)。因此，我們對該算法進行了完善,將該算法的4個分解過程只保留了3個(但計算復雜度保持不變),將MSRFFT所需要的5/8N-2次因子訪問次數(shù)減少到只要15/32N-2次。
　　針對長度為N=6m的DFT,我們提出了基-3/6

3、FFT算法來對其進行計算分解，在計算分解的同時對帶因子的子DFT進行旋轉(zhuǎn)變換,使得旋轉(zhuǎn)因子的下標不包括因子3,從而減少算法的計算復雜度。針對長度為q×2m的DFT，我們通過執(zhí)行2m個長度為q的DFT將該DFT分解成q個長度為2m的子DFT。該方法通過旋轉(zhuǎn)變換將帶因子wnN，wN/4+nN,…，w(q?1)N/4+nN的(共計q)項放在一列組成一個長度為q的子DFT,抽取該q個旋轉(zhuǎn)因子的公共因子wnN使得該子DFT變成帶常數(shù)因子的DFT(

4、SDFT)。SDFT將會使用我們提出的方法來高效實現(xiàn),減少其計算復雜度。由于長度為q的FFT的計算精度比2的冪次方的FFT差,我們對以上算法進行改進,通過旋轉(zhuǎn)變換將帶因子為W nq的(共計2m個)項放在一列組成一個長度為2m的子DFT,該SDFT同樣可以高效實現(xiàn),其計算復雜度和原算法一樣,精確度提高了。針對長度為N=2m的DFT，我們提出了四個算法。這四個算法,都是在MSRFFT算法的基礎(chǔ)上提出來的。我們的算法克服了MSRFFT算法的缺

5、點,將MSRFFT算法的因子抽取方法擴展到復數(shù)。相比于分裂基FFT(SRFFT)，我們所提四個計算2m長度FFT算法中的其中二個算法在計算復雜度、計算精度和旋轉(zhuǎn)系數(shù)計算或查表次數(shù)三個方面的性能得到了提高。其它兩個計算2m長度FFT算法是目前已經(jīng)出版的算法中計算復雜度最低的算法。
　　由于L-型的蝶的算法具有較高的實現(xiàn)復雜度，因此我們提出了一個新的實現(xiàn)方法,將一個L-型蝶分解成幾個類似于基-2FFT的蝶的執(zhí)行單元(BU-2),將一個

6、L-型蝶塊分解成幾個BU-2塊。所有分裂基系列FFT算法都可以使用這個方法象Cooley-Tukey算法一樣遞推實現(xiàn)。采用這個方法,我們用遞推的方法實現(xiàn)了第2章的簡化的修正的MSRFFT算法和第6章所提的計算長度N=q×2m的FFT算法。通過比較我們發(fā)現(xiàn):(1)遞推實現(xiàn)的MSFFT在DFT較小比其它算法速度快,但當DFT較大時,所需時間會會急劇增加,因為MSFFT需要的內(nèi)存比其它算法要多。(2)遞推實現(xiàn)的所提計算長度N=q×2m的FFT

7、算法,與其它算法相比所需要的時間相對要少;和FFTW相比,當DFT較小時,我們所提算法要比FFTW快,但當DFT較大時,我們的算法就比FFTW慢,因為我們的程序沒有進行內(nèi)存優(yōu)化。
　　剪切FFT就是針對輸入信號數(shù)目和/或輸出信號數(shù)目遠小于DFT長度的一類優(yōu)化算法。該類算法采用減少或消除標準FFT的多余操作的方式來達到提高效率的目的?？紤]到剪切FFT的蝶不再對稱的這一特點,我們提出四種基于共軛因子的方法來進行FFT剪切，減少剪切FF

8、T算法在輸入和/或輸出階段的計算復雜度。和其它剪切FFT算法相比,我們所提四種算法減少了計算復雜度。
　　多序列比對(MSA)是生物信號學中最重要的分析工具之一。有一個叫MAFT的MSA程序采用FFT來進行序列相似性的計算,識別相似區(qū)域,減少序列比對的解空間,是序列比對精度最高的MSA程序中速度最快的程序。為了進一步完善MAFFT的計算效率,我們對MAFFT的序列相似性的計算方法進行了三個方面的修正。首先,基于復數(shù)的氨基酸和核苷酸

9、表示被使用在修正的相關(guān)系數(shù)計算方案中,代替了原來基于實數(shù)的表示。由此,相比于原MAFFT方案,一半的內(nèi)存和一多半的計算可以節(jié)省。其次,線性巻積代替了循環(huán)卷積來計算氨基酸和核苷酸隊列的相關(guān)系數(shù),在計算最優(yōu)路徑的過程中,更多的同態(tài)區(qū)域?qū)话l(fā)現(xiàn)。再其次,我們設(shè)計一個FFT算法來高效計算線性巻積。所設(shè)計FFT算法基于共軛FFT(CPFFT),不需要執(zhí)行隊列的排序。該FFT還是一個新穎的剪切FFT,他的輸出只需要實數(shù)。模擬結(jié)果顯示修正的方案計算