互质因子算法 （Prime-factor FFT algorithm, PFA），又称为Good-Thomas算法[ 1] [ 2] 快速傅立叶变换 （FFT），把N = N 1 N 2 大小的离散傅立叶变换 重新表示为N 1 * N 2 大小的二维离散傅立叶变换 ，其中N 1 与N 2 需互质 。变成N 1 和N 2 大小的傅立叶变换后，可以继续递回使用PFA，或用其他快速傅立叶变换 算法来计算。
较流行的Cooley-Tukey算法 经由mixed-radix一般化后，也是把N = N 1 N 2 大小的离散傅立叶变换 分割为N 1 和N 2 大小的转换，但和互质因子算法 (PFA)作法并不相同，不应混淆。Cooley-Tukey算法 的N 1 与N 2 不需互质 ，可以是任何整数。然而有个缺点是比PFA多出一些乘法，和单位根 twiddle factors 相乘。相对的，PFA的缺点则是N 1 与N 2 需互质 (例如N 是2次方就不适用)，而且要借由中国剩余定理 来进行较复杂的re-indexing。互质因子算法 (PFA)可以和mixed-radix Cooley-Tukey算法 相结合，前者将N 分解为互质 的因数 ，后者则用在重复质因数 上。
PFA也与nested Winograd FFT 算法密切相关，后者使用更为精巧的二维折积 技巧分解成N 1 * N 2 的转换。因而一些较古老的论文把Winograd算法称为PFA FFT。
尽管PFA和Cooley-Tukey算法并不相同，但有趣的是Cooley和Tukey在他们1965年发表的有名的论文中，没有发觉到高斯 和其他人更早的研究，只引用Good在1958年发表的PFA作为前人的FFT结果。刚开始的时候人们对这两种作法是否不同有点困惑。
离散傅立叶变换 （DFT）的定义如下:
X
k
=
∑
n
=
0
N
−
1
x
n
e
−
2
π
i
N
n
k
k
=
0
,
…
,
N
−
1
{\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。
设N = N 1 N 2 ，N 1 与N 2 两者互质 ，然后把输入n 和输出k 一一对应 到
n
=
n
1
N
2
+
n
2
N
1
mod
N
{\displaystyle n=n_{1}N_{2}+n_{2}N_{1}\mod N}
因N 1 与N 2 互质 ，故根据最大公因数表现定理 ，对每个n 都存在满足上式的整数n 1 与n 2 ，且在同余 N 之下n 1 可以调整至0～N 1 –1之间，n 2 可以调整至0～N 2 –1之间。并根据同余 理论易知满足上式且在以上范围内的整数n 1 与n 2 是唯一的。这称为Ruritanian 映射 (或Good's 映射)，
k
=
k
1
mod
N
1
{\displaystyle k=k_{1}\mod N_{1}}
k
=
k
2
mod
N
2
{\displaystyle k=k_{2}\mod N_{2}}
举例来说:
如果
N
=
15
,
N
1
=
5
,
N
2
=
3
,
n
=
0
,
1
,
2
,
.
.
.
,
12
,
13
,
14
,
{\displaystyle N=15,N_{1}=5,N_{2}=3,n=0,1,2,...,12,13,14,}
n
{\displaystyle 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
{\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}
0
=
0
⋅
N
2
+
0
⋅
N
1
mod
15
{\displaystyle 0=0\centerdot N_{2}+0\centerdot N_{1}\mod 15}
1
=
2
⋅
N
2
+
2
⋅
N
1
mod
15
{\displaystyle 1=2\centerdot N_{2}+2\centerdot N_{1}\mod 15}
2
=
4
⋅
N
2
+
1
⋅
N
1
mod
15
{\displaystyle 2=4\centerdot N_{2}+1\centerdot N_{1}\mod 15}
3
=
1
⋅
N
2
+
0
⋅
N
1
mod
15
{\displaystyle 3=1\centerdot N_{2}+0\centerdot N_{1}\mod 15}
4
=
3
⋅
N
2
+
2
⋅
N
1
mod
15
{\displaystyle 4=3\centerdot N_{2}+2\centerdot N_{1}\mod 15}
5
=
0
⋅
N
2
+
1
⋅
N
1
mod
15
{\displaystyle 5=0\centerdot N_{2}+1\centerdot N_{1}\mod 15}
6
=
2
⋅
N
2
+
0
⋅
N
1
mod
15
{\displaystyle 6=2\centerdot N_{2}+0\centerdot N_{1}\mod 15}
7
=
4
⋅
N
2
+
2
⋅
N
1
mod
15
{\displaystyle 7=4\centerdot N_{2}+2\centerdot N_{1}\mod 15}
8
=
1
⋅
N
2
+
1
⋅
N
1
mod
15
{\displaystyle 8=1\centerdot N_{2}+1\centerdot N_{1}\mod 15}
9
=
3
⋅
N
2
+
0
⋅
N
1
mod
15
{\displaystyle 9=3\centerdot N_{2}+0\centerdot N_{1}\mod 15}
10
=
0
⋅
N
2
+
2
⋅
N
1
mod
15
{\displaystyle 10=0\centerdot N_{2}+2\centerdot N_{1}\mod 15}
11
=
2
⋅
N
2
+
1
⋅
N
1
mod
15
{\displaystyle 11=2\centerdot N_{2}+1\centerdot N_{1}\mod 15}
12
=
4
⋅
N
2
+
0
⋅
N
1
mod
15
{\displaystyle 12=4\centerdot N_{2}+0\centerdot N_{1}\mod 15}
13
=
1
⋅
N
2
+
2
⋅
N
1
mod
15
{\displaystyle 13=1\centerdot N_{2}+2\centerdot N_{1}\mod 15}
14
=
3
⋅
N
2
+
1
⋅
N
1
mod
15
{\displaystyle 14=3\centerdot N_{2}+1\centerdot N_{1}\mod 15}
因N 1 与N 2 互质 ，故根据中国剩余定理 ，对于每组 ( k 1 , k 2 ) (其中k 1 在0～N 1 – 1之间, k 2 在0～N 2 – 1之间)，都有存在且唯一的k 在0～N - 1之间且满足上两式。这称为 CRT 映射。
CRT 映射的另一种表示法如下
k
=
k
1
N
2
−
1
N
2
+
k
2
N
1
−
1
N
1
mod
N
{\displaystyle k=k_{1}N_{2}^{-1}N_{2}+k_{2}N_{1}^{-1}N_{1}\mod N}
其中N 1 -1 表示N 1 在模 N 2 之下的反元素 ，N 2 -1 反之。
( 也可以改成对输入n 用 CRT 映射以及对输出k 用Ruritanian 映射)
对于有效re-indexing (理想上是达到原地 )的方法有许多研究[ 3] 模 运算。
表示方法一:
将以上的re-indexing代入DFT公式里指数部分的nk 之中，
e
−
2
π
i
N
n
k
=
e
−
2
π
i
N
(
n
1
N
2
+
n
2
N
1
)
k
=
e
−
2
π
i
N
1
k
n
1
e
−
2
π
i
N
2
k
n
2
=
e
−
2
π
i
N
1
k
1
n
1
e
−
2
π
i
N
2
k
2
n
2
{\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}}}
( 因为e 2πi = 1，所以两个指数的k 部分可以分别模 N 1 与N 2 )。剩下的部分变成
X
k
1
,
k
2
=
∑
n
1
=
0
N
1
−
1
(
∑
n
2
=
0
N
2
−
1
x
n
1
N
2
+
n
2
N
1
e
−
2
π
i
N
2
n
2
k
2
)
e
−
2
π
i
N
1
n
1
k
1
.
{\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}}.}
则内部和外部的总和 分别转换成大小为N 2 与N 1 的DFT。
表示方法二:
如果令
k
=
k
1
N
2
+
k
2
N
1
f
o
r
k
=
0
,
1
,
.
.
.
,
N
−
1
,
{\displaystyle k=k_{1}N_{2}+k_{2}N_{1}\quad for\quad k=0,1,...,N-1,}
令
n
=
(
(
n
1
N
2
+
n
2
N
1
)
)
N
{\displaystyle n=((n_{1}N_{2}+n_{2}N_{1}))_{N}}
(
⋅
)
N
{\displaystyle (\cdot )_{N}}
N
{\displaystyle N}
n
1
=
0
,
…
,
N
1
−
1
{\displaystyle n_{1}=0,\dots ,N_{1}-1}
n
2
=
0
,
…
,
N
2
−
1
{\displaystyle n_{2}=0,\dots ,N_{2}-1}
X
[
(
(
k
1
N
2
+
k
2
N
1
)
)
N
]
=
∑
n
=
0
N
−
1
x
[
(
(
n
1
N
2
+
n
2
N
1
)
)
N
]
e
−
j
2
π
N
2
N
1
(
k
1
N
2
+
k
2
N
1
)
(
n
1
N
2
+
n
2
N
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})}}
=
∑
n
=
0
N
−
1
x
[
(
(
n
1
N
2
+
n
2
N
1
)
)
N
]
e
−
j
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
)
{\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})}}
=
∑
n
=
0
N
−
1
x
[
(
(
n
1
N
2
+
n
2
N
1
)
)
N
]
e
−
j
2
π
N
1
(
k
1
n
1
N
2
)
e
−
j
2
π
N
2
(
k
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_{1}}}(k_{1}n_{1}N_{2})}e^{-j{\frac {2\pi }{N_{2}}}(k_{2}n_{2}N_{1})}}
=
∑
n
2
=
0
N
2
−
1
{
∑
n
1
=
0
N
1
−
1
x
[
(
(
n
1
N
2
+
n
2
N
1
)
)
N
]
e
−
j
2
π
N
1
(
k
1
n
1
N
2
)
}
e
−
j
2
π
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
2
{\displaystyle n_{2}}
N
1
{\displaystyle N_{1}}
D
F
T
{\displaystyle DFT}
n
2
=
0
,
…
,
N
2
−
1
{\displaystyle n_{2}=0,\dots ,N_{2}-1}
N
2
{\displaystyle N_{2}}
N
2
{\displaystyle N_{2}}
N
1
{\displaystyle N_{1}}
D
F
T
{\displaystyle DFT}
对于每一组
(
(
k
1
N
2
)
)
N
1
{\displaystyle ((k_{1}N_{2}))_{N_{1}}}
N
2
{\displaystyle N_{2}}
D
F
T
{\displaystyle DFT}
N
2
{\displaystyle N_{2}}
k
1
=
0
,
…
,
N
1
−
1
{\displaystyle k_{1}=0,\dots ,N_{1}-1}
N
1
{\displaystyle N_{1}}
N
1
{\displaystyle N_{1}}
N
2
{\displaystyle N_{2}}
D
F
T
{\displaystyle DFT}
因此如果要计算复杂度，可以乘法器的数量当作考量,
假设
N
1
{\displaystyle N_{1}}
D
F
T
{\displaystyle DFT}
M
1
{\displaystyle M_{1}}
假设
N
2
{\displaystyle N_{2}}
D
F
T
{\displaystyle DFT}
M
2
{\displaystyle M_{2}}
则总共需要
N
2
M
1
+
N
1
M
2
{\displaystyle N_{2}M_{1}+N_{1}M_{2}}
以N = 6为例，有两种可能，N 1 = 2, N 2 = 3或N 1 = 3, N 2 = 2。
N 1 = 2, N 2 = 3 N 1 = 3, N 2 = 2 第一种情形所产生的流程图如左图所示。先做2次3点DFT后再做3次2点DFT。
第二种情形所产生的流程图如右图所示。先做3次2点DFT后再做2次3点DFT。
其中2点DFT的部分因构造单纯，皆以交错的蝴蝶图 来显示。
可以看出即使在这个简单的例子中，输入和输出的index也都经过有点复杂的重新排列。
如首段所述，Cooley-Tukey算法 和互质因子算法 (PFA)曾被误认为很类似。两者皆有各自优点可适用于不同状况，因此分辨它们的不同是很重要的。在1965年著名的论文中发表的Cooley-Tukey算法 ，是在DFT的定义
X
k
=
∑
n
=
0
N
−
1
x
n
e
−
2
π
i
N
n
k
k
=
0
,
…
,
N
−
1
{\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-{\frac {2\pi i}{N}}nk}\qquad k=0,\dots ,N-1}
中代入n = n 1 + n 2 N 1 , k = k 1 N 2 + k 2 ，则
e
−
2
π
i
N
n
k
=
e
−
2
π
i
N
(
n
1
+
n
2
N
1
)
(
k
1
N
2
+
k
2
)
=
e
−
2
π
i
N
1
n
1
k
1
e
−
2
π
i
N
n
1
k
2
e
−
2
π
i
N
2
n
2
k
2
{\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}}}
X
k
1
N
2
+
k
2
=
∑
n
1
=
0
N
1
−
1
(
∑
n
2
=
0
N
2
−
1
x
n
1
+
n
2
N
1
e
−
2
π
i
N
2
n
2
k
2
)
e
−
2
π
i
N
n
1
k
2
e
−
2
π
i
N
1
n
1
k
1
{\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}}}
比PFA多了一些要乘的因子
e
−
2
π
i
N
n
1
k
2
{\displaystyle e^{-{\frac {2\pi i}{N}}n_{1}k_{2}}}
twiddle factors )，但index较为简单，且适用于任何N 1 、N 2 。在J. Cooley稍后发表的关于FFT历史探讨的论文[ 4] N = 24点FFT为例，显示两种作法在index结构上的不同。
N
=
N
1
∗
N
2
{\displaystyle N=N_{1}*N_{2}}
N
1
{\displaystyle N_{1}}
N
2
{\displaystyle N_{2}}
离散傅立叶变换 （DFT）的定义如下:
F
[
m
]
=
∑
n
=
0
N
−
1
f
[
n
]
e
−
2
π
i
N
m
n
m
,
n
=
0
,
…
,
N
−
1
{\displaystyle F[m]=\sum _{n=0}^{N-1}f[n]e^{-{\frac {2\pi i}{N}}mn}\qquad m,n=0,\dots ,N-1}
N
2
{\displaystyle N_{2}}
N
1
−
p
o
i
n
t
{\displaystyle N_{1}-point}
N
1
{\displaystyle N_{1}}
N
2
−
p
o
i
n
t
{\displaystyle N_{2}-point}
D
F
T
s
{\displaystyle DFT_{s}}
twiddle factor 。
令
n
=
n
1
N
1
+
n
2
{\displaystyle n=n_{1}N_{1}+n_{2}}
m
=
m
1
+
m
2
N
2
{\displaystyle m=m_{1}+m_{2}N_{2}}
n
1
,
m
1
=
0
,
1
,
2
,
.
.
.
.
,
N
2
−
1
{\displaystyle n_{1},m_{1}=0,1,2,....,N_{2}-1}
n
2
,
m
2
=
0
,
1
,
2
,
.
.
.
.
,
N
1
−
1
{\displaystyle n_{2},m_{2}=0,1,2,....,N_{1}-1}
可得出下列式子
F
[
m
1
+
m
2
N
2
]
=
∑
n
=
0
N
−
1
f
[
n
1
N
1
+
n
2
]
e
−
2
π
i
N
(
m
1
+
m
2
N
2
)
(
n
1
N
1
+
n
2
)
{\displaystyle F[m_{1}+m_{2}N_{2}]=\sum _{n=0}^{N-1}f[n_{1}N_{1}+n_{2}]e^{-{\frac {2\pi i}{N}}(m_{1}+m_{2}N_{2})(n_{1}N_{1}+n_{2})}\qquad }
=
∑
n
=
0
N
−
1
f
[
n
1
N
1
+
n
2
]
e
−
2
π
i
N
1
N
2
(
m
1
n
1
N
1
+
m
1
n
2
+
m
2
n
1
N
1
N
2
+
m
2
n
2
N
2
)
{\displaystyle \qquad \qquad \qquad \ \ =\sum _{n=0}^{N-1}f[n_{1}N_{1}+n_{2}]e^{-{\frac {2\pi i}{N_{1}N_{2}}}(m_{1}n_{1}N_{1}+m_{1}n_{2}+m_{2}n_{1}N_{1}N_{2}+m_{2}n_{2}N_{2})}}
=
∑
n
=
0
N
−
1
f
[
n
1
N
1
+
n
2
]
e
−
2
π
i
N
2
(
m
1
n
1
)
e
−
2
π
i
N
1
(
m
2
n
2
)
e
−
2
π
i
N
1
N
2
(
m
1
n
2
)
{\displaystyle \qquad \qquad \qquad \ \ =\sum _{n=0}^{N-1}f[n_{1}N_{1}+n_{2}]e^{-{\frac {2\pi i}{N_{2}}}(m_{1}n_{1})}e^{-{\frac {2\pi i}{N_{1}}}(m_{2}n_{2})}e^{-{\frac {2\pi i}{N_{1}N_{2}}}(m_{1}n_{2})}}
=
∑
n
2
=
0
P
1
−
1
(
∑
n
1
=
0
N
2
−
1
f
[
n
1
N
1
+
n
2
]
e
−
2
π
i
N
2
(
m
1
n
1
)
)
e
−
2
π
i
N
1
(
m
2
n
2
)
e
−
2
π
i
N
1
N
2
(
m
1
n
2
)
{\displaystyle \qquad \qquad \qquad \ \ =\sum _{n_{2}=0}^{P_{1}-1}{\Bigl (}\sum _{n_{1}=0}^{N_{2}-1}f[n_{1}N_{1}+n_{2}]e^{-{\frac {2\pi i}{N_{2}}}(m_{1}n_{1})}{\Bigr )}e^{-{\frac {2\pi i}{N_{1}}}(m_{2}n_{2})}e^{-{\frac {2\pi i}{N_{1}N_{2}}}(m_{1}n_{2})}}
上述的
e
−
2
π
i
N
1
N
2
(
m
1
n
2
)
{\displaystyle e^{-{\frac {2\pi i}{N_{1}N_{2}}}(m_{1}n_{2})}}
twiddle factor ，需要额外的乘法去做运算。
由于
n
1
,
m
1
=
0
,
1
,
2
,
.
.
.
.
,
N
2
−
1
{\displaystyle n_{1},m_{1}=0,1,2,....,N_{2}-1}
n
2
,
m
2
=
0
,
1
,
2
,
.
.
.
.
,
N
1
−
1
{\displaystyle n_{2},m_{2}=0,1,2,....,N_{1}-1}
twiddle factors的数量为
N
=
N
1
∗
N
2
{\displaystyle N=N_{1}*N_{2}}
m
1
=
0
{\displaystyle m_{1}=0}
n
2
=
0
{\displaystyle n_{2}=0}
(
N
1
−
1
)
∗
(
N
2
−
1
)
{\displaystyle (N_{1}-1)*(N_{2}-1)}
令
g
[
n
1
,
n
2
]
=
f
[
n
1
N
1
+
n
2
]
{\displaystyle g[n_{1},n_{2}]=f[n_{1}N_{1}+n_{2}]}
固定
n
2
{\displaystyle n_{2}}
n
1
{\displaystyle n_{1}}
N
2
−
p
o
i
n
t
{\displaystyle N_{2}-point}
D
F
T
{\displaystyle DFT}
G
1
[
m
1
,
n
2
]
=
∑
n
1
=
0
N
2
−
1
g
[
n
1
,
n
2
]
e
−
2
π
i
N
2
(
m
1
n
1
)
{\displaystyle G_{1}[m_{1},n_{2}]=\sum _{n_{1}=0}^{N_{2}-1}g[n_{1},n_{2}]e^{-{\frac {2\pi i}{N_{2}}}(m_{1}n_{1})}}
由于
n
2
=
0
,
1
,
2
,
.
.
.
.
,
N
1
−
1
{\displaystyle n_{2}=0,1,2,....,N_{1}-1}
N
1
{\displaystyle N_{1}}
N
2
−
p
o
i
n
t
{\displaystyle N_{2}-point}
D
F
T
s
{\displaystyle DFT_{s}}
G
2
[
m
1
,
n
2
]
=
G
1
[
m
1
,
n
2
]
e
−
2
π
i
N
1
N
2
(
m
1
n
2
)
{\displaystyle G_{2}[m_{1},n_{2}]=G_{1}[m_{1},n_{2}]e^{-{\frac {2\pi i}{N_{1}N_{2}}}(m_{1}n_{2})}}
twiddle factor s)
固定
n
2
{\displaystyle n_{2}}
n
2
{\displaystyle n_{2}}
N
1
−
p
o
i
n
t
{\displaystyle N_{1}-point}
D
F
T
{\displaystyle DFT}
G
3
[
m
1
,
m
2
]
=
∑
n
2
=
0
N
1
−
1
g
[
m
1
,
n
2
]
e
−
2
π
i
N
1
(
m
2
n
2
)
{\displaystyle G_{3}[m_{1},m_{2}]=\sum _{n_{2}=0}^{N_{1}-1}g[m_{1},n_{2}]e^{-{\frac {2\pi i}{N_{1}}}(m_{2}n_{2})}}
由于
m
1
=
0
,
1
,
2
,
.
.
.
.
,
N
2
−
1
{\displaystyle m_{1}=0,1,2,....,N_{2}-1}
N
2
{\displaystyle N_{2}}
N
1
−
p
o
i
n
t
{\displaystyle N_{1}-point}
D
F
T
s
{\displaystyle DFT_{s}}
F
[
m
1
+
m
2
N
2
]
=
G
3
[
m
1
,
m
2
]
{\displaystyle F[m_{1}+m_{2}N_{2}]=G_{3}[m_{1},m_{2}]}
N
=
N
1
∗
N
2
{\displaystyle N=N_{1}*N_{2}}
假设
N
1
−
p
o
i
n
t
{\displaystyle N_{1}-point}
B
1
{\displaystyle B_{1}}
N
2
−
p
o
i
n
t
{\displaystyle N_{2}-point}
D
F
T
{\displaystyle DFT}
B
2
{\displaystyle B_{2}}
且
m
1
n
2
{\displaystyle m_{1}n_{2}}
有
D
1
{\displaystyle D_{1}}
N
/
12
{\displaystyle N/12}
N
/
8
{\displaystyle N/8}
有
D
2
{\displaystyle D_{2}}
N
/
12
{\displaystyle N/12}
N
/
8
{\displaystyle N/8}
N
/
4
{\displaystyle N/4}
则
N
−
p
o
i
n
t
{\displaystyle N-point}
D
F
T
{\displaystyle DFT}
N
2
B
1
+
N
1
B
2
+
3
D
1
+
2
D
2
{\displaystyle N_{2}B_{1}+N_{1}B_{2}+3D_{1}+2D_{2}}
a
{\displaystyle a}
a
∗
e
i
θ
{\displaystyle a*e^{i\theta }}
θ
{\displaystyle \theta }
π
/
4
{\displaystyle \pi /4}
θ
{\displaystyle \theta }
π
/
3
{\displaystyle \pi /3}
16
−
p
o
i
n
t
{\displaystyle 16-point}
D
F
T
{\displaystyle DFT}
16
=
4
∗
4
{\displaystyle 16=4*4}
4
−
p
o
i
n
t
{\displaystyle 4-point}
0
M
U
L
s
{\displaystyle 0\ MUL_{s}}
m
1
n
2
{\displaystyle m_{1}n_{2}}
0
,
0
,
0
,
0
,
0
,
1
,
2
,
3
,
0
,
2
,
4
,
6
,
0
,
3
,
6
,
9
{\displaystyle 0,0,0,0,0,1,2,3,0,2,4,6,0,3,6,9}
D
1
{\displaystyle D_{1}}
D
2
{\displaystyle D_{2}}
总计需要
4
∗
0
+
4
∗
0
+
3
∗
4
+
2
∗
4
=
20
M
U
L
s
{\displaystyle 4*0+4*0+3*4+2*4=20MUL_{s}}
^ I. J. Good, The interaction algorithm and practical Fourier analysis , J. R. Statist. Soc. B, 1958, 20(2) : 361–372 ^ L. H. Thomas, Using a computer to solve problems in physics, Applications of Digital Computers, 1963 ^ 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 ^ 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
P. Duhamel and M. Vetterli, Fast Fourier transforms: a tutorial review and a state of the art , Signal Processing, 1990, 19 : 259–299 Jian-Jiun Ding, Advanced Digital Signal Processing class note,the Department of Electrical Engineering, National Taiwan University (NTU), Taipei, Taiwan, 2025 
![{\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})}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fbf599d06e8729134d9c00b5e4b2bde2b24fcb94)
![{\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})}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d53333685253fd2cadbcdd46da32523c33846820)
![{\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})}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/66d77514852130c9cc9b66e7b7c7d8e2d7df3f06)
![{\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})}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d12904e0a977ad3e1142221bf48c1f697790be62)
![{\displaystyle F[m]=\sum _{n=0}^{N-1}f[n]e^{-{\frac {2\pi i}{N}}mn}\qquad m,n=0,\dots ,N-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ae60a8dd48fcbd2f8348a20385737132bf9ea7ae)
![{\displaystyle F[m_{1}+m_{2}N_{2}]=\sum _{n=0}^{N-1}f[n_{1}N_{1}+n_{2}]e^{-{\frac {2\pi i}{N}}(m_{1}+m_{2}N_{2})(n_{1}N_{1}+n_{2})}\qquad }](https://wikimedia.org/api/rest_v1/media/math/render/svg/b5103e38a762807b7e97856c149ed702527bb828)
![{\displaystyle \qquad \qquad \qquad \ \ =\sum _{n=0}^{N-1}f[n_{1}N_{1}+n_{2}]e^{-{\frac {2\pi i}{N_{1}N_{2}}}(m_{1}n_{1}N_{1}+m_{1}n_{2}+m_{2}n_{1}N_{1}N_{2}+m_{2}n_{2}N_{2})}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3237bd74a98ce5a9e1b63979aafe0af5f090a4f3)
![{\displaystyle \qquad \qquad \qquad \ \ =\sum _{n=0}^{N-1}f[n_{1}N_{1}+n_{2}]e^{-{\frac {2\pi i}{N_{2}}}(m_{1}n_{1})}e^{-{\frac {2\pi i}{N_{1}}}(m_{2}n_{2})}e^{-{\frac {2\pi i}{N_{1}N_{2}}}(m_{1}n_{2})}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c8318143f9665186e58bf991217ab1d321a86960)
![{\displaystyle \qquad \qquad \qquad \ \ =\sum _{n_{2}=0}^{P_{1}-1}{\Bigl (}\sum _{n_{1}=0}^{N_{2}-1}f[n_{1}N_{1}+n_{2}]e^{-{\frac {2\pi i}{N_{2}}}(m_{1}n_{1})}{\Bigr )}e^{-{\frac {2\pi i}{N_{1}}}(m_{2}n_{2})}e^{-{\frac {2\pi i}{N_{1}N_{2}}}(m_{1}n_{2})}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3cda60da73b0565bfbfb9933bf1623ac24552ba5)
![{\displaystyle g[n_{1},n_{2}]=f[n_{1}N_{1}+n_{2}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5c4caac90136f405766121d7a515108b398686a6)
![{\displaystyle G_{1}[m_{1},n_{2}]=\sum _{n_{1}=0}^{N_{2}-1}g[n_{1},n_{2}]e^{-{\frac {2\pi i}{N_{2}}}(m_{1}n_{1})}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d5af581903695d6e299e1fa2d95cb83bc78c7352)
![{\displaystyle G_{2}[m_{1},n_{2}]=G_{1}[m_{1},n_{2}]e^{-{\frac {2\pi i}{N_{1}N_{2}}}(m_{1}n_{2})}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/daea3806df23713b0e936bec46d6bfeae2005c02)
![{\displaystyle G_{3}[m_{1},m_{2}]=\sum _{n_{2}=0}^{N_{1}-1}g[m_{1},n_{2}]e^{-{\frac {2\pi i}{N_{1}}}(m_{2}n_{2})}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7839660dfa6d085f82d1d090fe65bae58da35b44)
![{\displaystyle F[m_{1}+m_{2}N_{2}]=G_{3}[m_{1},m_{2}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1e9b4320cb5654eaf5fe0a3b772816526ed3aeb6)
