互質因子算法

维基百科,自由的百科全书
跳转至: 导航搜索

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

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

PFA也與nested Winograd FFT算法密切相關,後者使用更為精巧的二維摺積技巧分解成N1 * N2的轉換。因而一些較古老的論文把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\pi i}{N} nk }
\qquad
k = 0,\dots,N-1

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

Re-indexing[编辑]

N = N1N2N1N2兩者互質,然後把輸入n 和輸出k 一一對應

n = n_1 N_2 + n_2 N_1 \mod N

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

k = k_1 \mod N_1
k = k_2 \mod N_2

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

k = k_1 N_2^{-1} N_2 + k_2 N_1^{-1} N_1 \mod N

其中N1-1表示N1N2之下的反元素N2-1反之。

( 也可以改成對輸入nCRT 映射以及對輸出kRuritanian 映射)

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

DFT re-expression[编辑]

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

e^{-\frac{2\pi i}{N} nk } = e^{-\frac{2\pi i}{N} ( n_1 N_2 + n_2 N_1 )k} = e^{-\frac{2\pi i}{N_1} k n_1} e^{-\frac{2\pi i}{N_2} k n_2} = e^{-\frac{2\pi i}{N_1} k_1 n_1} e^{-\frac{2\pi i}{N_2} k_2 n_2}

( 因為ei = 1,所以兩個指數的k 部份可以分別N1N2 )。剩下的部分變成

X_{k_1 , k_2 } =
 \sum_{n_1=0}^{N_1-1}
   \left( \sum_{n_2=0}^{N_2-1} x_{n_1 N_2 + n_2 N_1}
           e^{-\frac{2\pi i}{N_2} n_2 k_2 } \right)
   e^{-\frac{2\pi i}{N_1} n_1 k_1 }.

則內部和外部的總和分別轉換成大小為N2N1的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也都經過有點複雜的重新排列。

與Cooley-Tukey算法的比較[编辑]

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

X_k = \sum_{n=0}^{N-1} x_n e^{-\frac{2\pi i}{N} nk }
\qquad
k = 0,\dots,N-1

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

e^{-\frac{2\pi i}{N} nk } = e^{-\frac{2\pi i}{N} ( n_1 + n_2 N_1 )( k_1 N_2 + k_2 )} = e^{-\frac{2\pi i}{N_1} n_1 k_1} e^{-\frac{2\pi i}{N} n_1 k_2} e^{-\frac{2\pi i}{N_2} n_2 k_2}
X_{k_1N_2 + k_2} =
 \sum_{n_1=0}^{N_1-1}
   \left( \sum_{n_2=0}^{N_2-1} x_{n_1 + n_2 N_1}
           e^{-\frac{2\pi i}{N_2} n_2 k_2 } \right) e^{-\frac{2\pi i}{N} n_1 k_2}
   e^{-\frac{2\pi i}{N_1} n_1 k_1 }

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

相關條目[编辑]

注釋[编辑]

  1. ^ I. J. Good, The interaction algorithm and practical Fourier analysis, J. R. Statist. Soc. B, 1958,, 20(2): 361–372 
  2. ^ L. H. Thomas, Using a computer to solve problems in physics, Applications of Digital Computers, 1963 
  3. ^ S. C. Chan and K. L. Ho, On indexing the prime-factor fast Fourier transform algorithm, IEEE Trans. Circuits and Systems, 1991,, 38(8): 951–953 .
  4. ^ J. Cooley, P. Lewis, and P. Welch, Historical notes on the fast Fourier transform, IEEE Transactions on Audio and Electroacoustics, 1967,, 15(2): 76–79 

參考文獻[编辑]

  1. P. Duhamel and M. Vetterli, Fast Fourier transforms: a tutorial review and a state of the art, Signal Processing, 1990, 19: 259–299 

外部連結[编辑]