【正文】 反變換將這些頻 域信號(hào)轉(zhuǎn)換成原來(lái)的時(shí)域信號(hào)，這是一種特殊的積分變換。然而，它在運(yùn)算上過(guò)于復(fù)雜，過(guò)于宏大的運(yùn)算過(guò)程，對(duì)于一些相對(duì)簡(jiǎn)單的低功耗處理器來(lái)說(shuō)，難以自如應(yīng)對(duì)，因此，快速 傅里葉變換則顯出了它的優(yōu)越性。對(duì)于計(jì)算機(jī)處理信號(hào)方面上是一大進(jìn)步。通過(guò)傅立葉變換（ DFT），運(yùn)用測(cè)試軟件進(jìn)行檢測(cè)，我們可以看出，快速傅里葉變換大大的提高了運(yùn)算速度，它為各系統(tǒng)的設(shè)計(jì)方案提供了簡(jiǎn)單算法，有著非常重要的意義。因?yàn)樗旧砭途哂幸幌盗械膬?yōu)點(diǎn)，所以能夠有效地促進(jìn)工程技術(shù)領(lǐng)域的技術(shù)改造和科學(xué)發(fā)展，應(yīng)用領(lǐng)域也更加地廣泛、深入，越來(lái)越受到人們的重視。由于離散傅里葉變換（ DFT）而發(fā)現(xiàn)了頻率離散化，可以直接用它來(lái)分析信號(hào)的頻譜、計(jì)算濾波器的頻率響應(yīng)、以及實(shí)現(xiàn)信號(hào)通過(guò)線系統(tǒng)的卷積運(yùn)算等，因而在信號(hào)的譜分析等方面有著非常大的作用。但需要用較為精準(zhǔn)的數(shù)字方法，即 DFT，進(jìn)行譜分析，在 快速傅氏變換（ FFT）出現(xiàn)以前是不 切實(shí)際的。直到 1965 年庫(kù)利（ ）和圖基（ ）首次發(fā)現(xiàn) DFT 的一種快速算法，局面才發(fā)生根本性的變化?？焖俑道锶~變換（ Fast Fourier Transform， FFT）并非與離散傅里葉變換完全不同的另一種變換，而是為了減少 DFT 計(jì) 算次數(shù)而誕生的一種快速、有效的算法。它使得 DFT 的運(yùn)算量大大的縮小簡(jiǎn)化，它推動(dòng)了近 30 年來(lái)信號(hào)處理技術(shù)止步不前的前進(jìn)發(fā)展，成為了數(shù)字信號(hào)處理應(yīng)用領(lǐng)域里強(qiáng)有力的工具，為 DFT 乃至數(shù)字信號(hào)處理技術(shù)的實(shí)際應(yīng)用創(chuàng)造了良好的條件，從而使 DFT 在實(shí)際使用中得以廣泛的應(yīng)用 [2]。近年來(lái)發(fā)展尤為迅速，它不僅應(yīng)用于數(shù)字信號(hào)處理方面，而且在圖像處理、語(yǔ)音處理、通信等領(lǐng)域得到廣泛的應(yīng)用。 DSP 處理器中集成了高速的乘法硬件，能快速、準(zhǔn)確地進(jìn)行大量數(shù)據(jù)的乘法以及加法的運(yùn)算。除了需要普通微處理器所強(qiáng)調(diào)的高速運(yùn)算和控制能力之外，鑒于實(shí)時(shí)數(shù)字信號(hào)處理的特點(diǎn)，在處理器結(jié)構(gòu)、指令系統(tǒng)、指令流程上做了很大程度上的改進(jìn)。 DSP芯片的出現(xiàn)，使 FFT的實(shí)現(xiàn)更加方便。 快速傅里葉變換為頻譜分析、卷積、相關(guān)數(shù)字濾波器設(shè)計(jì)與實(shí)現(xiàn)與功率譜計(jì)算、傳遞函數(shù)建模、圖像處理等，提供了快速有效的運(yùn)算方法。 武漢工程大學(xué)畢業(yè)設(shè)計(jì) (論文 )說(shuō)明書 3 數(shù) 字信號(hào)中的傅里葉變換 ,通常是采用離散 型傅里葉變換 (DFT)。比如，計(jì)算一個(gè) N 點(diǎn)的 DFT ,一般需要2N次復(fù)數(shù)乘法和 N(N1)次復(fù)數(shù)加法運(yùn)算 .因此 ,當(dāng) N較大或要求對(duì)信號(hào)進(jìn)行實(shí)時(shí)處理時(shí) ,往往很難實(shí)現(xiàn)達(dá)到所需的運(yùn)算速度。快速 傅里葉變換的實(shí)質(zhì)是利用式 (31)中的權(quán)函數(shù)nkNW的對(duì)稱性和周期性 ,把 N點(diǎn) DFT進(jìn)行一系列分解和組合 ,使整個(gè) DFT的計(jì)算過(guò)程變成一系列疊代運(yùn)算過(guò)程 ,使 DFT的運(yùn)算量大大簡(jiǎn)化 ,為 DFT及數(shù)字信號(hào)的實(shí)時(shí)處理和應(yīng)用創(chuàng)造了非常良好的條件 [3]。將時(shí)域序列逐次分解為一組子序列，依據(jù)旋轉(zhuǎn)因子的特性，由子序列的 DFT 來(lái)實(shí)現(xiàn)整個(gè)序列的 DFT[4]。當(dāng)1024?N點(diǎn)甚至更多的時(shí)候，需要 N2=1048576 次運(yùn)算。如此變換以后，總的運(yùn)算次數(shù)就變成了2/)2/(2 22 NNN ???。而如果我們將這種“一分為二”的思想不斷進(jìn)行下去，直到分成兩兩一組的 DFT運(yùn)算單元，那么 N點(diǎn)的 DFT 變換就只需要nN 2log次的運(yùn)算，N在 1024 點(diǎn)時(shí)，運(yùn)算量?jī)H有 10240 次，是先前的直接算法的 1%，點(diǎn)數(shù)越多，運(yùn)算量的節(jié)約就越大，這就是 FFT 的優(yōu)越性 .當(dāng)然， FFT 提高了運(yùn)算速度 ,但是 ,也對(duì)參與運(yùn)算的樣本序列作出了限制 ,即要求樣本數(shù)為 2^N點(diǎn) .離散傅里葉變換 DFT則無(wú)上述限制 [5]。要知道傅立葉變換算法的意義，首先要了解傅立葉變換原理的意義。而利用該原理而創(chuàng)立的傅立葉變換算法則利用直接能測(cè)量到的原始信號(hào)，并以累加方式來(lái)計(jì)算該信號(hào)中不同正弦波信號(hào)的頻率、相 位和振幅。該反變換從本質(zhì)上說(shuō)也就是一種累加處理，這樣便可以將單獨(dú)改變的正弦波信號(hào)轉(zhuǎn)換成一個(gè)信號(hào)。武漢工程大學(xué)畢業(yè)設(shè)計(jì) (論文 )說(shuō)明書 5 最后還可以利用傅立葉反變換將這些頻域信號(hào)轉(zhuǎn)換成原來(lái)的時(shí)域信號(hào)。它能夠?qū)M足一定條件下的某個(gè)函數(shù)表示成為正弦基函數(shù)的線性組合或者積分形式。 在數(shù)學(xué)領(lǐng)域，盡管最初傅立葉分析是作為熱過(guò)程的解析分析的工具，但是其思想方法仍然具有典型的還原論和分析主義的特征。2. 傅立葉變換的逆變換容易求出 ,而且形式與正變換非常類似 。4. 離散形式的傅立葉的物理系統(tǒng)內(nèi) ,頻率是個(gè)不變的性質(zhì) ,從而系統(tǒng)對(duì)于復(fù)雜激勵(lì)的響應(yīng)可以通過(guò)組合其對(duì)不同頻率正弦信號(hào)的響應(yīng)來(lái)獲取 。 正是由于上述的良好性質(zhì) ,傅里葉變換在物理學(xué)、數(shù)論、組合數(shù)學(xué)、信號(hào)處理、概率、統(tǒng)計(jì)、密碼學(xué)、聲學(xué)、光學(xué)等領(lǐng)域都有著廣泛的應(yīng)用 [6]。 錯(cuò)誤 !未找到引用源。10)( )(0 ??? ??? Nne NnkxX NKn k ?? (31) 由 (31)式可知，對(duì)每一個(gè) n，計(jì)算 X(ｎ )須作 N次復(fù)數(shù)乘法及 N1次復(fù)數(shù)加法，要完成這組變換共需 N2 錯(cuò)誤 !未找到引用源。但以下介紹的快速 傅里葉變換的算法，可大大減少運(yùn)算次數(shù)，提高工作效率。 (32) 121 2 0 1 2 022rrr r r rk k k k k k k??? ? ? ?? ? ? ? ? （ 33） 又記 NWe???? ,則（ 31）式可改寫為 0 0 1 1 01 1 11 2 0 0 1 2 00( ) ( )r pr r r rk k kX n n n x k k k W? ? ?? ? ? ??? ? ? ? （ 34） 式中： 1 2 1 21 2 0 1 2 0( 2 2 ) ( 2 2 )r r r rr r r rP n k k k k n n n? ? ? ?? ? ? ?? ? ? ? ? ? ? ? ? 1 2 1 1 2 21 2 0 1 1 2 0 2( 2 2 ) 2 ( 2 2 ) 2r r r r r rr r r r r rn n n k n n n kPW W W? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ?? 120 1 2 0( 2 2 )rrrrK n n nW ????? ? ? (35) 因?yàn)?22 [ ] 1r r NNW W e ??? ? ?所以（ 32）可改成 Z 0 0 1 1 01 1 11 2 0 0 1 2 00( ) ( )rr r r rk k kX n n n x k k k? ? ?? ? ? ??? ? ?1 2 1 1 2 2 1 21 2 0 1 1 2 0 2 0 1 2 0( 2 2 ) 2 ( 2 2 ) 2 ( 2 2 )r r r r r r r rr r r r r r r rn n n k n n n k K n n nW W W? ? ? ? ? ? ? ?? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? （ 36） 2012 0 1 3 0 0 0 2 0( ) ( )rrrkx n n k k x n k k????? ?1 0 2(2 )2 2 rn n r kW ??? (37) 1 2 0 0 1 1( ) ( )r r r rX n n n x n n n? ? ?? 武漢工程大學(xué)畢業(yè)設(shè)計(jì) (論文 )說(shuō)明書 7 則式（ 37）即為式（ 36）的分解形式。當(dāng) 1ln? 分別?。昂停睍r(shí)，分別有 , / 2 lk i k j i n? ? ? ?。將 ()lxi與 ( /2 )llx i n? 稱為第 L個(gè)數(shù)組中的對(duì)偶結(jié)點(diǎn)對(duì)。 因 2/2 1112 NPPP R ???? ? ，于是對(duì)偶結(jié)點(diǎn)的 pW 有如下關(guān)系： 1112 22 ][ PNPNNPP WeWW ???? ??? ??,因此式（ 38）可表示為 1111( ) ( ) [ ]2( ) ( ) [ ]22pl l l lpl l lllNx i x i x i WNNx i x i x i W????? ? ?? ? ? ? （ 311） 武漢工程大學(xué)畢業(yè)設(shè)計(jì) (論文 )說(shuō)明書 8 P 的求法：在 )(ixl中， i 寫成二進(jìn)制數(shù) kknnnlrl 01110 ?? ???右移 lr? 位，就成為 nnn l 11000 ??? 顛倒位序得 )2,1(00011 rlp nnn l ??? ?? ? 式（ 37）中，前面的 r 個(gè)等式，每個(gè)等式均對(duì)應(yīng)一組數(shù)據(jù)進(jìn)行計(jì)算，每組數(shù)據(jù)都有 N/２對(duì)結(jié)點(diǎn)，根據(jù)式（ 311），每對(duì)結(jié)點(diǎn)只需作１次乘法和２次加法，因此，每組數(shù)據(jù)只需 N/2次乘法和 N次加法，因而完成 r組數(shù)據(jù)的計(jì)算共需 Nr/2 次乘法和 Nr 次加法。作 N 點(diǎn) FFT 時(shí)，若 N 不是素?cái)?shù)，則 N 可分解為 12N NN? ，那么由 []fn的 DFT 10[ ] [ ] 0 1N nkNnF k f n W k N??? ? ? ?? （ 312） 通過(guò)映射： 2 1 2 1 1 2 21 1 2 1 1 2 20 1 , 0 10 1 , 0 1n N n n n N n Nk k N k k N k N? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? （ 313） 可得到 2 1 2 1 1 2 2 1 1 1 2 1 2 2 1 1 2 2( ) ( ) ( )N n n k N k N n k N N n k n k N n knkN N NW W W? ? ? ? ??? 而 12N NN? ， 12NNNWW?， 21NNNWW?，可化簡(jiǎn)為 1 1 2 1 2 212n k n k n knkN N N NW W W W? （ 314） 從而式（ 312）轉(zhuǎn)化為 212 2 2 1 1 121111 2 1 200[ , ] ( [ , ] )NNn k n k n kN N NnnF k k W W f n n W????? ?? （ 315） 其中 1 1 2 20 1 , 0 1k N k N? ? ? ? ? ?。 武漢工程大學(xué)畢業(yè)設(shè)計(jì) (論文 )說(shuō)明書 9 圖 31 CooleyTukey 20 點(diǎn) FFT算法 3. 3 RaderBrenner FFT 算法 RaderBrenner 算法是類似于 CooleyTukey 算法，但是采用的旋轉(zhuǎn)因 子都是純虛數(shù)，以增加加法運(yùn)算和降低了數(shù)值穩(wěn)定性為代價(jià)減少了乘法運(yùn)算。 Bruun 以及 QFT 算法是不斷的把 DFT 分成許多較小的 DFT 運(yùn)算。 Bruun 算法則可以運(yùn)用在可被分成偶數(shù)個(gè)運(yùn)算的數(shù)字 )。 另一個(gè)從多項(xiàng)式觀點(diǎn)的快速傅立葉變換法是 Winograd 算法。 這樣只需要很少的乘法量 (如果有需要的話 )，所以 winograd 是可以得到最少乘法量的快速傅立葉算法，對(duì)于較小的數(shù)字，可以找出有效率的算方式。 Winograd 也可以利用剩余值定理來(lái)簡(jiǎn)化 DFT。另一個(gè)primesize 的 FFT 算法為 chirpZ 算法。 Goertsel 算法 如前所述 , N 點(diǎn)時(shí)域序列 )(nx 的離散付里葉變換式為 ?? ?? ?10 )()( Nn knNWnxkX ， 1,....,2,1,0 ?? Nk （ 316） 這 N 點(diǎn)頻域序列是同時(shí)被算出的，不可能只計(jì)算其中某一個(gè)或幾個(gè)指定點(diǎn)。這個(gè)算法把離散付里葉變換看作一組濾波器，將輸入端的時(shí)域序列與其中一個(gè)濾波器的沖激響應(yīng)序列進(jìn)行卷積運(yùn)算，求濾波器的輸出序列，即得 )(kX 序列的一點(diǎn)。 由于 1))(2( ?? ???? kNNjkNN eW 故式（ 316）可化為 )(1010 )()()( mNkNNmkmNNmkNN WmxWmxWkX ??????? ????1,....,2,1,0 ?? Nk （ 317） 定義序列 )(nyk 為 )(10 )()( mnkNNmk Wm