快速傅立叶变换算法

　　正像这一章的概述中所提到的，我们使用的是surrus^[111]提出的术语，他将所有的快速傅立叶变换（Fast Fourier Transform，FFT）算法简单地根据不同的（多维）输入输出序列的索引映射进行分类。这是建立在长度为N的DFT（6．2）：

　　到多维N＝II_laN_l的表达式的变换基础之上的。—般情况下，只需要讨论两个因子的情形就足够了，因为更高的维数可以通过简单地反复迭代替换其中的一个因子就能够实现。为了简化表达式，我们在此只在二维索引映射变换内讨论3种FET算法。

　　将（时域）索引n用：

　　进行交换，其中N＝N₁N₂，且A，B∈Z是以后必须定义据下面的公式：

　　来构造数据的二维映射f∶C^N→C^{N₁ x N₂}。将另一个索引映射k应用到输出（频）域， 就得到：

　　其中C，D∈Z是以后必须定义的常数。由于DFT是双映射，所以我们必须选择A，B，C和D，这样变换表达式才能仍然保持惟一，也就是惟一的双映射投影。Burrus^[111]已经确定了如何为具体的N1和N2选择A，B，C和D的一般情形，这样映射就是双映射了。

　　区别不同FFT算法的重要一点就是是否允许N1和N2具有公因数的问题，也就是gcd（N₁，N₂）＞1（gcd，greatest common pisor，公约数），或者说Ny和蝇必须是互质的。通常，god（N₁，N₂）1的算法指的是公共因数算法（common factor algorithms，CFAs），而gcd（N₁，N₂）＝1就称为质数因数算法（prlrne factor algorithms，PFAs）。在接下来要讨论的CFA算法是Cooley-Tukey FFT，而Good－Thomas和Winograd FFT则是PFA类型的。应该强调的是Cooley－Tukey算法可以真正地用两个因数N＝N1N2实现，彼此之间是互质的，并且对于PFA，因子N₁和N₂必须是互质的，也就是说它们自身不一定是质数。例如：长度N＝12的变换因数分解成N₁＝4和N₂＝3，既可以用于CFA FFT也可以用于PFA FFT ！

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