互質因子算法

互質因子算法（Prime-factor FFT algorithm, PFA），又稱為Good-Thomas算法^[1] ^[2]，是一種快速傅立葉變換（FFT），把N = N₁N₂大小的離散傅立葉變換重新表示為N₁ * N₂大小的二維離散傅立葉變換，其中N₁與N₂需互質。變成N₁和N₂大小的傅立葉變換後，可以繼續遞迴使用PFA，或用其他快速傅立葉變換算法來計算。

較流行的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）的定義如下:

X_{k} = \sum_{n = 0}^{N - 1} x_{n} e^{- \frac{2 π i}{N} n k} k = 0, \dots, N - 1

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

Re-indexing

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

n = n_{1} N_{2} + n_{2} N_{1} mod N

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

k = k_{1} mod N_{1}

k = k_{2} mod N_{2}

舉例來說:

如果 $N = 15, N_{1} = 5, N_{2} = 3, n = 0, 1, 2, . . ., 12, 13, 14,$ 對於任一 $n$ 都可以對應到

$n = n_{1} N_{2} + n_{2} N_{1} mod N, n_{1} = 0, 1, . . ., N_{1} - 1, n_{2} = 0, 1, . . ., N_{2} - 1$

$0 = 0 \cdot N_{2} + 0 \cdot N_{1} mod 15$

$1 = 2 \cdot N_{2} + 2 \cdot N_{1} mod 15$

$2 = 4 \cdot N_{2} + 1 \cdot N_{1} mod 15$

$3 = 1 \cdot N_{2} + 0 \cdot N_{1} mod 15$

$4 = 3 \cdot N_{2} + 2 \cdot N_{1} mod 15$

$5 = 0 \cdot N_{2} + 1 \cdot N_{1} mod 15$

$6 = 2 \cdot N_{2} + 0 \cdot N_{1} mod 15$

$7 = 4 \cdot N_{2} + 2 \cdot N_{1} mod 15$

$8 = 1 \cdot N_{2} + 1 \cdot N_{1} mod 15$

$9 = 3 \cdot N_{2} + 0 \cdot N_{1} mod 15$

$10 = 0 \cdot N_{2} + 2 \cdot N_{1} mod 15$

$11 = 2 \cdot N_{2} + 1 \cdot N_{1} mod 15$

$12 = 4 \cdot N_{2} + 0 \cdot N_{1} mod 15$

$13 = 1 \cdot N_{2} + 2 \cdot N_{1} mod 15$

$14 = 3 \cdot N_{2} + 1 \cdot N_{1} mod 15$

因N₁與N₂ 互質，故根據中國剩餘定理，對於每組 ( k₁ , k₂ ) (其中k₁在0～N₁ – 1之間, k₂在0～N₂ – 1之間)，都有存在且唯一的k 在0～N - 1之間且滿足上兩式。這稱為 CRT 映射。 CRT 映射的另一種表示法如下

k = k_{1} N_{2}^{- 1} N_{2} + k_{2} N_{1}^{- 1} N_{1} mod N

其中N₁^-1表示N₁在模N₂之下的反元素，N₂^-1反之。

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

對於有效re-indexing (理想上是達到原地)的方法有許多研究^[3]，以減少耗費時間的模運算。

DFT re-expression

表示方法一:

將以上的re-indexing代入DFT公式裡指數部分的nk 之中，

e^{- \frac{2 π i}{N} n k} = e^{- \frac{2 π i}{N} (n_{1} N_{2} + n_{2} N_{1}) k} = e^{- \frac{2 π i}{N_{1}} k n_{1}} e^{- \frac{2 π i}{N_{2}} k n_{2}} = e^{- \frac{2 π i}{N_{1}} k_{1} n_{1}} e^{- \frac{2 π i}{N_{2}} k_{2} n_{2}}

( 因為e^2πi = 1，所以兩個指數的k 部份可以分別模N₁與N₂ )。剩下的部分變成

X_{k_{1}, k_{2}} = \sum_{n_{1} = 0}^{N_{1} - 1} (\sum_{n_{2} = 0}^{N_{2} - 1} x_{n_{1} N_{2} + n_{2} N_{1}} e^{- \frac{2 π i}{N_{2}} n_{2} k_{2}}) e^{- \frac{2 π i}{N_{1}} n_{1} k_{1}} .

則內部和外部的總和分別轉換成大小為N₂與N₁的DFT。

表示方法二:

如果令 $k = k_{1} N_{2} + k_{2} N_{1} f o r k = 0, 1, . . ., N - 1,$

令 $n = ((n_{1} N_{2} + n_{2} N_{1}))_{N}$ ， $(\cdot)_{N}$ 相當於取 $N$ 的餘數， $n_{1} = 0, \dots, N_{1} - 1$ , $n_{2} = 0, \dots, N_{2} - 1$

$X [((k_{1} N_{2} + k_{2} N_{1}))_{N}] = \sum_{n = 0}^{N - 1} x [((n_{1} N_{2} + n_{2} N_{1}))_{N}] e^{- j \frac{2 π}{N_{2} N_{1}} (k_{1} N_{2} + k_{2} N_{1}) (n_{1} N_{2} + n_{2} N_{1})}$

$= \sum_{n = 0}^{N - 1} x [((n_{1} N_{2} + n_{2} N_{1}))_{N}] e^{- j \frac{2 π}{N_{2} N_{1}} (k_{1} n_{1} N_{2} N_{2} + k_{2} n_{2} N_{1} N_{1} + k_{1} n_{2} N_{2} N_{1} + k_{2} n_{1} N_{1} N_{2})}$

$= \sum_{n = 0}^{N - 1} x [((n_{1} N_{2} + n_{2} N_{1}))_{N}] e^{- j \frac{2 π}{N_{1}} (k_{1} n_{1} N_{2})} e^{- j \frac{2 π}{N_{2}} (k_{2} n_{2} N_{1})}$

$= \sum_{n_{2} = 0}^{N_{2} - 1} {\sum_{n_{1} = 0}^{N_{1} - 1} x [((n_{1} N_{2} + n_{2} N_{1}))_{N}] e^{- j \frac{2 π}{N_{1}} (k_{1} n_{1} N_{2})}} e^{- j \frac{2 π}{N_{2}} (k_{2} n_{2} N_{1})} .$

對於每一個 $n_{2}$ 都要做一個 $N_{1}$ 點的 $D F T$ ，而因為 $n_{2} = 0, \dots, N_{2} - 1$ 有 $N_{2}$ 個，所以需要 $N_{2}$ 個 $N_{1}$ 點 $D F T$ ,

對於每一組 $((k_{1} N_{2}))_{N_{1}}$ 都要做一個 $N_{2}$ 點的 $D F T$ ，而因為 $N_{2}$ 為常數， $k_{1} = 0, \dots, N_{1} - 1$ 有 $N_{1}$ 個，所以需要 $N_{1}$ 個 $N_{2}$ 點 $D F T$ ，

因此如果要計算複雜度，可以乘法器的數量當作考量,

假設 $N_{1}$ 點的 $D F T$ 需要 $M_{1}$ 個乘法器,

假設 $N_{2}$ 點的 $D F T$ 需要 $M_{2}$ 個乘法器,

則總共需要 $N_{2} M_{1} + N_{1} M_{2}$ 個乘法器。

範例

以N = 6為例，有兩種可能，N₁ = 2, N₂ = 3或N₁ = 3, N₂ = 2。

第一種情形所產生的流程圖如左圖所示。先做2次3點DFT後再做3次2點DFT。

第二種情形所產生的流程圖如右圖所示。先做3次2點DFT後再做2次3點DFT。

其中2點DFT的部份因構造單純，皆以交錯的蝴蝶圖來顯示。

可以看出即使在這個簡單的例子中，輸入和輸出的index也都經過有點複雜的重新排列。

與Cooley-Tukey算法的比較

如首段所述，Cooley-Tukey算法和互質因子算法 (PFA)曾被誤認為很類似。兩者皆有各自優點可適用於不同狀況，因此分辨它們的不同是很重要的。在1965年著名的論文中發表的Cooley-Tukey算法，是在DFT的定義

X_{k} = \sum_{n = 0}^{N - 1} x_{n} e^{- \frac{2 π i}{N} n k} k = 0, \dots, N - 1

中代入n = n₁ + n₂N₁ , k = k₁N₂ + k₂，則

e^{- \frac{2 π i}{N} n k} = e^{- \frac{2 π i}{N} (n_{1} + n_{2} N_{1}) (k_{1} N_{2} + k_{2})} = e^{- \frac{2 π i}{N_{1}} n_{1} k_{1}} e^{- \frac{2 π i}{N} n_{1} k_{2}} e^{- \frac{2 π i}{N_{2}} n_{2} k_{2}}

X_{k_{1} N_{2} + k_{2}} = \sum_{n_{1} = 0}^{N_{1} - 1} (\sum_{n_{2} = 0}^{N_{2} - 1} x_{n_{1} + n_{2} N_{1}} e^{- \frac{2 π i}{N_{2}} n_{2} k_{2}}) e^{- \frac{2 π i}{N} n_{1} k_{2}} e^{- \frac{2 π i}{N_{1}} n_{1} k_{1}}

比PFA多了一些要乘的因子 $e^{- \frac{2 π i}{N} n_{1} k_{2}}$ (稱為twiddle factors )，但index較為簡單，且適用於任何N₁、N₂。在J. Cooley稍後發表的關於FFT歷史探討的論文^[4]中使用N = 24點FFT為例，顯示兩種作法在index結構上的不同。

注釋

Template:Reflist

參考文獻

Template:Citation

外部連結

Template:Authority control

[1] Template:Citation

[2] Template:Citation

[3] Template:Citation.

[4] Template:Citation

[1]

[2]

[3]

[4]

互質因子算法

目录

算法

Re-indexing

DFT re-expression

範例

與Cooley-Tukey算法的比較

相關條目

注釋

參考文獻

外部連結

导航菜单

互質因子算法

算法

Re-indexing

DFT re-expression

範例

與Cooley-Tukey算法的比較

相關條目

注釋

參考文獻

外部連結

导航菜单

搜索