离散傅立叶变换(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也都经过有点复杂的重新排列。