Good-Thomas FFT算法

　　Good ^[134]和Thomas^[135]提出的索引变换将一个长度N=N1N2的DFT变换成“实际的”二维DFT，也就是说没有Cooley-Tukey FFT中的旋转因子。无旋转因子流程的代价就是因子之间必须是互质的（也就是gcd（N_k，N₁）＝1，k≠1），只要索引映射计算是在线进行的，而且没有预先计算好的表可供使用，那么索引映射就会变得更加复杂。

　　试图消除通过n和k的索引映射引入的旋转因子，就会有

　　检验：因为AD和BC之中均包括因子N₁N₂＝N，所以也就验证了（6，34）式。有了gcd（N₁，N₂）=1以及欧拉定理，就可以写出逆运算巧N^-1₂mod N₁＝N^{φ（N1）- 1}₂modN₁，其中φ是欧拉φ函数。条件（6．35）现在就可以改写成：

　　同样的理论也适用于条件（6．36）式，且如果采用Good－Thomas映射，从（6．34）式到（6，36）式的3个条件均可以满足。

　　，我们就可以得到下面的定理。

　　（6，41）式的变换与2．2．12中的中国余数定理是一致的。所以k1和k2可以简单地通过模简化来计算，也就是k1＝kmod Nl。

　　如果在DFT矩阵方程（6．16）式中替换Good-Thomas索引映射，就有：

　　也就是像前面提到的，这是一种“实际的”二维DFT变换，没有Colley和Tukey提出的映射所引入的旋转因子。

　　下面就是Good-Thomas算法，虽然与Colley－Tukey算法6．8相似，但是索引映射不同，而且没有旋转因子。

　　下面用N12的变换的示例来说明这些步骤。

　　例 N=12的Godd－Thomas FFT算法

　　假设N1＝4，N2＝3，接下来根据n＝3n1＋4n2mod12和k＝9k1＋4k2mod12计算输入索引到输出索引结果的映射，并且也可以计算下面的索引映射表：

　　利用这些索引变换，我们就可以构造图所示的信号流程图了。其中级有3个DFT，每个DFT又有4个点，第二级有4个DFT，每个DFT的长度为3。级间不需要旋转因子乘法。

　　图 N=12的PFAFFT

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