【正文】 ，用于 IDFT運算時，由于輸入變量由時間序列 x(n)改成頻率序列 X(k)， 原來按x(n)的奇、偶次序分組的時間抽取法 FFT，現(xiàn)在就變成了按 X(k)的奇偶次序抽取了。 第 4章 快速傅立葉變換（ FFT） 圖 DIT―IFFT 運算流圖 W N0W N1?W N2?W N3?W N0W N0N1x ( 0 )x ( 4 )x ( 2 )x ( 6 )x ( 4 )x ( 5 )x ( 3 )x ( 7 )X ( 0 )X ( 1 )X ( 2 )X ( 3 )X ( 4 )X ( 5 )X ( 6 )X ( 7 )W N2?W N2?N1N1N1N1N1N1N1第 4章 快速傅立葉變換（ FFT） 圖 DIT―IFFT 運算流圖 (防止溢出 ) WN02121 x ( 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 )212121WN121?WN221?WN321?2121WN021WN221?2121WN021WN221?21WN02121WN0212121WN021WN021第 4章 快速傅立葉變換（ FFT） nkNNkWkXNnx ?????10)(1)(此 DFT可用 FFT程序 ? 利用 FFT計算 IFFT的思路 2 nkNNkWkXNnx ????10* )(1)(＊取共軛再取共軛）(])([1)( *10* nkNNkWkXNnx ?????** )]}([{1 kXD F TN?直接調(diào)用 FFT子程序計算 IFFT的方法： 共軛 FFT 共軛 乘 1/ N ()Xk*()Xk ()xn第 4章 快速傅立葉變換（ FFT） 1)0( ＝x1)2( －?x2)1( ?x3)3( ?x5)0( ?XjX ?? 2)1(5)2( ??XjX ?? 2)3(2)1(0)0(11＝＝XX1)1(5)0(22???XX04WjW ??141 1 04W1 04W1 例：有限長序 x(n)={1,2,1,3}按 FFT運算流圖求 X(k)，在由 X(k) 按 IFFT反求 x(n) DFT過程： 第 4章 快速傅立葉變換（ FFT） 1)0( ＝x1)2( －?x2)1( ?x3)3( ?x5)0( ?XjX ?? 2)1(5)2( ??XjX ?? 2)3(10)1(0)0(11＝＝xxjxx2)1(4)0(22??IDFT過程： 04WjW ?14－1 1 04W1 04W1 1/4 1/4 1/4 1/4 第 4章 快速傅立葉變換（ FFT） 由 DITFFT運算流圖已得出結(jié)論， N=2M點 FFT共需要MN/2次復(fù)數(shù)乘法。當 L=2 時，共有兩個旋轉(zhuǎn)因子： 和 ，因此，第二級也不需要乘法運算。 1和 177。 10 ?NW10 ?NWjW NN ??4/0NW2/NNW4/NNW 進一步減少運算量的措施 多類蝶形單元運算 第 4章 快速傅立葉變換（ FFT） 先除去第一、二兩級后，所需復(fù)數(shù)乘法次數(shù)應(yīng)是 0NW 4/NNW當 L=3時，有兩個無關(guān)緊要的旋轉(zhuǎn)因子 和 ，因為同一旋轉(zhuǎn)因子對應(yīng)著 2M－ L=N/2L個碟形運算，所以第三級共有2N/23=N/4 個碟形不需要復(fù)數(shù)乘法運算。 這樣，從 L=3至 L=M共減少復(fù)數(shù)乘法次數(shù)為 ( 2)2M NCM??() 第 4章 快速傅立葉變換（ FFT） () 222122331 ????????? ?????NNN MLLMLL 下面再討論 FFT中特殊的復(fù)數(shù)運算，以便進一步減少復(fù)數(shù)乘法次數(shù)。但對 這一特殊復(fù)數(shù)，任一復(fù)數(shù) (x+jy)與其相乘時， 2/2)1(8/ jW NN ??因此， DITFFT的復(fù)乘次數(shù)降至 ( 2 ) 2 ( 3 ) 22 2 2M N N NC M M??? ? ? ? ? ? ?????() 第 4章 快速傅立葉變換（ FFT） IRyxyxyxyxyxj)](j)[(22)jj(22)j)(j1(22d e f???????????)(22)(22)(22xyyxIyxR???????第 4章 快速傅立葉變換（ FFT） 只需要兩次實數(shù)加和兩次實數(shù)乘就可實現(xiàn)。因此從第三級至最后一級，旋轉(zhuǎn)因子 節(jié)省的實數(shù)乘次數(shù)與 ()式相同。 jW rN ??若再去掉 的旋轉(zhuǎn)因子，則稱為 三類碟形單元運算； 后三種運算稱為 多類碟形單元運算 。例如， N=4096時，三類碟形單元運算的乘法次數(shù)為一類碟形單元運算的 75% 第 4章 快速傅立葉變換（ FFT） ? 在 FFT運算中，旋轉(zhuǎn)因子 ?，求正弦和余弦函數(shù)值的計算量是很大的。 )/c o s ( NmπW mN 2? )/s in ( Nmπj 2? 旋轉(zhuǎn)因子的生成 ? 產(chǎn)生旋轉(zhuǎn)因子的方法 : ?1. 在每級運算中直接產(chǎn)生； mNW? FFT程序開始前預(yù)先計算出 ， m = 0， 1， … ， N/2－ 1， 存放在數(shù)組中，作為旋轉(zhuǎn)因子表，在程序執(zhí)行過程中直接查表得到所需旋轉(zhuǎn)因子值，不再計算 。如果直接按 FFT運算流圖計算，就是把 x(n)看成一個虛部為零的復(fù)序列進行計算，這就增加了存儲量和運算時間。 ?第二種方法是 用 N/2點 FFT計算一個 N點實序列的 DFT。 第 4章 快速傅立葉變換（ FFT） 設(shè) x(n)為 N點實序列，取 x(n)的偶數(shù)點和奇數(shù)點分別作為新構(gòu)造序列 y(n)的實部和虛部，即 12121222121?????????N10nnxjnxnyN10nnxnxnxnx，，??)()()()()()()(? ?? ?112212( ) D F T ( ) ( )0 , 1 ,( ) D F T ( ) ( )epopX k x n Y k NkX k x n jY k??? ????? ? ? ??對 y(n)進行 N/2點 FFT，輸出 Y(k)，則 用 N/2點 FFT計算一個 N點實序列的 DFT的原理： 第 4章 快速傅立葉變換（ FFT） 由于 x(n)為實序列，因此 X(k)具有共軛對稱性， X(k)的另外N/2點的值為： )0(2 ),0(2 2211 XNXXNX ??????????????1210)()( * ???? NkkXkNX ， ?12 ?N 根據(jù) DITFFT的思想及式 ()和 ()，可得到 X(k)的前 個值： 210)()()( 21NkkXWkXkX kN ， ????() 其中： 第 4章 快速傅立葉變換（ FFT） 計算 點 FFT的復(fù)乘次數(shù)為 ，計算式()的復(fù)乘次數(shù)為 ，所以用這種算法 , 計算 X(k)所需復(fù)數(shù)乘法次數(shù)為 。其他高效快速算法請讀者參考文獻［ 1］、［ 3］、［ 12］。本節(jié)簡要介紹其他幾種快速算法的運算量及其主 其他快速算法簡介 第 4章 快速傅立葉變換（ FFT） ? 從理論上講，不同基數(shù)的 FFT算法的運算效率不同，實際中最常用的是基 2FFT、基 4 FFT、分裂基 FFT和 DHT ［ 1］ 。其具體算法請參考文獻［ 1］、［ 12 ? 在基 rFFT算法中，基 4FFT算法運算效率與基 8FFT很接近，但基 4FFT算法實現(xiàn)程序簡單，且判斷開銷少?；?FFT要求 N=4M， M為自然數(shù)。 j和 1的計算 。 NNC M lb21)2( ? 1984年，法國的杜梅爾（ ）和霍爾曼（ H. Hollmann）將基 2分解和基 4分解糅合，提出了分裂基 FFT算法，其復(fù)數(shù)乘法次數(shù)接近 FFT理論最小值，但其運算流圖卻與基 2FFT很相似，編程簡單，運算程序也很短，是一種很實用的高效算法。應(yīng)當說明，在比較時，未考慮（ ）式后 2項減少的運算量，所以分裂基 FFT算法的效率更高。而一次復(fù)數(shù)乘法需要四次實數(shù)乘法和二次實數(shù)加法。我們知道，實序列的 N點 DFT具有共軛對稱性， 即 ? *( ) ( ) , 0 , 1 , 2 , , 1X N k X k k N? ? ? ?第 4章 快速傅立葉變換（ FFT） 所以，只要計算出 X（ k）的前面 N/2個值，則其后面的N/2個值可以由對稱性求得。 離散哈特萊變換（ DHT）就是針對實序列的一種高效變換算法， 相對一般的 FFT算法， DHT的快速算法FHT 可以減少近一半的計算量 ［ 1］ 。下面會看到該關(guān)系非常簡單。與前面三種 FFT算法比較，對實序列，基 2DITFHT算法的實數(shù)乘法次數(shù)最少。 (2) DHT的正、逆變換（除了因子 1/N外）具有相同的形式，所以實現(xiàn)硬件或程序亦相同。 所以對實信號 x(n)進行譜分析時，可以先對 x(n)進行 FHT, 得到 XH(k)=DHT[x(n)]N,然后再將Ｘ H(k)轉(zhuǎn)換成 X(k)=DFT[x(n)]N，這樣可以提高分析速度，減少存儲