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ⁿ¹_n＝w_n2和wⁿ²_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）