【正文】 兩邊再同時取共軛，得 ? ?1011( ) [ ( ) ]。 設(shè)序列 x(n)的長度為 N=2M，將 x(n)前后對半分開，得到兩個子序列，其 DFT可表示為如下形式： 10/ 2 1 10 / 2/ 2 1 / 2 1( / 2 )00/ 2 1/20( ) [ ( ) ] ( )( ) ( )( ) ( )2[ ( ) ( ) ]2NknNnNNk n k nNNn n NNNk n k n NNNnnNk N k nNNnX k D FT x n x n Wx n W x n WNx n W x n WNx n W x n W?????????????????? ? ?? ? ??????? 將 X(k)分解成偶數(shù)組與奇數(shù)組，當(dāng) k取偶數(shù) (k=2r, r=0,1,… ,N/21)時 /2 1,( 1 )1k N kNkWk???? ? ?? ????偶奇/ 2 120/ 2 1/20( 2 ) [ ( ) ( ) ]2[ ( ) ( ) ] 0 , 1 , , 122NrnNnNrnNnNX r x n x n WNNx n x n W r????? ? ?? ? ? ? ???當(dāng) k取奇數(shù) (k=2r+1,r=0,1,… ,N/21)時 / 2 1 ( 2 1)0/ 2 1/20( 2 1 ) [ ( ) ( ) ]2[ ( ) ( ) ]2NnrNnNn nrNNnNX r x n x n WNx n x n W W?????? ? ? ?? ? ???12( ) ( ) ( / 2 )( ) [ ( ) ( / 2 ) ] 0 , 1 , , / 2 1nNx n x n x n Nx n x n x n N W n N? ? ?? ? ? ? ?/ 2 11 / 20/ 2 12 / 20( 2 ) ( )( 2 1 ) ( )NrnNnNrnNnX r x n WX r x n W?????????? ??????令： 則： 所以在頻域按 K將一個 N點(diǎn)的 DFT，分成偶、奇兩部分的N/2點(diǎn)的 DFT 圖 DIF―FFT 一次分解運(yùn)算流圖 (N=8) N / 2 點(diǎn)D F TW N0N / 2 點(diǎn)D F TW N1W N2WN3X ( 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 )同樣還可繼續(xù)分解，將 N/2點(diǎn)的 DFT分解成兩個 N/4點(diǎn)的DFT 圖 DIF―FFT 二次分解運(yùn)算流圖 (N=8) N /4 點(diǎn)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 點(diǎn)D F TN /4 點(diǎn)D F TN /4 點(diǎn)D F T 圖 DIF―FFT 運(yùn)算流圖 (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 ) 圖 DIT―FFT 的一種變形運(yùn)算流圖 W N0W N0W N2W 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 )W N0W N2W N1W N3W N2W N0W N0W N0 圖 DIT―FFT 的一種變形運(yùn)算流圖 W N0W N0W N2W N0X ( 0 )X ( 1 )X ( 2 )X ( 3 )X ( 4 )X ( 5 )X ( 6 )X ( 7 )x ( 0 )x ( 1 )x ( 2 )x ( 3 )x ( 4 )x ( 5 )x ( 6 )x ( 7 )W N0W N2W N1W N3W N2W N0W N0W N03. IDFT的高效算法 上述 FFT算法流圖也可以用于離散傅里葉逆變換(Inverse Discrete Fourier Transform，簡稱 IDFT)。如圖所示： nnn?nn? nn nn n n3)、 碼位整序 通常將 x(n)按順序輸入，通過變址運(yùn)算，得到它的倒序排列。 為了避免重復(fù)對調(diào)，需要檢查 是否小于 n，若 n ,說明x(n)已與 x( )調(diào)換過。 對偶節(jié)點(diǎn)的間距可用下式確定： m為該級的序號 r可由下式確定： 若 ,則數(shù)據(jù)不必交換?？梢源蟠蟮墓?jié)省存儲單元，減少成本。而不需要開辟新的地址存放計算結(jié)果。即 xm(p), xm(q) 只與 xm1(p), xm1(q)有關(guān)，而與其它節(jié)點(diǎn)值無關(guān)，同時 xm1(p), xm1(q)也不再參加其它的蝶算。如圖所示： 可看出第 m1級的兩節(jié)點(diǎn) xm1(p), xm1(q) ，經(jīng)蝶算后，在 m級中的節(jié)點(diǎn)序號是不變的，即 xm(p), xm(q) 。所以 N點(diǎn)的 FFT需要： 個復(fù)數(shù)乘， 個復(fù)數(shù)加。兩個 N/2點(diǎn)的 DFT需要 2 (N/2)2＝ N2/2次復(fù)數(shù)乘 ,可見，分解后運(yùn)算量大約節(jié)省了一倍。 由于 X1(k)和 X2(k)均以 N/2為周期，且 ， 而 X(k)為 N點(diǎn) 所以： / 2 11 1 / 2 10/ 2 12 2 / 2 20( ) ( ) [ ( ) ]( ) ( ) [ ( ) ] 0 , , / 2 1NkrNrNkrNrX k x r W D F T x rX k x r W D F T x r k N??????? ? ? ???2Nk kNNWW? ??/21212( / 2 ) ( / 2 ) ( / 2 )( ) ( )kNNkNX k N X k N W X k NX k W X k?? ? ? ? ???其中 X1(k)和 X2(k)分別為 x1(r)和 x2(r)的 N/2點(diǎn) DFT，即 用信號流圖表示： 1212( ) ( ) ( ) 0 , 1 , 12( ) ( ) ( ) 0 , 1 , 122kNkNNX k X k W X k kNNX k X k W X k k? ? ? ? ? ? ?? ? ? ? ? ? ? ?X(k)可表示為 )(1 kX)(2 kXkNW)()( 21 kXWkX kN?)()( 21 kXWkX kN?蝶形運(yùn)算流圖符號 ∵ 呈蝶形， ∴ 稱為 蝶形計算結(jié)構(gòu) ，是 FFT運(yùn)算中的一個基本單元 N /2 點(diǎn)D F TW N0N /2 點(diǎn)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 )可將上述分解過程用計算流圖來表示。 基 2時 域 抽取 (Decimation in time)FFT算法 基 2頻率抽取 (Decimation in frequency)FFT算法 12,1,0]12[ ]2[][ ???????Nrrxrxkx ?nr r k 1 基 2時域抽取 FFT算法（ DITFFT） 設(shè)： x(n)為一長度為 N的序列。其周期性表現(xiàn)為 10( ) ( ) , 0 , 1 , , 1NknNnX k x n W k N??? ? ??? ?? 應(yīng)用了上述性質(zhì)后，獨(dú)立的值只有 N/2個，為簡化DFT的運(yùn)算提供了有力的依據(jù)。所以直接計算 DFT的計算量與 N的平方成正比，當(dāng) N較大時，計算量太大。 直接計算 DFT的特點(diǎn) 設(shè) x(n)長度為 N，其 DFT為： X(K),長度也為 N 1010( ) ( ) , 0 , 1 , , 11( ) ( ) , 0 , 1 , , 1NknNnNknNkX k x n W k Nx n X k W n NN?????? ? ? ? ? ?? ? ? ? ? ???一、 DFT運(yùn)算的特點(diǎn) 可看出正、反變換形式上很相似 , 所以只討論正變換 運(yùn)算時間： 設(shè)： x(n)為復(fù)數(shù)序列，計算一個 X(K)值需要 N次復(fù)數(shù)乘 及N1次復(fù)數(shù)加 。)kN jnNmnkX x n em?? ??? ?11 2200( ) ( ) ( )kkmm j r j rmmMrrkkX k X e X emm???? ????????而 1 20/0/km jrmrm k mekm?? ???? ???為 整 數(shù)不 為 整 數(shù)( ) /()0/Mkm X k mXk mkm??? ???為 整 數(shù)不 為 整 數(shù)如： x(n)=cos(nπ/6) 0 1 2 11x ( n )n 0 1X ( k )11 nN=12時的 DFT N=24時的 DFT 6N=16時的 DFT 快速傅里葉變換 (FFT) 頻譜分析在數(shù)字信號處理中用途廣泛：如通過語言信號的頻譜分析實(shí)現(xiàn)語音通訊的頻帶壓縮、聲納信號的頻譜分析用以區(qū)分水面與水下目標(biāo)、在各種測量儀器中，頻譜分析用得更多，這些都需要 DFT運(yùn)算。39。 0( ) ( 39。)kkmN j n j rN m mrnx n e e? ??? ????? ??211 ( 39。20 39。 0( ) ( 39。 0 , 1 , , 1n n r N r m n N? ?