【正文】 整序過程為：（設 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 。這種運算稱為 原位運算 。 那么， X1(k)又可表示為 3141( ) ( 2 ) , 0 , 1 , , 1( ) ( 2 1 ) 4x l x l Nlx l x l? ? ? ? ? ? ???? ?1 3 / 2 41 3 / 2 4( ) ( ) ( ) , 0 , 1 , , / 4 1( / 4) ( ) ( )kNkNX k X k W X k kNX k N X k W X k??? ? ? ? ? ? ??? ? ???/ 4 13 3 / 4 30/ 4 14 4 / 4 40( ) ( ) [ ( ) ]( ) ( ) [ ( ) ]NklNlNklNlX k x l W D F T x lX k x l W D F T x l??????????與第一次分解相同，將 x1(r)按 r的奇偶分解成兩個 N/4長的子序列 x3(l)和 x4(l)，即 式中 1212( ) ( ) ( ) 0 , 1 , 12( ) ( ) ( ) 0 , 1 , 122kNkNNX k X k W X k kNNX k X k W X k k? ? ? ??? ?? ? ? ? ??? ?)0(x)2(x)4(x)6(x)0(3X)0(1X)1(1X)2(1X)3(1X)1(3X)0(4X)1(4X02/NW12/NWN/4 點 DFT N/4 點 DFT 分解圖如圖所示 : 將一個 N/2點的 DFT分解為兩個 N/4點的 DFT 用同樣的方法將 x2(r)分解成兩個 N/4長的子序列 x5(l)和 x6(l)， 5262( ) ( 2 ) , 0 , 1 , , 1( ) ( 2 1 ) 4x l x l Nlx l x l? ? ? ? ? ? ???? ?2 5 / 2 62 5 / 2 6( ) ( ) ( ) , 0 , 1 , / 4 1( / 4 ) ( ) ( )kNkNX k X k W X k kNX k N X k W X k??? ? ? ? ? ? ??? ? ? ??/ 4 15 5 / 4 50/ 4 16 6 / 4 60( ) ( ) [ ( ) ]( ) ( ) [ ( ) ]NklNlNklNlX k x l W D F T x lX k x l W D F T x l??????????那么， X2(k)可表示為 其中 N點 DFT的第二次時域抽取分解圖 (N=8) 一個 8點 DFT就可分解為四個 2點的 DFT，如圖所示 N / 4 點DF TWN12WN12W N0W N1W N2W N3X1( 0 )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 ( 0 )X3( 0 )X3( 1 )X4( 0 )X4( 1 )x ( 4 )x ( 2 )x ( 6 )x ( 1 )x ( 5 )x ( 3 )x ( 7 )N / 4 點DF TN / 4 點DF TN / 4 點DF TWN02WN02X5( 0 )X5( 1 )X6( 0 )X6( 1 ) / 4 13 3 / 40( ) ( ) 0 , 1N klNlX k x l W k?????03 3 3 / 413 3 3 / 4( 0 ) ( 0 ) ( 1 ) ( 0 ) ( 4 )( 1 ) ( 0 ) ( 1 ) ( 0 ) ( 4 )NNX x x W x xX x x W x x? ? ? ?? ? ? ?兩點 DFT 若 N=8，則： 05 5 5 / 415 5 5 / 406 6 6 / 416 6 6 / 4( 0) ( 0) ( 1 ) ( 1 ) ( 5 )( 1 ) ( 0) ( 1 ) ( 1 ) ( 5 )( 0) ( 0) ( 1 ) ( 3 ) ( 7 )( 1 ) ( 0) ( 1 ) ( 3 ) ( 7 )NNNNX x x W x xX x x W x xX 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個蝶形運算，所以總共需要的蝶形運算為： 每個蝶形運算需要一次復數(shù)乘和兩次復數(shù)加法。 knNW22 ()()j k n j k n Nk n k n NNNNNn n NNNW e e WWW??? ? ???? ? ??即 ： 提高 DFT運算效率的依據(jù) ： 具有 周期性 和 對稱性 。 )mN j k n r NmNMrnX k x n r N e??? ????????令： 21 39。 )0 39。 截斷效應 例： 試利用 DFT分析一連續(xù)信號 ， 已知其最高頻率 =1000Hz， 要求頻率分辨率 F?2Hz， DFT的點數(shù)必須為 2的整數(shù)冪次 ， 確定以下參數(shù)：最大的抽樣間隔 ， 最少的信號記錄時間 ， 最少的 DFT點數(shù) 。 將x(n)均勻分成長度為 M的若干段，表示為： 0( ) ( )PkkLx n x n PM????000( ) ( ) ( ) ( ) ( )( ) ( ) ( )PkkPPkkkky n h n x n h n x nh n x n y n???? ? ? ?? ? ????( ) ( ) ( )kMx n x n R n k M? ? ?重疊相加法 : 可看出，每一項 的長度為 N+M1，大于序列分段 的長度 M ( ) ( )kh n x n?()kxn 所以卷積結(jié)果求和時，每段卷積最后 N1個點和下一段的最前面的 N1個點重合，重合相加，可得到最后結(jié)果。 圓周卷積 DFT 乘積 線性卷積 FT 乘積 而 圓周卷積比起線性卷積，在運算速度上有很大的優(yōu)越性，它可以采用離散傅立葉變換的乘積實現(xiàn)，而快速付里葉變換（ FFT）技術(shù)又大大提高了離散傅立葉變換的計算速度，所以利用圓周卷積求線性卷積 . 用 DFT計算線性卷積 設： x (n)、 h(n)為兩個有限長序列，其長度分別為 N1和 N2，線性卷積的定義為： 1 1120( ) ( ) * ( ) ( ) ( ) 0 2Nmly n x n h n h m x n m n N N??? ? ? ? ? ? ??而循環(huán)卷積的定義：要求 L≥max(N 1,N2) 即 yc(n)的長度為 L。 令： 11011()1( ) ( ) ( )Nk kNNkkzzN W zX z X k z??????????? ?內(nèi)插函數(shù) 2110111( ) ( )1j k NkN NNNNkk NWezX z X kN W z???????????????1111)(???????zWzNz kNNk稱為內(nèi)插函數(shù)。 時域抽樣定理 和 頻域抽樣定理 為利用數(shù)字化方式 分析和處理信號奠定了理論基礎(chǔ)。 選頻性 設有復序列 x(n): 0≤n≤N1 其離散付里葉變換為 其中 q為整數(shù)。 圖中 *表示對應點為序列取共軛后的值。如圖所示 ( ) ( )j j nnX e x n e??? ????? ?X(k)與 X(e jω)的關(guān)系 ( 1 ) / 2 s in ( / 2 )()s in / 2j j N NX e e?? ?????38si n( )2( ) ,si n( )80 , 1 , , 7jkkX k ekk?????? ???316si n( )4( ) ,si n( )160 , 1 , , 15jkkX k ekk?????? ???DFT DFT矩陣表示 DFT矩陣形式為 其中 DFT IDFT矩陣形式為 dftmtx(N) 函數(shù)產(chǎn)生 N N的 DFT矩陣 DN conj(dftmtx(N))/N 函數(shù)產(chǎn)生 N N的 IDFT矩陣 DN1 DFT 利用 MATLAB計算 DFT fft(x) fft(x,N) ifft(x) ifft(x,N) fft(x) 計算 M點的 DFT。離散傅里葉變換 (DFT) 及其快速算法 DFT的定義 DFT的主要性質(zhì) 頻域采樣 快速傅里葉變換（ FFT） FFT應用 圖 41 各種形式的傅里葉變換 xa( t )