第四章快速傅里叶变换 §4-3按时间抽取(DT的FFT算法( Cooley- Tukey算法 - Tukey X(,+k)=X(k)+x2(k) N W32=e=-10≤k≤--1 2 X(k) -,(k) 0sk≤-1 归纳起来有 X(k)=X1(k)+WX2(k)k=02 (4-13) X(N+6)=X()+x:()k=012-1(4-14) 可见, DET w-DET N-DFT DFT) ( ) ( ) 2 ( 2 ) 2 1 k X k W X k N X k N N + + = + 1 2 1 0 2  = = −   − N W e k j N N   归纳起来有 1 (4 -14) 2 ) ( ) ( ) 0,1,..., 2 ( 1 (4 -13) 2 ( ) ( ) ( ) 0,1,..., 1 2 1 2 + = + = − = + = − N k X k W X k k N X N X k X k W X k k k N k N 第四章 快速傅里叶变换 §4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法) 1 2 = 1 ( ) − 2 ( ) 0   − N X k W X k k k N 可见， N −DFT DFT N − 2 DFT N − 2 N −DFT