【正文】 d e f???????????)(22)(22)(22xyyxIyxR???????第 4章 快速傅立葉變換（ FFT） 只需要兩次實(shí)數(shù)加和兩次實(shí)數(shù)乘就可實(shí)現(xiàn)。這樣， DITFFT運(yùn)算流圖中，從 L=3至 L=M級(jí)，每級(jí)都包含旋轉(zhuǎn)因子 ，第 L級(jí)中， 對(duì)應(yīng) N/2L個(gè)蝶形運(yùn)算。因此從第三級(jí)至最后一級(jí)，旋轉(zhuǎn)因子 節(jié)省的實(shí)數(shù)乘次數(shù)與 ()式相同。所以從實(shí)數(shù)乘運(yùn)算考慮，計(jì)算 N=2M點(diǎn) DITFFT所需實(shí)數(shù)乘法次數(shù)為 8/NNW8/NNW8/NNW8/NNW() 134 ( 3 ) 2 2 2 1 02 2 2MNNR M N M? ? ? ? ? ?? ? ? ? ? ? ? ?? ? ? ???? ? ? ? ? ?第 4章 快速傅立葉變換（ FFT） 若包含了所有旋轉(zhuǎn)因子，則稱(chēng)該算法為 一類(lèi)碟形單元運(yùn)算； 1mNW ??若去掉 的旋轉(zhuǎn)因子，則稱(chēng)之為 二類(lèi)碟形單元運(yùn) 算； (1 j) 2 / 2mNW ??若再判斷處理 ，則稱(chēng)之為 四類(lèi)碟形運(yùn)算。 jW rN ??若再去掉 的旋轉(zhuǎn)因子，則稱(chēng)為 三類(lèi)碟形單元運(yùn)算； 后三種運(yùn)算稱(chēng)為 多類(lèi)碟形單元運(yùn)算 。顯然，碟形單元類(lèi)型越多，編程就越復(fù)雜，但當(dāng) N較大時(shí)，乘法運(yùn)算的減少量是相當(dāng)可觀的。例如， N=4096時(shí)，三類(lèi)碟形單元運(yùn)算的乘法次數(shù)為一類(lèi)碟形單元運(yùn)算的 75% 第 4章 快速傅立葉變換（ FFT） ? 在 FFT運(yùn)算中，旋轉(zhuǎn)因子 ?，求正弦和余弦函數(shù)值的計(jì)算量是很大的。所以編程時(shí)，產(chǎn)生旋轉(zhuǎn)因子的方法直接影響運(yùn)算速度。 )/c o s ( NmπW mN 2? )/s in ( Nmπj 2? 旋轉(zhuǎn)因子的生成 ? 產(chǎn)生旋轉(zhuǎn)因子的方法 : ?1. 在每級(jí)運(yùn)算中直接產(chǎn)生； mNW? FFT程序開(kāi)始前預(yù)先計(jì)算出 ， m = 0， 1， … ， N/2－ 1， 存放在數(shù)組中，作為旋轉(zhuǎn)因子表，在程序執(zhí)行過(guò)程中直接查表得到所需旋轉(zhuǎn)因子值，不再計(jì)算 。 這樣使運(yùn)算速度大大提高， 第 4章 快速傅立葉變換（ FFT） 在實(shí)際工作中，數(shù)據(jù) x(n)常常是實(shí)數(shù)序列。如果直接按 FFT運(yùn)算流圖計(jì)算，就是把 x(n)看成一個(gè)虛部為零的復(fù)序列進(jìn)行計(jì)算，這就增加了存儲(chǔ)量和運(yùn)算時(shí)間。 實(shí)序列的 FFT算法 ?處理該問(wèn)題的方法有三種 : ?早期提出的方法是 用一個(gè) N點(diǎn) FFT計(jì)算兩個(gè) N點(diǎn)實(shí)序列的FFT，一個(gè)實(shí)序列作為 x(n)的實(shí)部，另一個(gè)作為虛部，計(jì)算完 FFT后，根據(jù) DFT的共軛對(duì)稱(chēng)性，由輸出 X(k)分別得到兩個(gè)實(shí)序列的 N點(diǎn) DFT。 ?第二種方法是 用 N/2點(diǎn) FFT計(jì)算一個(gè) N點(diǎn)實(shí)序列的 DFT。 ?第三種方法是用 離散哈特萊變換（ DHT） ［ 1］ 。 第 4章 快速傅立葉變換（ FFT） 設(shè) x(n)為 N點(diǎn)實(shí)序列，取 x(n)的偶數(shù)點(diǎn)和奇數(shù)點(diǎn)分別作為新構(gòu)造序列 y(n)的實(shí)部和虛部，即 12121222121?????????N10nnxjnxnyN10nnxnxnxnx，，，，，??)()()()()()()(? ?? ?112212( ) D F T ( ) ( )0 , 1 ,( ) D F T ( ) ( )epopX k x n Y k NkX k x n jY k??? ????? ? ? ??對(duì) y(n)進(jìn)行 N/2點(diǎn) FFT，輸出 Y(k)，則 用 N/2點(diǎn) FFT計(jì)算一個(gè) N點(diǎn)實(shí)序列的 DFT的原理： 第 4章 快速傅立葉變換（ FFT） 由于 x(n)為實(shí)序列，因此 X(k)具有共軛對(duì)稱(chēng)性， X(k)的另外N/2點(diǎn)的值為： )0(2 ),0(2 2211 XNXXNX ??????????????1210)()( * ???? NkkXkNX ，， ?12 ?N 根據(jù) DITFFT的思想及式 ()和 ()，可得到 X(k)的前 個(gè)值： 210)()()( 21NkkXWkXkX kN ，， ????() 其中： 第 4章 快速傅立葉變換（ FFT） 計(jì)算 點(diǎn) FFT的復(fù)乘次數(shù)為 ，計(jì)算式()的復(fù)乘次數(shù)為 ，所以用這種算法 , 計(jì)算 X(k)所需復(fù)數(shù)乘法次數(shù)為 。相對(duì)一般的 N點(diǎn) FFT算法，上述算法的運(yùn)算效率為 ，當(dāng) N=2M=210時(shí)，η=20/11，運(yùn)算速度提高近 1 2N)1(4 ?MN2N)1(42)1(4 ???? MNNMN)1/(2)1(4/2 ???? MMMNMN?第 4章 快速傅立葉變換（ FFT） 本章僅介紹算法最簡(jiǎn)單、編程最容易的基 2FFT算法原理及其編程思想，使讀者建立快速傅里葉變換的基本概念，了解研究 FFT算法的主要途徑和編程思路。其他高效快速算法請(qǐng)讀者參考文獻(xiàn)［ 1］、［ 3］、［ 12］。例如，分裂基 FFT算法、離散哈特萊變 (換 DHT)、基4FFT、基 8FFT、基 rFFT、混合基 FFT，以及進(jìn)一步減少運(yùn)算量的途徑等內(nèi)容，對(duì)研究新的快速算法都是很有用的。本節(jié)簡(jiǎn)要介紹其他幾種快速算法的運(yùn)算量及其主 其他快速算法簡(jiǎn)介 第 4章 快速傅立葉變換（ FFT） ? 從理論上講，不同基數(shù)的 FFT算法的運(yùn)算效率不同，實(shí)際中最常用的是基 2FFT、基 4 FFT、分裂基 FFT和 DHT ［ 1］ 。為此，下面簡(jiǎn)要介紹后三種 FFT算法的特點(diǎn)和運(yùn)算效率，以擴(kuò)展讀者的視野。其具體算法請(qǐng)參考文獻(xiàn)［ 1］、［ 12 ? 在基 rFFT算法中，基 4FFT算法運(yùn)算效率與基 8FFT很接近，但基 4FFT算法實(shí)現(xiàn)程序簡(jiǎn)單，且判斷開(kāi)銷(xiāo)少?？梢宰C明，當(dāng) FFT的基大于 4時(shí)，不會(huì)明顯降低計(jì)算量?；?FFT要求 N=4M， M為自然數(shù)。其復(fù)數(shù)乘法次數(shù)為 ［ 12］ （ ） 3 lb ( )8 NN?CM(基 4) 其中未計(jì)入乘以 177。 j和 1的計(jì)算 。 第 4章 快速傅立葉變換（ FFT） 比較基 2FFT的復(fù)數(shù)乘法次數(shù) ，基 4FFT的復(fù)數(shù)乘法次數(shù)減少 25%。 NNC M lb21)2( ? 1984年，法國(guó)的杜梅爾（ ）和霍爾曼（ H. Hollmann）將基 2分解和基 4分解糅合，提出了分裂基 FFT算法，其復(fù)數(shù)乘法次數(shù)接近 FFT理論最小值，但其運(yùn)算流圖卻與基 2FFT很相似，編程簡(jiǎn)單，運(yùn)算程序也很短，是一種很實(shí)用的高效算法。分裂基 FFT算法復(fù)數(shù)乘法次數(shù)為［ 2］ ? ?22l b ( ) 13 9 9MN NN? ? ?CM(分裂基 )= （ ） 第 4章 快速傅立葉變換（ FFT） ? 只考慮 （ ） 式的第一項(xiàng)，分裂基 FFT算法的復(fù)數(shù)乘法次數(shù)就比基 2FFT減少 33%，比基 4FFT減少 11%。應(yīng)當(dāng)說(shuō)明，在比較時(shí)，未考慮（ ）式后 2項(xiàng)減少的運(yùn)算量，所以分裂基 FFT算法的效率更高。 由此可見(jiàn)，分裂基FFT ? 但是，對(duì)實(shí)序列 x(n)，上述各種 FFT算法仍將其看成虛部為零的復(fù)序列存儲(chǔ)和計(jì)算。而一次復(fù)數(shù)乘法需要四次實(shí)數(shù)乘法和二次實(shí)數(shù)加法。所以，必然浪費(fèi)存儲(chǔ)資源和增加多余的運(yùn)算量。我們知道，實(shí)序列的 N點(diǎn) DFT具有共軛對(duì)稱(chēng)性， 即 ? *( ) ( ) , 0 , 1 , 2 , , 1X N k X k k N? ? ? ?第 4章 快速傅立葉變換（ FFT） 所以，只要計(jì)算出 X（ k）的前面 N/2個(gè)值，則其后面的N/2個(gè)值可以由對(duì)稱(chēng)性求得。因此， FFT算法得到的 N個(gè) X（ k）值有一半是多余的。 離散哈特萊變換（ DHT）就是針對(duì)實(shí)序列的一種高效變換算法， 相對(duì)一般的 FFT算法， DHT的快速算法FHT 可以減少近一半的計(jì)算量 ［ 1］ 。 N點(diǎn)基 2時(shí)域抽取快速 DHT（基 2DITFHT）算法的實(shí)數(shù)乘法次數(shù)為 ［ 1］ F H T 34M NM N? ? ?（ ） 第 4章 快速傅立葉變換（ FFT） N點(diǎn)基 2DITFHT算法的實(shí)數(shù)加法次數(shù)為 ［ 1］ 應(yīng)當(dāng)說(shuō)明， DHT是與 DFT不同的變換，所以要想得到實(shí)序列 DFT，還要根據(jù)二者的關(guān)系式進(jìn)行轉(zhuǎn)換。下面會(huì)看到該關(guān)系非常簡(jiǎn)單。 F H T1322MAN ??? （ ） 可見(jiàn)，基 2DITFHT算法的實(shí)數(shù)乘法次數(shù)約為基 2DITFFT算法的一半。與前面三種 FFT算法比較，對(duì)實(shí)序列，基 2DITFHT算法的實(shí)數(shù)乘法次數(shù)最少。 第 4章 快速傅立葉變換（ FFT） DHT具有以下主要優(yōu)點(diǎn)： (1) DHT是實(shí)數(shù)變換，在對(duì)實(shí)信號(hào)進(jìn)行處理時(shí)避免了復(fù)數(shù)運(yùn)算，運(yùn)算效率高，且實(shí)現(xiàn)硬件簡(jiǎn)單經(jīng)濟(jì)。 (2) DHT的正、逆變換（除了因子 1/N外）具有相同的形式，所以實(shí)現(xiàn)硬件或程序亦相同。 1H02 π( ) D H T [ ( ) ] ( )c o s ( ) 0 , 1 , 2 , , 1NNnX k x n x n k n k NN??? ? ? ??（ ） N點(diǎn) DHT定義如下： （ ） 1HH012 π( ) I D H T [ ( ) ] ( )c o s ( ) 0 , 1 , 2 , , 1NNkx n X k X k k n n NNN??? ? ? ??第 4章 快速傅立葉變換（ FFT） (4) DHT與 DFT之間的關(guān)系非常簡(jiǎn)單，容易實(shí)現(xiàn)二者之間的轉(zhuǎn)換，關(guān)系式如下： (3) DHT滿足循環(huán)卷積定理，所以，可以直接用 FHT實(shí)現(xiàn)實(shí)序列的快速卷積，大大提高處理速度，并使處理硬件簡(jiǎn)化。 所以對(duì)實(shí)信號(hào) x(n)進(jìn)行譜分析時(shí)，可以先對(duì) x(n)進(jìn)行 FHT, 得到 XH(k)=DHT[x(n)]N,然后再將Ｘ H(k)轉(zhuǎn)換成 X(k)=DFT[x(n)]N，這樣可以提高分析速度，減少存儲(chǔ)空間。 H H H H11( ) [ ( ) ( ) ] j [ ( ) ( ) ]22X k X k X N k X k X N k? ? ? ? ? ?（ ） 第 4章 快速傅立葉變換（ FFT）