雷德算法

雷德算法（英语：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})$之复杂度。