fft的發(fā)展、現(xiàn)狀、典型算法

1、數(shù)字信號處理期末大作業(yè)FFT的發(fā)展史、現(xiàn)狀及典型算法班級學(xué)號：姓名：FFT的發(fā)展史、現(xiàn)狀及典型算法傅里葉分析已有200多年的歷史，目前FFT及其校正算法在工程實際中仍在廣泛應(yīng)用，展現(xiàn)了其不竭的生命力。本次作業(yè)我們論述FFT的現(xiàn)狀，發(fā)展史以及一些算法，去詳細了解、擴展這一算法，鞏固所學(xué)知識。一FFT的簡介傅里葉變換是一種將信號從時域變換到頻域的變換形式，然而當(dāng)N很大的時候，求一個N點的DFT要完成N*N次復(fù)數(shù)乘法和N*（N-1）次復(fù)數(shù)加法，計算量非常大，所以人們開始探索一種簡便的算法對于一個較大的N進行傅里葉變換。在20世紀(jì)60年代由Cooley和Tukey提出了快速傅里葉變換算法，它是快速計算

2、DFT的一種簡單高效的方法。關(guān)于何為FFT，它是根據(jù)離散傅氏變換的奇、偶、虛、實等特性，對離散傅立葉變換的算法進行改進獲得的。舉個例子，設(shè)x(n)為N項的復(fù)數(shù)序列，由DFT變換，任一X（m）的計算都需要N次復(fù)數(shù)乘法和N-1次復(fù)數(shù)加法，而一次復(fù)數(shù)乘法等于四次實數(shù)乘法和兩次實數(shù)加法，一次復(fù)數(shù)加法等于兩次實數(shù)加法，即使把一次復(fù)數(shù)乘法和一次復(fù)數(shù)加法定義成一次“運算”（四次實數(shù)乘法和四次實數(shù)加法），那么求出N項復(fù)數(shù)序列的X（m）,即N點DFT變換大約就需要N2次運算。當(dāng)N=1024點甚至更多的時候，需要N2=1048576次運算，在FFT中，利用WN的周期性和對稱性，把一個N項序列（設(shè)N=2k,k為正整

3、數(shù)），分為兩個N/2項的子序列，每個N/2點DFT變換需要（N/2）2次運算，再用N次運算把兩個N/2點的DFT變換組合成一個N點的DFT變換。這樣變換以后，總的運算次數(shù)就變成N+2*（N/2)2=N+（N2）/2。繼續(xù)上面的例子，N=1024時，總的運算次數(shù)就變成了525312次，節(jié)省了大約50%的運算量。而如果我們將這種“一分為二”的思想不斷進行下去，直到分成兩兩一組的DFT運算單元，那么N點的DFT變換就只需要Nlog2N次的運算，N在1024點時，運算量僅有10240次，是先前的直接算法的1%，點數(shù)越多，運算量的節(jié)約就越大，這就是FFT的優(yōu)越性。所以使用FFT算法，可以大大提高傅里葉變

4、換的運算速度，運算時間縮短一到兩個數(shù)量級，從而使DFT變換應(yīng)用迅速普及，不僅在頻譜分析，而且在線性卷積、線性相關(guān)等方面得到廣泛應(yīng)用。二FFT的現(xiàn)實意義隨著計算機技術(shù)的發(fā)展，離散傅里葉變化的出現(xiàn)使得傅里葉變換在工程中進入實際應(yīng)用階段。在信號處理中，DFT的計算具有舉足輕重的作用，信號的相關(guān)、濾波、譜估計等都要通過DFT來實現(xiàn)，但必須減少它的運算量，DFT才能在工程計算中具有實用價值。所以，F(xiàn)FT的出現(xiàn)提高了它的實用價值。而FFT成為數(shù)字信號處理的關(guān)鍵技術(shù)，在信號處理領(lǐng)域扮演的角色越來越重要。高效率的快速傅立葉變換(FFT)算法是雷達信號處理、衛(wèi)星通訊、生物醫(yī)學(xué)和多媒體信號處理等基礎(chǔ)和核心算法。提

5、高FFT處理速度滿足對雷達信號處理實時性的，要求在EW接收機高速數(shù)據(jù)處理方面將有廣泛的應(yīng)用前景。隨著科學(xué)技術(shù)的不斷進步，相控陣體制已廣泛應(yīng)用于各種星載、機載、艦載和地面雷達。對于電尺寸較大幾十甚至幾百個波長的相控陣天線，(如高分辨率星載，SAR天線、大型稀布陣天線等)，用公式按級數(shù)求和計算陣列天線方向圖的方法效率甚低。FFT的引入將從根本上解決這一難題。平面近場測量方法是天線測量的常規(guī)手段而FFT技術(shù)加快了天線參數(shù)評估的速度。三傅里葉變換的發(fā)展歷程對于發(fā)展史，我們由記載可知，離散傅里葉變換DFT是數(shù)字信號處理最重要的基石之一，也是對信號進行分析和處理時最常用的工具之一。在200多年前法國數(shù)學(xué)家

6、、物理學(xué)家傅里葉提出后來以他名字命名的傅里葉級數(shù)之后，用DFT這個工具來分析信號就已經(jīng)為人們所知。歷史上最偉大的數(shù)學(xué)家之一。歐拉是第一個使用“函數(shù)”一詞來描述包含各種參數(shù)的表達式的人，例如：y = f(x)。他是把微積分應(yīng)用于物理學(xué)的先驅(qū)者之一。 給出了一個用實變量函數(shù)表示傅立葉級數(shù)系數(shù)的方程； 用三角級數(shù)來描述離散聲音在彈性媒介中傳播，發(fā)現(xiàn)某些函數(shù)可以通過余弦函數(shù)之和來表達。 但在很長時間內(nèi)，這種分析方法并沒有引起更多的重視，最主要的原因在于這種方法運算量比較大。直到1965年，Cooley和Tukey在計算機科學(xué) 發(fā)表著名的機器計算傅立葉級數(shù)的一種算法論文，F(xiàn)FT才開始大規(guī)模應(yīng)用。那個年代

7、，有個肯尼迪總統(tǒng)科學(xué)咨詢委員會。其中有項研究主題是，對蘇聯(lián)核測試進行檢測，Tukey就是其中一員。美國/蘇聯(lián)核測試提案的批準(zhǔn)，主要取決于不實地訪問核測試設(shè)施而做出檢測的方法的發(fā)展。其中一個想法是，分析離海岸的地震計情況，這種計算需要快速算法來計算DFT。其它應(yīng)用是國家安全，如用聲學(xué)探測遠距離的核潛艇。所以在軍事上，迫切需要一種快速的傅立葉變換算法，這也促進了FFT的正式提出。FFT的這種方法充分利用了DFT運算中的對稱性和周期性，從而將DFT運算量從N2減少到N*log2N。當(dāng)N比較小時，F(xiàn)FT優(yōu)勢并不明顯。但當(dāng)N大于32開始，點數(shù)越大，F(xiàn)FT對運算量的改善越明顯。比如當(dāng)N為1024時，F(xiàn)FT

8、的運算效率比DFT提高了100倍。在庫利和圖基提出的FFT算法中，其基本原理是先將一個N點時域序列的DFT分解為N個1點序列的DFT，然后將這樣計算出來的N個1點序列DFT的結(jié)果進行組合，得到最初的N點時域序列的DFT值。實際上，這種基本的思想很早就由德國偉大的數(shù)學(xué)家高斯提出過，在某種情況下，天文學(xué)計算（也是現(xiàn)在FFT應(yīng)用的領(lǐng)域之一）與等距觀察的有限集中的行星軌道的內(nèi)插值有關(guān)。由于當(dāng)時計算都是靠手工，所以產(chǎn)生一種快速算法的迫切需要。 而且，更少的計算量同時也代表著錯誤的機會更少，正確性更高。高斯發(fā)現(xiàn)，一個富氏級數(shù)有寬度N=N1*N2，可以分成幾個部分。計算N2子樣本DFT的N1長度和N1子樣本

9、DFT的N2長度。只是由于當(dāng)時尚欠東風(fēng)計算機還沒發(fā)明。在20世紀(jì)60年代，伴隨著計算機的發(fā)展和成熟，庫利和圖基的成果掀起了數(shù)字信號處理的革命，因而FFT發(fā)明者的桂冠才落在他們頭上。之后，桑德-圖基等快速算法相繼出現(xiàn)，幾經(jīng)改進，很快形成了一套高效運算方法，這就是現(xiàn)在的快速傅立葉變換（FFT）。這種算法使DFT的運算效率提高1到2個數(shù)量級，為數(shù)字信號處理技術(shù)應(yīng)用于各種信號的實時處理創(chuàng)造了良好的條件，大大推進了數(shù)學(xué)信號處理技術(shù)。1984年，法國的杜哈梅和霍爾曼提出的分裂基塊快速算法，使運算效率進一步提高。庫利和圖基的FFT算法的最基本運算為蝶形運算，每個蝶形運算包括兩個輸入點，因而也稱為基-2算法。

10、在這之后，又有一些新的算法，進一步提高了FFT的運算效率，比如基-4算法，分裂基算法等。這些新算法對FFT運算效率的提高一般在50%以內(nèi)，遠遠不如FFT對DFT運算的提高幅度。從這個意義上說，F(xiàn)FT算法是里程碑式的。可以說，正是計算機技術(shù)的發(fā)展和FFT的出現(xiàn)，才使得數(shù)字信號處理迎來了一個嶄新的時代。除了運算效率的大幅度提高外，F(xiàn)FT還大大降低了DFT運算帶來的累計量化誤差，這點常為人們所忽略。以上為FFT的發(fā)展史，在整個發(fā)展歷程中，傅里葉的發(fā)明作用尤為重要，后人的推動，改良在發(fā)展史上也起到了至關(guān)重要的作用。四FFT的現(xiàn)狀、發(fā)展熱度對于傅里葉變換的現(xiàn)狀，我們分為國內(nèi)國外兩部分進行討論：首先介紹國

11、外現(xiàn)狀，國外圍繞快速傅立葉變換的并行計算進行了多項研究和開發(fā)。美國新墨西哥大學(xué)Vasilios Georgitsis等人設(shè)計了2-DFFT程序，可處理512*512個點的圖像，其底層通信基于PVM，將2-DFFT轉(zhuǎn)化成1-DFFT并行計算，完成了二維圖像的變換。目前最新的研究成果是由麻省理工學(xué)院計算機科學(xué)實驗室超級計算技術(shù)組開發(fā)的FFTW。FFTW是計算離散傅里葉變換DFT的快速C程序的一個完整集合，它可計算一維或多維、實數(shù)據(jù)和復(fù)數(shù)據(jù)以及任意規(guī)模的DFT。 在FFTW中，DFT的計算由執(zhí)行器完成。執(zhí)行器是由許多高度優(yōu)化的、可組裝的子代碼模塊組成的。FFTW有一個規(guī)劃器。規(guī)劃器用以根據(jù)具體機器的

12、體系結(jié)構(gòu)特點和具體的DFT寬度N。在運行時尋找一種有效的子代碼塊組裝方式，因此使得FFTW具有很好的自適應(yīng)性和很快的運行速度。FFTW還包含對共享和分布式存儲系統(tǒng)的并行變換。 對于國內(nèi)現(xiàn)狀，在我國80年代初就開展了并行算法研究。快速傅立葉變換的并行算法主要包括基于SIMD-MC2、SIMD-BF、SIMD-CC、MIMD-DM四種體系結(jié)構(gòu)上的FFT算法，它們都是基-2FFT算法，算法各有利弊，受體系結(jié)構(gòu)影響較大。 SIMD-MC2上的FFT算法是按頻率抽取的快速傅立葉變換在網(wǎng)孔結(jié)構(gòu)上的具體實現(xiàn)。假設(shè)將n個處理器P0，P1，PN-1排成的方陣。初始序列開始時已處于陣列的各處理器中，即ak處于Pk

13、中。算法結(jié)束時，Pk保存bk。SIMD-BF上FFT算法是在一個n=2k的蝶形網(wǎng)絡(luò)，簡記為BF。將(k+1)、2k個節(jié)點布局成(k+1)行，每行有n個節(jié)點。令(r，i)表示第r行和第i列的坐標(biāo)，0，i，n-1，exp(r，i)表示在BF中坐標(biāo)點(r，i)處的w的指數(shù)，它等于字長為k的整數(shù)j，即exp(r，i)=j。使得如果i的二進制表示為a1，a2，ar-1，ar，ak，則j的二進制為ar，ar-1a1，000。也就是說將i的前r位取位反，即倒序，后面其余位補零就可以得到j(luò)。因為蝶形網(wǎng)絡(luò)第r-1行和第r行之間的連接，正好能滿足直接將dr-1，i和dr-1，j傳到P(r，j)和P(r，j)，所以

14、無需考慮選路時間。算法時間除計算w、exp(r，i)的時間外，主要是算法第2步進行復(fù)數(shù)運算的時間。它等于0( )，顯然優(yōu)于SIMD-MC2上的FFT算法，這也說明算法和體系結(jié)構(gòu)的密切關(guān)系。西安電子科技大學(xué)信息科學(xué)研究所提出了一種基于共享存儲的多機系統(tǒng)并行計算FFT算法。中國科學(xué)院計算技術(shù)研究所利用星型互聯(lián)網(wǎng)的遞歸可分解性的多樣性，提出了一種基于星型互聯(lián)網(wǎng)絡(luò)的并行快速傅立葉變換算法。星圖具有層次型結(jié)構(gòu)，可由許多低維的子星圖組成。國防科大就向量機上的FFT并行算法作了系統(tǒng)的研究，并就離散變換、卷積和濾波的并行算法，用多項式變換計算離散卷積以及短卷積嵌套計算長卷積的并行算法，并研究了離散卷積的并行計

15、算下界，對一維和二維濾波給出了用變換法及遞推公式計算的并行算法?？梢姛o論在與國內(nèi)還是國外，F(xiàn)FT算法都是研究的熱點，有著廣闊的發(fā)展前景。五基4FFT算法原理及介紹基4FFT算法是把長度N=4的序列一分為四，將N點DFT表示為4個N/4點DFT的線性組合。然后再把N/4點DFT一分為四，表示為四個N /16點的DFT。如此重復(fù)下去直至分解成兩點DFT的運算。多基時分蝶式運算定理在形式上比基2時分碟式運算定理復(fù)雜，但在本質(zhì)上是一致的。前者表明,對N=p，q的情形，若按xm(i)=x(ip+m)將原N點序列分解成p個q點的子序列，則原序列x(n)的DFT可由各子序列xm(i)的DFT的線性組合得到。

16、基4時分FFT算法是多基算法的特例，因此從多基時分FFT的蝶式運算定理即可推導(dǎo)出基4時分FFT算法的蝶式運算公式。具體算法如下：設(shè)p=4,q=N/4,這時由多基時分蝶式運算定理,輸入序列x(n)可以分解成如下的4個子序列:子序列均為N/4點序列，設(shè)它們的N/4點DFT為，則其中，k,s,r均為整數(shù)。將s=0,1，2,3代入上式，則：,其中，上式就是基4FFT蝶形運算公式。其具體算法和基2算法相近。將式中的序列整理為4個序列，然后繼續(xù)拆分，即可得最后結(jié)果。相比于基2FFT算法，基4FFT算法運算量較小，但是相應(yīng)的變換長度更少，靈活性不如基2FFT算法。六實際應(yīng)用中的FFT典型算法描述及介紹（1）

17、余弦窗插值FFT算法加窗插值FFT算法是一種異步采樣方法，它是以固定不變的采樣頻率對信號進行采樣，利用窗函數(shù)截斷信號時產(chǎn)生的泄漏頻剖來得到信號的實際頻譜值。通過對信號加窗可以減小由頻譜泄漏現(xiàn)象引起的誤差，通過插值算法可以減小由柵欄效應(yīng)引起的誤差。用FFT計算電力系統(tǒng)諧波時需要將被測信號截斷，這樣就會產(chǎn)生截斷效應(yīng)，即產(chǎn)生頻譜泄漏，信號的基波和高次諧波譜線向附近展寬，形成主瓣和旁瓣。泄漏的頻譜主瓣可能淹沒主譜附近的諧波分量，影響是短范圍的。旁瓣的影響是長范圍(譜間干擾)的，它對相鄰的基波和高次諧波分量影響較大。當(dāng)采樣頻率是信號基波頻率的整倍數(shù)時，可以得到精確的計算結(jié)果，但是當(dāng)采樣頻率不是信號頻率的

18、整倍數(shù)時，由于柵欄效應(yīng)，只能測得泄漏的頻譜，計算產(chǎn)生誤差。加窗插值FFT算法可以計算出信號的頻率偏移量，再對測得的泄漏頻譜進行修正，從而得到實際信號的頻譜。實際信號的頻譜的計算精度取決于所加窗函數(shù)的特性，選擇主瓣窄的窗函數(shù)可以減小短范圍的影響；選擇旁瓣峰值小、衰減速度快的窗函數(shù)，可以減小長范圍的影響。一個理想的窗函數(shù)應(yīng)具有主瓣寬度窄、最大旁瓣峰值小和旁瓣衰減速度快的特點。但最大旁瓣峰值小且旁瓣衰減速度快的窗函數(shù)，其主瓣較寬，因此，要尋找主瓣窄且旁瓣峰值又小的窗函數(shù)是很困難的。泄漏頻譜主瓣的影響在實際應(yīng)用中可以通過增加觀測時間來消除，但這又影響了算法的實時性。實際上，觀測的基波周期數(shù)就是相鄰兩頻

19、譜主譜線之間的譜線間隔數(shù)，例如加漢寧窗截斷的正弦信號的頻譜泄漏主瓣的寬度為4個譜線間隔，要分辨出相鄰的諧波(消除主瓣的影響)，加漢寧窗插值FFT算法至少需要兩個基波周期的采樣點 (相鄰兩頻譜主譜線間隔兩個譜線間隔)；加Blackman-harris窗截斷的正弦信號的頻譜泄漏主瓣的寬度為8個譜線間隔，要分辨出相鄰諧波(消除主瓣的影響)，加Blackman-harris窗插值FFT算法至少需要4個基波周期的采樣點(相鄰兩頻譜主譜線間隔4個譜線間隔)。對旁瓣峰值高且衰減快的窗函數(shù)可再適當(dāng)增加觀測時間(采樣的基波周期數(shù))來消除臨近主瓣的峰值較高的幾個旁瓣對相鄰諧波的影響21，例如加漢寧窗插值FFT算法

20、采用4個基波周期的采樣點進行FFT變換還能提高計算精度。對旁瓣峰值不衰減的窗函數(shù)即使增加再多的觀測時間(采樣的基波周期數(shù))也無法消除旁瓣對相鄰諧波計算精度的影響。余弦窗的一般表達式5項余弦窗主瓣寬10/N，6項余弦窗主瓣寬12/N，7項余弦窗主瓣寬14/N，8項余弦窗主瓣寬16/N。5項余弦窗最大旁瓣峰值-89.69 db，6、7、8項余弦窗最大旁瓣峰值依次減小。從旁瓣衰減速度來看，7項余弦窗旁瓣衰減速度很慢，5、6、7項余弦窗旁瓣衰減依次加快，8項余弦窗旁瓣衰減速度最快，頻率為0.5時旁瓣峰值下降到-220db以下。7項余弦窗旁瓣基本不衰減，故加7項余弦窗插值FFT算法計算精度通過增加觀測時

21、間不能有效提高，精度甚至低于加5、6項余弦窗插值FFT算法。根據(jù)圖1中的頻譜特性可以看出，8項余弦窗主瓣雖寬，但最大旁瓣峰值最小，旁瓣衰減速度最快，考慮到泄漏頻譜主瓣的影響可以通過增加觀測時間來消除，加8項余弦窗插值FFT算法在這4種加余弦窗插值FFT算法中具有最高的計算精度?？紤]到余弦窗項數(shù)越多，加余弦窗FFT算法計算量越大。下面以單頻率信號為例進行分析，設(shè)復(fù)振幅Am一般為復(fù)數(shù)，反映了初相角，實際頻率fr= (l+r)*F，它在頻率lF和(l+1)*F之間，l 為整數(shù)，其中頻率分辨率F=1/(NTs)，Ts為采樣時間間隔，r為頻率偏移量，0<r<1。x(t)的離散形式為:其DFT

22、為：添加余弦窗后，DFT變?yōu)椋褐蟠胗嘞掖跋禂?shù)可求得最終結(jié)果。余弦窗函數(shù)系數(shù)如下表所示：余弦窗頻譜如下圖所示：（2）基于Nuttall窗的插值FFT算法上文使用的算法直接使用了余弦窗，在這里我們詳細分析第二種基于Nuttall窗的插值FFT算法。對于插值FFT算法而言，窗函數(shù)的不同會導(dǎo)致最終表達不同。在選擇窗函數(shù)時，對各種常見窗函數(shù)的頻譜特性進行了比較，得出以下結(jié)論：如果對實時性要求高而計算精度要求一般，應(yīng)選擇2項Hanning窗，由于觀測的周期數(shù)就是相鄰兩頻譜主譜線之間的譜線間隔數(shù)，加Harming窗截斷的正弦信號的頻譜泄漏主瓣的寬度為4個譜線間隔，要分辨出相鄰的諧波，至少需要2個周期的采

23、樣點，所需要的采樣周期數(shù)最少；如果對實時性要求較高且計算精度也較高，應(yīng)選擇3項Exact Blackman窗，其至少需4個周期的采樣點；如果對實時性要求一般，但要求很高的測量精度，應(yīng)當(dāng)選擇旁瓣衰減幅度大且衰減速率大的窗函數(shù)，在這里介紹的算法所采用的4項Nut-tall(I)窗與4項Blackman-harris窗相比具有這種特性，且頻率偏移量計算非常簡單，計算量非常小，算是一種改進算法。與普通的余弦窗插值方法一樣，我們以但頻率信號為例進行分析，振幅設(shè)定為復(fù)振幅，,則離散信號加余弦窗的DFT有：當(dāng)k=l時有如下關(guān)系式：當(dāng)N>>1時，有以下關(guān)系成立： 考慮到，當(dāng)K=3時，可以得到加余弦

24、窗DFT的通用形式為代入，可以得到Nuttall窗截斷后的信號頻譜為設(shè)定幅值比為由上式聯(lián)立解出r值為：由于頻率偏移量r的變化范圍為0-1，所以幅值比的變化范圍為0.75-4/3。將r代入式子中，解得修正后的復(fù)振幅：所以諧波相位也可以求得為到這步為止，已求得了信號的所需參數(shù)。插值算法的幅值比是頻率偏移量r的一次多項式，r的計算容易且計算量很小，這在加4項(及以上)窗插值FFT算法中是很難找到的。另外其窗函數(shù)頻譜旁瓣的衰減速率快，通過增加觀測時間，能有效地提高計算精度，計算精度優(yōu)于加Blackman-harris窗插值FFT算法。利用三次樣條插值函數(shù)計算復(fù)振幅的修正系數(shù)，能更好地提高加4項余弦窗Nuttall(I)窗插值FFT算法的計算速度。七FFT發(fā)展展望及啟示（1）快速變換算法的每一次突破都是找到一種數(shù)學(xué)工具以揭示變換的內(nèi)在關(guān)系,從而推動了快速