[科普中國(guó)]-互質(zhì)因子算法

互質(zhì)因子算法（Prime-factor FFT algorithm, PFA），又稱為Good-Thomas算法，是一種快速傅立葉變換（FFT），把N = N1N2大小的離散傅立葉變換重新表示為N1*N2大小的二維離散傅立葉變換，其中N1與N2需互質(zhì)。變成N1和N2大小的傅立葉變換后，可以繼續(xù)遞回使用PFA，或用其他快速傅立葉變換算法來(lái)計(jì)算。

簡(jiǎn)介較流行的Cooley-Tukey算法經(jīng)由mixed-radix一般化后，也是把N = N1N2大小的離散傅立葉變換分割為N1和N2大小的轉(zhuǎn)換，但和互質(zhì)因子算法 (PFA)作法并不相同，不應(yīng)混淆。Cooley-Tukey算法的N1與N2不需互質(zhì)，可以是任何整數(shù)。然而有個(gè)缺點(diǎn)是比PFA多出一些乘法，和單位根twiddle factors相乘。相對(duì)的，PFA的缺點(diǎn)則是N1與N2需互質(zhì) (例如N 是2次方就不適用)，而且要借由中國(guó)剩余定理來(lái)進(jìn)行較復(fù)雜的re-indexing?；ベ|(zhì)因子算法 (PFA)可以和mixed-radix Cooley-Tukey算法相結(jié)合，前者將N 分解為互質(zhì)的因數(shù)，后者則用在重復(fù)質(zhì)因數(shù)上。

PFA也與nested Winograd FFT算法密切相關(guān)，后者使用更為精巧的二維折積技巧分解成N1 * N2的轉(zhuǎn)換。因而一些較古老的論文把Winograd算法稱為PFA FFT。

盡管PFA和Cooley-Tukey算法并不相同，但有趣的是Cooley和Tukey在他們1965年發(fā)表的有名的論文中，沒(méi)有發(fā)覺(jué)到高斯和其他人更早的研究，只引用Good在1958年發(fā)表的PFA作為前人的FFT結(jié)果。剛開(kāi)始的時(shí)候人們對(duì)這兩種作法是否不同有點(diǎn)困惑。1

算法離散傅立葉變換（DFT）的定義如下:

PFA將輸入和輸出re-indexing，代入DFT公式后轉(zhuǎn)換成二維DFT。

Re-indexing設(shè)N = N1N2，N1與N2兩者互質(zhì)，然后把輸入n 和輸出k 一一對(duì)應(yīng)到

因N1與N2 互質(zhì)，故根據(jù)最大公因數(shù)表現(xiàn)定理，對(duì)每個(gè)n 都存在滿足上式的整數(shù)n1與n2，且在同余N 之下n1可以調(diào)整至0～N1 –1之間，n2可以調(diào)整至0～N2 –1之間。并根據(jù)同余理論易知滿足上式且在以上范圍內(nèi)的整數(shù)n1與n2是只有一個(gè)的。這稱為Ruritanian 映射 (或Good's 映射)，

舉例來(lái)說(shuō):

如果對(duì)于任一都可以對(duì)應(yīng)到

因N1與N2互質(zhì)，故根據(jù)中國(guó)剩余定理，對(duì)于每組 (k1,k2) (其中k1在0～N1– 1之間,k2在0～N2– 1之間)，都有存在且只有一個(gè)的k在0～N- 1之間且滿足上兩式。這稱為CRT映射。CRT映射的另一種表示法如下

其中N1表示N1在模N2之下的反元素，N2反之。

( 也可以改成對(duì)輸入n用CRT映射以及對(duì)輸出k用Ruritanian映射)

對(duì)于有效re-indexing (理想上是達(dá)到原地)的方法有許多研究，以減少耗費(fèi)時(shí)間的模運(yùn)算。2

DFT re-expression表示方法一:

將以上的re-indexing代入DFT公式里指數(shù)部分的nk之中，

( 因?yàn)閑= 1，所以兩個(gè)指數(shù)的k部分可以分別模N1與N2)。剩下的部分變成

則內(nèi)部和外部的總和分別轉(zhuǎn)換成大小為N2與N1的DFT。

表示方法二:

如果令

令相當(dāng)于取的余數(shù)，

對(duì)于每一個(gè)都要做一個(gè)點(diǎn)的，而因?yàn)?img src="https://img-xml.kepuchina.cn/images/newsWire/rvguV9d3W8IwdjS5fTuYLREhFTULwSRonlfr.jpg" alt="" />有個(gè)，所以需要個(gè)點(diǎn)

對(duì)于每一組都要做一個(gè)點(diǎn)的而因?yàn)?img src="https://img-xml.kepuchina.cn/images/newsWire/rw0L2AvhcEGHVjb6WhzdLgz0JB2Dudkk4P3v.jpg" alt="" />為常數(shù)，有個(gè)，所以需要 個(gè)點(diǎn)，

因此如果要計(jì)算復(fù)雜度，可以乘法器的數(shù)量當(dāng)作考量,

假設(shè)點(diǎn)的需要個(gè)乘法器,

假設(shè)點(diǎn)的需要個(gè)乘法器,

則總共需要個(gè)乘法器。

與Cooley-Tukey算法的比較如首段所述，Cooley-Tukey算法和互質(zhì)因子算法 (PFA)曾被誤認(rèn)為很類似。兩者皆有各自優(yōu)點(diǎn)可適用于不同狀況，因此分辨它們的不同是很重要的。在1965年著名的論文中發(fā)表的Cooley-Tukey算法，是在DFT的定義

中代入n=n1+n2N1,k=k1N2+k2，則

比PFA多了一些要乘的因子 (稱為twiddle factors)，但index較為簡(jiǎn)單，且適用于任何N1、N2。在J. Cooley稍后發(fā)表的關(guān)于FFT歷史探討的論文中使用N= 24點(diǎn)FFT為例，顯示兩種作法在index結(jié)構(gòu)上的不同。

本詞條內(nèi)容貢獻(xiàn)者為:

何星 - 副教授 - 上海交通大學(xué)