離散傅立葉變換(DFT)的定義如下:
-
PFA將輸入和輸出re-indexing,代入DFT公式後轉換成二維DFT。
設N = N1N2,N1與N2兩者互質,然後把輸入n 和輸出k 一一對應到
-
因N1與N2 互質,故根據最大公因數表現定理,對每個n 都存在滿足上式的整數n1與n2,且在同餘N 之下n1可以調整至0~N1 –1之間,n2可以調整至0~N2 –1之間。並根據同餘理論易知滿足上式且在以上範圍內的整數n1與n2是唯一的。這稱為Ruritanian 映射 (或Good's 映射),
-
-
舉例來說:
如果 對於任一 都可以對應到
因N1與N2 互質,故根據中國剩餘定理,對於每組 ( k1 , k2 ) (其中k1在0~N1 – 1之間, k2在0~N2 – 1之間),都有存在且唯一的k 在0~N - 1之間且滿足上兩式。這稱為 CRT 映射。
CRT 映射的另一種表示法如下
-
其中N1-1表示N1在模N2之下的反元素,N2-1反之。
( 也可以改成對輸入n 用 CRT 映射以及對輸出k 用Ruritanian 映射)
對於有效re-indexing (理想上是達到原地)的方法有許多研究[3],以減少耗費時間的模運算。
表示方法一:
將以上的re-indexing代入DFT公式裏指數部分的nk 之中,
-
( 因為e2πi = 1,所以兩個指數的k 部份可以分別模N1與N2 )。剩下的部分變成
-
則內部和外部的總和分別轉換成大小為N2與N1的DFT。
表示方法二:
如果令
令 , 相當於取 的餘數, ,
對於每一個 都要做一個 點的 ,而因為 有 個,所以需要 個 點 ,
對於每一組 都要做一個 點的 ,而因為 為常數, 有 個,所以需要 個 點 ,
因此如果要計算複雜度,可以乘法器的數量當作考量,
假設 點的 需要 個乘法器,
假設 點的 需要 個乘法器,
則總共需要 個乘法器。
以N = 6為例,有兩種可能,N1 = 2, N2 = 3或N1 = 3, N2 = 2。
N1 = 2, N2 = 3
N1 = 3, N2 = 2
第一種情形所產生的流程圖如左圖所示。先做2次3點DFT後再做3次2點DFT。
第二種情形所產生的流程圖如右圖所示。先做3次2點DFT後再做2次3點DFT。
其中2點DFT的部份因構造單純,皆以交錯的蝴蝶圖來顯示。
可以看出即使在這個簡單的例子中,輸入和輸出的index也都經過有點複雜的重新排列。