# 互質因子算法

## 算法

${\displaystyle 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 一一對應

${\displaystyle 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 映射)，

${\displaystyle k=k_{1}\mod N_{1}}$
${\displaystyle k=k_{2}\mod N_{2}}$

${\displaystyle 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}$

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

${\displaystyle 1=2\centerdot N_{2}+2\centerdot N_{1}\mod 15}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

### DFT re-expression

${\displaystyle 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}}}kn_{1}}e^{-{\frac {2\pi i}{N_{2}}}kn_{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 )。剩下的部分變成

${\displaystyle 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}}.}$

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

${\displaystyle 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\pi }{N_{2}N_{1}}}(k_{1}N_{2}+k_{2}N_{1})(n_{1}N_{2}+n_{2}N_{1})}}$

${\displaystyle =\sum _{n=0}^{N-1}x[((n_{1}N_{2}+n_{2}N_{1}))_{N}]e^{-j{\frac {2\pi }{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})}}$

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

${\displaystyle =\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\pi }{N_{1}}}(k_{1}n_{1}N_{2})}\}e^{-j{\frac {2\pi }{N_{2}}}(k_{2}n_{2}N_{1})}.}$

### 範例

N = 6為例，有兩種可能，N1 = 2, N2 = 3或N1 = 3, N2 = 2。

N1 = 2, N2 = 3
N1 = 3, N2 = 2

## 與Cooley-Tukey算法的比較

${\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-{\frac {2\pi i}{N}}nk}\qquad k=0,\dots ,N-1}$

${\displaystyle 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}}}$
${\displaystyle X_{k_{1}N_{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}}}$

## 注釋

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