【正文】 H H H H11( ) [ ( ) ( ) ] j [ ( ) ( ) ]22X k X k X N k X k X N k? ? ? ? ? ?（ ） 第 4章 快速傅立葉變換（ FFT） 。 1H02 π( ) D H T [ ( ) ] ( )c o s ( ) 0 , 1 , 2 , , 1NNnX k x n x n k n k NN??? ? ? ??（ ） 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)系非常簡單，容易實現(xiàn)二者之間的轉(zhuǎn)換，關(guān)系式如下： (3) DHT滿足循環(huán)卷積定理，所以，可以直接用 FHT實現(xiàn)實序列的快速卷積，大大提高處理速度，并使處理硬件簡化。 第 4章 快速傅立葉變換（ FFT） DHT具有以下主要優(yōu)點： (1) DHT是實數(shù)變換，在對實信號進行處理時避免了復(fù)數(shù)運算，運算效率高，且實現(xiàn)硬件簡單經(jīng)濟。 F H T1322MAN ??? （ ） 可見，基 2DITFHT算法的實數(shù)乘法次數(shù)約為基 2DITFFT算法的一半。 N點基 2時域抽取快速 DHT（基 2DITFHT）算法的實數(shù)乘法次數(shù)為 ［ 1］ F H T 34M NM N? ? ?（ ） 第 4章 快速傅立葉變換（ FFT） N點基 2DITFHT算法的實數(shù)加法次數(shù)為 ［ 1］ 應(yīng)當(dāng)說明， DHT是與 DFT不同的變換，所以要想得到實序列 DFT，還要根據(jù)二者的關(guān)系式進行轉(zhuǎn)換。因此， FFT算法得到的 N個 X（ k）值有一半是多余的。所以，必然浪費存儲資源和增加多余的運算量。 由此可見，分裂基FFT ? 但是，對實序列 x(n)，上述各種 FFT算法仍將其看成虛部為零的復(fù)序列存儲和計算。分裂基 FFT算法復(fù)數(shù)乘法次數(shù)為［ 2］ ? ?22l b ( ) 13 9 9MN NN? ? ?CM(分裂基 )= （ ） 第 4章 快速傅立葉變換（ FFT） ? 只考慮 （ ） 式的第一項，分裂基 FFT算法的復(fù)數(shù)乘法次數(shù)就比基 2FFT減少 33%，比基 4FFT減少 11%。 第 4章 快速傅立葉變換（ FFT） 比較基 2FFT的復(fù)數(shù)乘法次數(shù) ，基 4FFT的復(fù)數(shù)乘法次數(shù)減少 25%。其復(fù)數(shù)乘法次數(shù)為 ［ 12］ （ ） 3 lb ( )8 NN?CM(基 4) 其中未計入乘以 177。可以證明，當(dāng) FFT的基大于 4時，不會明顯降低計算量。為此，下面簡要介紹后三種 FFT算法的特點和運算效率，以擴展讀者的視野。例如，分裂基 FFT算法、離散哈特萊變 (換 DHT)、基4FFT、基 8FFT、基 rFFT、混合基 FFT，以及進一步減少運算量的途徑等內(nèi)容，對研究新的快速算法都是很有用的。相對一般的 N點 FFT算法，上述算法的運算效率為 ，當(dāng) N=2M=210時，η=20/11，運算速度提高近 1 2N)1(4 ?MN2N)1(42)1(4 ???? MNNMN)1/(2)1(4/2 ???? MMMNMN?第 4章 快速傅立葉變換（ FFT） 本章僅介紹算法最簡單、編程最容易的基 2FFT算法原理及其編程思想，使讀者建立快速傅里葉變換的基本概念，了解研究 FFT算法的主要途徑和編程思路。 ?第三種方法是用 離散哈特萊變換（ DHT） ［ 1］ 。 實序列的 FFT算法 ?處理該問題的方法有三種 : ?早期提出的方法是 用一個 N點 FFT計算兩個 N點實序列的FFT，一個實序列作為 x(n)的實部，另一個作為虛部，計算完 FFT后，根據(jù) DFT的共軛對稱性，由輸出 X(k)分別得到兩個實序列的 N點 DFT。 這樣使運算速度大大提高， 第 4章 快速傅立葉變換（ FFT） 在實際工作中，數(shù)據(jù) x(n)常常是實數(shù)序列。所以編程時，產(chǎn)生旋轉(zhuǎn)因子的方法直接影響運算速度。顯然，碟形單元類型越多，編程就越復(fù)雜，但當(dāng) N較大時，乘法運算的減少量是相當(dāng)可觀的。所以從實數(shù)乘運算考慮，計算 N=2M點 DITFFT所需實數(shù)乘法次數(shù)為 8/NNW8/NNW8/NNW8/NNW() 134 ( 3 ) 2 2 2 1 02 2 2MNNR M N M? ? ? ? ? ?? ? ? ? ? ? ? ?? ? ? ???? ? ? ? ? ?第 4章 快速傅立葉變換（ FFT） 若包含了所有旋轉(zhuǎn)因子，則稱該算法為 一類碟形單元運算； 1mNW ??若去掉 的旋轉(zhuǎn)因子，則稱之為 二類碟形單元運 算； (1 j) 2 / 2mNW ??若再判斷處理 ，則稱之為 四類碟形運算。這樣， DITFFT運算流圖中，從 L=3至 L=M級，每級都包含旋轉(zhuǎn)因子 ，第 L級中， 對應(yīng) N/2L個蝶形運算。一般實現(xiàn)一次復(fù)數(shù)乘法運算需要四次實數(shù)乘，兩次實數(shù)加。 依此類推，當(dāng) L≥3時，第 L級的 2個無關(guān)緊要的旋轉(zhuǎn)因子減少復(fù)數(shù)乘法的次數(shù)為 2N/2L=N/2L－ 1。 j的旋轉(zhuǎn)因子為無關(guān)緊要的旋轉(zhuǎn)因子，如 ， ， 等。在 DFT中，又稱其值為 177。由 ()式，當(dāng) L=1時，只有一種旋轉(zhuǎn)因子 ，所以，第一級不需要乘法運算。 ?頻率抽取的 FFT運算用于 IDFT運算時，也應(yīng)改變?yōu)闀r間抽取的 IFFT。 第 4章 快速傅立葉變換（ FFT） )2()()(1 Nnxnxnx ???1,1,0 2 ?? Nn ?nNWNnxnxnx?????? ??? )2()()(2進行如下碟形運算：和 )2()( Nnxnx ?1 nNW)2( Nnx ?)(nx(二 )蝶形運算 第 4章 快速傅立葉變換（ FFT） 圖 DIF―FFT 蝶形運算流圖符號 第 4章 快速傅立葉變換（ FFT） N=8時 ,按 k的奇偶分解過程先蝶形運算 ,后作 DFT: 1 1 1 1 )0(x)1(x)5(x)4(x)3(x)2(x)7(x)6(x)0(X)4(X)6(X)1(X)5(X)3(X)7(X)2(XD FTN點2D FTN點21NW2NW3NW0NW第 4章 快速傅立葉變換（ FFT） X(0) X(6) X(4) X(2) X(1) X(5) X(3) X(7) 0 N W 1 N W 2 N W 3 N W 1 1 1 1 x(0) x(3) x(1) x(2) x(4) x(5) x(6) x(7) 0 N W 2 N W 2點 DFT 1 1 2 N W 0 N W 1 1 2點 DFT 2點 DFT 2點 DFT 仿照按時間抽取的方法，再將 N/2點 DFT按 k的奇偶分解為兩個 N/4點的 DFT 如此進行下去 ,直至分解為 2點 DFT 1 1 1 1 1 1 1 1 1 1 1 1 )0(x)1(x)5(x)4(x)3(x)2(x)7(x)6(x)0(X)2(X)6(X)1(X)3(X)5(X)7(X)4(X1NW2NW3NW0NW2NW0NW0NW2NW0NW0NW0NW0NW第 4章 快速傅立葉變換（ FFT） 圖 DIF―FFT 一次分解運算流圖 (N=8) N /2 點D F TW N0N /2 點D F TW N1W N2W N3X ( 0 )x1( 0 )X ( 2 )X ( 4 )X ( 6 )X ( 1 )X ( 3 )X ( 5 )X ( 7 )x1( 1 )x1( 2 )x1( 3 )x2( 0 )x2( 1 )x2( 2 )x2( 3 )x ( 0 )x ( 1 )x ( 2 )x ( 3 )x ( 4 )x ( 5 )x ( 6 )x ( 7 )圖 DIF―FFT 二次分解運算流圖 (N=8) N /4 點D F TW N0W N1W N2W N3x ( 0 )x ( 1 )x ( 2 )x ( 3 )x ( 4 )x ( 5 )x ( 6 )x ( 7 )X ( 0 )X ( 4 )X ( 2 )X ( 6 )X ( 1 )X ( 5 )X ( 3 )X ( 7 )W N0W N2W N0W N2N /4 點D F TN /4 點D F TN /4 點D F T圖 DIF―FFT 運算流圖 (N=8) W N0W N1W N2W N3W N0W N2W N0W N2W N0W N0W N0W N0X ( 0 )X ( 4 )X ( 2 )X ( 6 )X ( 1 )X ( 5 )X ( 3 )X ( 7 )x ( 0 )x ( 1 )x ( 2 )x ( 3 )x ( 4 )x ( 5 )x ( 6 )x ( 7 ) ?FFT算法的特點 ?分級運算 ?同址運算 ?倒序輸入，順序輸出 (DIT),正序輸入，倒序輸出 (DIF) ?DITFFT蝶形先乘后加 (減 )，而 DIF FFT蝶形先加 (減 )后相乘。 由