Cooley－Tukey FFT算法

　　Cooley－Tukey FFT是所有FFT算法中为通用的，因为Ⅳ可以任意地进行因数分解。的Cooley-Tukey FFT就是变换长度N是r基的幂的形式，也就是N＝r^v。这些算法通常称作r基算法。

　　Cooley和Tukey（更早是Gauss）提出的索引变换也是简单的索引映射。令A＝N₂和B＝1就得到下面的映射结果：

　　从n₁和n₂的正确范围可以得出结论。

　　Cooley和Tukey选择C＝1和D＝N₁，就得到下面的映射结果：

　　在这种情况下也可以省略模计算。这时候如果根据（6．20）式和（6．21）式分别将n和k代入W^nk_N就会得到：

　　由于W是N＝N₁N₂阶的。就可以得到W^N1_N＝W_N2和W^N2_N＝W_N1，将（6．22）式简化成：

　　这时将就得到：

　　现在定义完整的Cooley－Tukey算法：

　　接下来用长度为12的变换来说明这些步骤。

　　例 N＝12的Cooley－Tukey FFT

　　假设N1＝4和N2＝3。则有n＝3n1＋n2和k=k1＋4k2，为索引映射计算下面的表：

　　在这个变换的帮助之下，可以构造如图所示的信号流程图。可以看到，首先必须用4个点计算3个DFT中的每一个，然后乘以旋转因子，计算4个DFT，其中每个的长度都是3。

　　图 N12的Cooley-Tukey FFT

　　要直接计算12点的DFT，总共需要12²＝144次复数乘法和11²＝121次复数加法。要计算同样长度的Cooley－Tukey FFT，旋转因子需要12次复数乘法，其中8次是无关紧要的乘法（也就是±1或与）。用8次实数加法就可以计算长度为4的DFT，而且不需要乘法。要计算长度为3的DFT，则需要4次乘法和3次加法。如果要用3次加法和3次乘法实现（固定系数的）复数乘法，12点Cooley－Tukey FFT的总工作量是：

　　而直接实现则需要2×11²＋12²×3＝674次实数加法和12²×3＝432次实数乘法。现在就应该非常清楚为什么将Cooley-Tukey算法叫作“快速傅立叶变换”（Fast Fourier Transform，FFT）的原因。

　　欢迎转载，信息来源维库电子市场网（www.dzsc.com）