Cooley Tukey FFT算法

Cooley-Tukey FFT是所有FFT算法中最为通用的,因为IV可以任意地进行因数分解。最流行的Cooley-Tukey FFT就是变换长度N是r基的幂的形式,也就是N=rv。这些算法通常称作r基算法。 Cooley和Tukey(更早是Gauss)提出的索引变换也是最简单的索引映射。令A=N2和B=1就得到下面的映射结果: 从n1和n2的正确范围可以得出结论。 Cooley和Tukey选择C=1和D=N1,就得到下面的映射结果: 在这种情况下也可以省略模计算。这时候如果根据(6.20)式和(6.21)式分别将n和k代入WnkN就会得到: 由于W是N