第四章快速傅里叶变换 §4-3按时间抽取(DT的FFT算法( Cooley- Tukey算法) 例:N=8 W,h=01 x1(0)=X X(0) x1(1)=X(2 x1(n) N/2 X￥(1) x1(2)=X(4) DET X(2) x1(3)=X(6) X(3) X2(0)=X(l) X(4) x2(1)=X(3) N/2 W2 X(5) X2(2)=X(5).DFT X(6) W X2(3)=X(7) X(7)
例：N=8 = = = = (3) (6) (2) (4) (1) (2) (0) (0) ( ) 1 1 1 1 1 X X X X X X X X X n = = = = (3) (7) (2) (5) (1) (3) (0) (1) ( ) 2 2 2 2 2 X X X X X X X X X n (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算法)
第四章快速傅里叶变换 §4-3按时间抽取(DT的FFT算法( Cooley- Tukey算法 计算量分析: 相比NDFT的 N NN 2 * N N(N-1) NN +:2× 1/+=2 运算量减小了一半。 2人2 ∵N=2 N 一2-DFT 2-1=2×2"-2 2-DET N DFT 2-DET DET 2-DET DFT< 2-DFT 2-DFT
计算量分析： 2 1 2 2 2 2 2 2 2 2 2 2 N N N N N N N + = − + + = ： ： 相比N-DFT的 ( 1) * 2 + N N − N ： ： 运算量减小了一半。 第四章 快速傅里叶变换 §4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法) 2 2 1 = − N DFT N − 2 DFT N − 4 DFT N − 4 2 − DFT 2 − DFT 2 − DFT 2 − DFT 2 − DFT 2 − DFT 1 2 2 2 2 2 2 − − = = = N N
第四章快速傅里叶变换 §4-3按时间抽取(DT的FFT算法( Cooley- Tukey算法 2-DFT X(k)=∑xOn)W2 =x(0形2+x(1)W2k=0,1 X(0)=xO)+x()=xO0+x()x0.、X(O) X()=x(0)-x(1)=x(0)-Wx(1)x()的x() 可见仅需计算“+/-”运算
2-DFT： = = 1 0 2 ( ) ( ) n kn X k x n W (0) (1) 2 0,1 0 = x W2 + x W k = k (0) (0) (1) (0) (1) 0 X x x x W x = + = + N (1) (0) (1) (0) (1) 0 X x x x W x = − = − N 可见仅需计算“+/-”运算。 x(0) x(1) X (0) X (1) 0 WN 第四章 快速傅里叶变换 §4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法)
第四章快速傅里叶变换 §4-3按时间抽取(DT的FFT算法( Cooley- Tukey算法 例:N=8(P129) x(0) x(4) x() x(2) x(2) W x(6) x(3) x(4) XO5 x(3) x() x() X() 图4-5N=8时的按频率抽取FFT运算流图
例：N=8 (P129) 第四章 快速傅里叶变换 §4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法) 图4-5 N=8时的按频率抽取FFT运算流图
第四章快速傅里叶变换 §4-3按时间抽取(DT的FFT算法( Cooley- Tukey算法 例:N=2(P130) 第1级 第2级 第3级 第v级 2点DFT 两个2点 DFT 2点DFT 组合 两个4点 DFT 2点DFT 两个2点 DFT 组合x()两个 2点DFT 组合 点 X(k) 组合 2点DFT 两个2点 DFT x2(k) 2点DF 组合 两个4点 DFT 组合 2点DFT 两个2点 DFT 2点DFT 组合 图45N点基2FFT的v级迭代过程
例：N=2v _ (P130) 第四章 快速傅里叶变换 §4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法) 图4-5 N点基-2FFT的ν级迭代过程