【正文】 X x x W x xX x x W x x? ? ? ?? ? ? ?? ? ? ?? ? ? ?04 4 4 / 414 4 4 / 4( 0 ) ( 0 ) ( 1 ) ( 2 ) ( 6 )( 1 ) ( 0 ) ( 1 ) ( 2 ) ( 6 )NNX x x W x xX x x W x x? ? ? ?? ? ? ? N點 DIT―FFT 運算流圖 (N=8) 所以， N=8點的 DITFFT運算流圖如圖所示： 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 1 ( 0 ) A ( 0 )A ( 7 )X ( 0 )X ( 1 )X ( 2 )X ( 3 )X ( 4 )X ( 5 )X ( 6 )X ( 7 )3( 0 )x3( 1 )x4( 0 )x4( 1 )x5( 0)x5( 1 )x6( 0 )x6( 1 )x3( 0 )X3(1)X4( 0 )X4( 1 )X5( 0 )X5( 1 )X6( 0 )X6( 1 )XX 1 ( 1 )X 1 ( 2 )X 1 ( 3 )X 2 ( 0 )X 2 ( 1 )X 2 ( 2 )X 2 ( 3 )DIT―FFT 算法與直接計算 DFT運算量的比較 從圖可看出當 N=2M時，要經(jīng)過 M級蝶算，每一級蝶算包含 N/2個蝶形運算，所以總共需要的蝶形運算為： 每個蝶形運算需要一次復(fù)數(shù)乘和兩次復(fù)數(shù)加法。所以 N點的 FFT需要： 個復(fù)數(shù)乘， 個復(fù)數(shù)加。 例如， N=210=1024時， DFT與 FFT復(fù)數(shù)乘法運算之比為： 2lo g22NNMN??2log2N N 2lo gN M N N??221048576 2 0 4 . 8( / 2) l o g 5 1 2 0NNN ?? 其中： Cxm 1( p )xm 1( q )xm( p )xm( q )11( ) ( ) ( )( ) ( ) ( )rm m N mrm m N mX p X p W X qX q X p W X q??????算法流圖規(guī)律 1)、 原位計算 在 FFT信號流圖中，每一級里節(jié)點是成對出現(xiàn)的。如圖所示： 可看出第 m1級的兩節(jié)點 xm1(p), xm1(q) ，經(jīng)蝶算后，在 m級中的節(jié)點序號是不變的，即 xm(p), xm(q) 。且蝶算自成獨立單元。即 xm(p), xm(q) 只與 xm1(p), xm1(q)有關(guān)，而與其它節(jié)點值無關(guān)，同時 xm1(p), xm1(q)也不再參加其它的蝶算。所以可以將計算出來的結(jié)果存入原來的單元。而不需要開辟新的地址存放計算結(jié)果。這種運算稱為 原位運算 ?？梢源蟠蟮墓?jié)省存儲單元，減少成本。 其中： p為對偶節(jié)點中上節(jié)點的序號 q為對偶節(jié)點中下節(jié)點的序號 在對偶節(jié)點中，只有下節(jié)點 Xm(q)才乘加權(quán)因子 2 mqp??1 ( 1 )2 2 2mmN N qrp?? ? ?2).旋轉(zhuǎn)因子的變化規(guī)律 同一級中參加蝶算的兩節(jié)點間的間距是相同的。 對偶節(jié)點的間距可用下式確定： m為該級的序號 r可由下式確定： 若 ,則數(shù)據(jù)不必交換。如： 010 若 ,則須將 x(n)與 x( )對調(diào)。 為了避免重復(fù)對調(diào)，需要檢查 是否小于 n，若 n ,說明x(n)已與 x( )調(diào)換過。只有當 n 時，才將 x(n)與 x( )的存放單元對換。如圖所示： nnn?nn? nn nn n n3)、 碼位整序 通常將 x(n)按順序輸入，通過變址運算，得到它的倒序排列。 整序過程為：（設(shè) N=8） 若輸入序列 x(n)的序號 n用二進制數(shù) n2 n1 n0表示，則其反序二進制數(shù) 表示為 n0 n1 n2 即： 001→100 x ( 0 ) x ( 1 ) x ( 2 ) x ( 3 ) x ( 4 ) x ( 5 ) x ( 6 ) x ( 7 )A ( 0 ) A ( 1 ) A ( 2 ) A ( 3 ) A ( 4 ) A ( 5 ) A ( 6 ) A ( 7 )A ( 0 ) A ( 1 ) A ( 2 ) A ( 3 ) A ( 4 ) A ( 5 ) A ( 6 ) A ( 7 )x ( 0 ) x ( 4 ) x ( 2 ) x ( 6 ) x ( 1 ) x ( 5 ) x ( 3 ) x ( 7 )2. 基 2頻域抽取 FFT算法 (DIF―FFT ) 在基 2快速算法中，頻域抽取法 FFT也是一種常用的快速算法，簡稱 DIF―FFT 。 設(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ù)組，當 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????? ? ?? ? ? ? ???當 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點的 DFT，分成偶、奇兩部分的N/2點的 DFT 圖 DIF―FFT 一次分解運算流圖 (N=8) N / 2 點D F TW N0N / 2 點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點的 DFT分解成兩個 N/4點的DFT 圖 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 ) 圖 DIT―FFT 的一種變形運算流圖 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 的一種變形運算流圖 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)。比較 DFT和 IDFT的運算公式： 1010( ) [ ( ) ] ( )1( ) [ ( ) ] ( )NknNnNknNkX k D FT x n x n Wx n I D FT x n X k WN???????????101( ) ( )N knNkx n X k WN????? ?對上式求共軛： 所以 由 X(K)求 x(n)的 IFFT算法 如下： 求 X(K)的共軛 X*(K) 求 X*(K)的 FFT，得 N*x*(n) 取 x*(n)的共軛并除以 N，即得 x(n)。 兩邊再同時取共軛，得 ? ?1011( ) [ (