互質因子算法:互質因子算法（Prime-factor FFT algor -百科知識中文網

簡介

較流行的Cooley-Tukey算法經由mixed-radix一般化後，也是把 N = N N大小的離散傅立葉變換分割為 N和 N大小的轉換，但和互質因子算法 (PFA)作法並不相同，不應混淆。Cooley-Tukey算法的 N與 N不需互質，可以是任何整數。然而有個缺點是比PFA多出一些乘法，和單位根twiddle factors相乘。相對的，PFA的缺點則是 N與 N需互質 (例如 N 是2次方就不適用)，而且要藉由中國剩餘定理來進行較複雜的re-indexing。互質因子算法 (PFA)可以和mixed-radix Cooley-Tukey算法相結合，前者將 N 分解為互質的因數，後者則用在重複質因數上。

PFA也與nested Winograd FFT算法密切相關，後者使用更為精巧的二維折積技巧分解成 N * N的轉換。因而一些較古老的論文把Winograd算法稱為PFA FFT。

儘管PFA和Cooley-Tukey算法並不相同，但有趣的是Cooley和Tukey在他們1965年發表的有名的論文中，沒有發覺到高斯和其他人更早的研究，只引用Good在1958年發表的PFA作為前人的FFT結果。剛開始的時候人們對這兩種作法是否不同有點困惑。

算法

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

PFA將輸入和輸出re-indexing，代入DFT公式後轉換成二維DFT。

Re-indexing

設 N = N N， N與 N兩者互質，然後把輸入 n 和輸出 k 一一對應到

因 N與 N 互質，故根據最大公因數表現定理，對每個 n 都存在滿足上式的整數 n與 n，且在同餘 N 之下 n可以調整至0～ N –1之間， n可以調整至0～ N –1之間。並根據同餘理論易知滿足上式且在以上範圍內的整數 n與 n是只有一個的。這稱為 Ruritanian 映射 (或 Good's 映射)，