雷德演算法

雷德演算法（英语：Rader's algorithm）是一种于1968年由麻省理工学院林肯实验室之查尔斯·M·雷德（Charles M. Rader）提出的快速傅立叶转换演算法。当讯号的资料点数量为质数时，此演算法可借由将离散傅立叶转换重新表示为圆周折积，快速计算出该讯号之离散傅立叶转换结果。另一种称为布鲁斯坦演算法的作法也是透过类似的方式将离散傅立叶转换改写为折积完成转换，且同样限制讯号长度需为质数。

由于雷德演算法之运作原理只依赖于具有周期性的离散傅立叶转换核，故它也可直接套用于其它具有类似特性的转换（惟讯号长度需为质数），例如数论转换或离散哈特利转换。

当所欲转换的讯号资料皆为实数时，可透过重新索引或排列将原转换拆成两个长度为一半的实数循环折积，如此稍微修改后的雷德演算法可进一步使运算时间减半；另一种快速计算实数讯号之离散傅立叶转换的方法则是使用离散哈特利转换。

萨缪尔·威诺格拉德进一步延伸了雷德演算法，使其也可用于长度为质数之次方数 $p^{m}$的讯号之离散傅立叶转换；也因此，雷德演算法亦可被视为威诺格拉德快速傅立叶转换演算法（亦称为乘法性傅立叶转换演算法）的特例之一，其中后者可用的讯号长度范围较广。然而，当讯号长度为合数（如质数之次方数）时，使用库利－图基快速傅立叶转换演算法更加简单且实作上也较容易，故雷德演算法一般只用于库利－图基演算法之递回拆解下较大质数之基本情况。

演算法

将雷德演算法之离散傅里叶转换矩阵视觉化的结果。图中上色之时钟图示代表了大小为11的矩阵中各元素之相位。除了第一行与第一列外，在使用11之原根（即2）重新排列矩阵后，原始之离散傅里叶转换矩阵即形成一循环矩阵。将讯号与一循环矩阵相乘即等同于圆周折积。

$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,\ldots ,N-1$之非零索引数集合即形成一整数模N乘法群。运用数论的一个结论，可知此类的群中存在一个生成元（有时亦称为原根，可由穷举搜索或其它较有效率之演算法快速找到）——一个整数 $g,$使得对于任意的非零索引数 $n\in \{1,2,\cdots ,N-1\},$都存在唯一的 $q\in \{0,1,\cdots ,N-2\}$令 $n=g^{q}{\pmod {N}}$，即形成一$q$至非零$n$的对射；同样地，对于任意的非零索引数 $k\in \{1,2,\cdots ,N-1\},$都存在唯一的 $p\in \{0,1,\cdots ,N-2\}$令 $k=g^{-p}{\pmod {N}}$，其中指数的负号代表的是 $g^{p}$之模反元素。这代表所求之离散傅立叶转换可用新的索引数 $p$及 $q$改写如下：

$X_{0}=\sum _{n=0}^{N-1}x_{n},$

$X_{g^{-p}}=x_{0}+\sum _{q=0}^{N-2}x_{g^{q}}e^{-{\frac {2\pi i}{N}}g^{-(p-q)}}\qquad p=0,\dots ,N-2$

其中$x_{n}$和$X_{k}$皆对$N$隐含周期性，而$e^{2\pi i}=1$。因此，所有索引数以及指数皆可依群算术之要求取模$N$之结果。

上式中最后的加总即为长度$N-1$（$q=0,\ldots ,N-2$）之两数列$a_{q}$和$b_{q}$的圆周折积：

$a_{q}=x_{g^{q}}$

$b_{q}=e^{-{\frac {2\pi i}{N}}g^{-q}}$

折积计算

由于$N-1$必为合数，上述之圆周折积可直接由折积定理以及其它常用之快速傅立叶转换演算法求得。然而，若 $N-1$本身具有较大之质因数，则此作法须递回使用雷德演算法，而较不具效率。替代方法之一乃是将原长度为 $N-1$之数列补零至长度大于$2(N-1)-1$，甚或是2的次方数，便可透过快速演算法在$O(N\log {N})$的时间内求得而不须递回使用雷德演算法。

如此一来，此演算法则需要$O(N)$之加法运算以及$O(N\log {N})$之折积运算。实作上，$O(N)$之加法常可被包含至后续的折积运算中：若折积是由一对快速傅立叶转换求得，则 $x_{n}$的加总即是 $x_{0}$以及 $a_{q}$离散傅立叶转换的第0项输出（即DC项）之和。同时，可在逆转换前先将 $x_{0}$加至折积之DC项，这样可使最后的输出皆已包含$x_{0}$。不过，此演算所需的运算步骤仍然比其它接近之合数长度的快速傅立叶转换来得多，实务上耗时是其 3 至 10 倍。

若雷德演算法未使用如上的补零法，而直接透过长度$N-1$之快速傅立叶转换计算，则其效率将取决于$N$值以及雷德演算法本身递回呼叫的次数。最坏情况乃是当$N-1=2N_{2}$且$N_{2}$为质数，$N_{2}-1=2N_{3}$且$N_{3}$为质数，依此类推；在此情况下，若上述的质数炼一直延伸至某界值，则递回雷德演算法之复杂度将为$O(N^{2})$。诸如此类的$N_{j}$称为索菲·热尔曼质数，而它们所形成的质数数列则称为第一类康宁汉炼。然而，康宁汉炼之长度增长的速度一般而言远较$\log _{2}{N}$慢，故如此使用雷德演算法之复杂度应不为$O(N^{2})$，但在最坏情况下复杂度仍应比$O(N\log {N})$高。不过，使用上述的补零法，便可达到 $O(N\log {N})$之复杂度。