《数字信号处理》课程教学课件（2020讲稿）第四章 快速傅里叶变换 §4-3 按时间抽取（DIT）的FFT算法（Cooley-Tukey算法）

S 4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法)N-+k)利用W的周期性，W2=WN1222N.-)N-+k）N2X(k+=)Zx(r)W))=212r=0N-IZx(r)wrkN-2r=0N(4-10)0≤k≤= X,(k),2NN同理有，X,(k+-0≤k≤ = X2(k),(4-11)22[可见X,(k)和X,(k)的后半部分完全重复了各自的前半部分]代入(4-7)式，有:

rk WN 2 利用 的周期性， ) 2 ( 2 2 k N r N rk WN W         1 2 0 ) 2 ( 2 1 1 ) ( ) 2 ( N r k N r WN x r N X k     1 2 0 2 1 ( ) N r rk WN x r [ ( ) ( ) ] 可见X1 k 和X2 k 的后半部分完全重复了各自的前半部分 代入(4-7)式，有: 1 2  1 ( ), 0    N X k k (4-10) 同理有， 1 2 ) ( ), 0 2 (2   2    N X k k N X k (4-11) §4-3 按时间抽取(DIT)的FFT算法 (Cooley-Tukey算法)

S 4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法)N= X,(k)+W?"X(k)+kNN1:W =ejn =-10≤k≤2N0≤k≤1= X,(k)-WkX2(k)2归纳起来有Nk = 0,1(4-13)X(k) = X,(k)+WkX,(k)2N-+k) = X,(k)-WkX,(k)k =0,1(4-14)2一NDFT可见，2N-DFTN-DFTNDFT2

1 2 1 0 2        N W e k j N N   归纳起来有 1 2 1 2 ( ) ( ) ( ) 0,1,., 1 (4-13) 2 ( ) ( ) ( ) 0,1,., 1 (4-14) 2 2 k N k N N X k X k W X k k N N X k X k W X k k          1 2  1 ( )  2 ( ) 0    N X k W X k k k N 可见， N  DFT DFT N  2 DFT N  2 N  DFT §4-3 按时间抽取(DIT)的FFT算法 (Cooley-Tukey算法) 2 1 2 ( ) ( ) ( ) 2     N k N N X k X k W X k

S 4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法)上述运算可用下列蝶形信号流图表示X,(k)X(k)= X,(k)+WkX2(k)WkNX,(k)X(-+k)= X,(k)-WkX2(k土运算符图4-1蝶形运算流图符号

上述运算可用下列蝶形信号流图表示:   ( ) 1 X k 2 X k( ) ( ) ( ) ( ) 1 2 X k X k W X k k   N ) ( ) ( ) 2 ( 1 2 k X k W X k N X k    N k WN 运算符 图 4-1 蝶形运算流图符号 §4-3 按时间抽取(DIT)的FFT算法 (Cooley-Tukey算法)

S 4-3按时间抽取(DIT)的FFT算法(Cooley-Tukey算法)例：N=8NWk,k=012x (0) = x(0)X(0)x,(1) = x(2)N/2-X(1)x(n)DFTx(2) = x(4)X(2)x (3) = x(6)X(3)Wx2(0) = x(1)X(4)W!N/2-x2(1) = x(3)X(5)W?x(n)DFTx2(2) = x(5)X(6)Wx2(3) = x(7)X(7)

例：N=8 1 1 1 1 1 (0) (0) (1) (2) ( ) (2) (4) (3) (6) x x x x x n x x x x            2 2 2 2 2 (0) (1) (1) (3) ( ) (2) (5) (3) (7) x x x x x n x x x x            (3) (2) (1) (0) X X X X (7) (6) (5) (4) X X X X N/2- DFT N/2- DFT 3 2 1 0 N N N N W W W W 1 2 ,  0,1,.,  N W k k N §4-3 按时间抽取(DIT)的FFT算法 (Cooley-Tukey算法)