第四章快速傅里叶变换 §4-3按时间抽取(DT的FFT算法( Cooley- Tukey算法) 、算法原理 Vx(n),0≤n≤N-1,N=2(若N≠2",可通过补零达到) FFT→基-2FFT/即N为2的整数幂的FFT 由FF7的定义: M1)=∑xm如k=01.…,N-1(4-4) 2x1(m) DFT N-x(n) DFT ?N-x(n) DFT一、算法原理  x(n), 0  n  N −1, 2 (若 2 ，可通过补零达到)   N = N  - 2 / 2 FFT FFT → 基 FFT 即N为 的整数幂的  01 1 (4 - 4) : 1 0  − = = = − N n kn N X(k) x(n)W k , , ,N FFT  由 的定义 DFT N x n − ( ) x n DFT N ( ) 2 − 1 x n DFT N ( ) 2 − 2 ? 第四章 快速傅里叶变换 §4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法)