快速傅里叶变换

File:Disambig gray.svg“FFT”重定向至此。关于其他用法，请见“FFT (消歧义)”。

File:Time Signal of Five Term Cosine Series.png

一个五项余弦级数的时域信号。频率为 <math> 10 \sqrt{ 2 } </math> 的倍数。振幅为 1, 2, 3, 4, 5。时间步长为 0.001 s

File:DFTs of Five Term Cosine Series.png

用FFT（~40,000次运算）五项余弦级数及用显式积分（~1亿次运算）得出的DFT。时间窗口是10秒。FFT是用FFTW3（ http://www.fftw.org/ （页面存档备份，存于互联网档案馆） ）计算的。显式积分DFT是用 https://sourceforge.net/projects/amoreaccuratefouriertransform/ （页面存档备份，存于互联网档案馆） 计算的。

File:Zoomed DFTs of Five Term Cosine Series.png

缩放后的五项余弦级数的DFT。注意到显式积分更细的步长大小比FFT更精确地再现了峰值（4）和频率（56.569 Hz），代价是速度慢了上千倍。

快速傅里叶变换（英语：Fast Fourier Transform, FFT），是快速计算序列的离散傅里叶变换（DFT）或其逆变换的方法。傅里叶分析将信号从原始域（通常是时间或空间）转换到频域的表示或者逆过来转换。FFT会通过把DFT矩阵分解为稀疏（大多为零）因子之积来快速计算此类变换。因此，它能够将计算DFT的复杂度从只用DFT定义计算需要的 <math>O(n^2)</math>，降低到 <math>O(n \log n)</math>，其中 <math>n</math> 为数据大小。

快速傅里叶变换广泛的应用于工程、科学和数学领域。这里的基本思想在1965年才得到普及，但早在1805年就已推导出来。1994年美国数学家吉尔伯特·斯特朗把FFT描述为“我们一生中最重要的数值算法”，它还被IEEE科学与工程计算期刊列入20世纪十大算法。

定义和速度

用FFT计算DFT会得到与直接用DFT定义计算相同的结果；最重要的区别是FFT更快。（由于舍入误差的存在，许多FFT算法还会比直接运用定义求值精确很多，后面会讨论到这一点。）

令 <math>X_0, \cdots , X_{N-1}</math> 为复数。DFT由下式定义

<math> X_k = \sum_{n=0}^{N-1} x_n e^{-{i 2\pi k \frac{n}{N}}}

\qquad k = 0,\dots,N-1. </math>

直接按这个定义求值需要 <math>O(N^2)</math> 次运算：<math>X^k</math> 共有 <math>N</math> 个输出，每个输出需要 <math>N</math> 项求和。直接使用DFT运算需使用 <math>N</math> 个复数乘法（ <math>4N</math> 个实数乘法）与 <math>N-1</math> 个复数加法（<math>2N-2</math> 个实数加法），因此，计算使用DFT所有 <math>N</math> 点的值需要 <math>N^2</math> 复数乘法与 <math>N^2-N</math> 个复数加法。FFT则是能够在 <math>O(N\log{}N)</math> 次操作计算出相同结果的任何方法。更准确的说，所有已知的FFT算法都需要 <math>O(N\log{}N)</math> 次运算（技术上 <math>O</math> 只标记上界），虽然还没有已知的证据证明更低的复杂度是不可能的。

要说明FFT节省时间的方式，就得考虑复数相乘和相加的次数。直接计算DFT的值涉及到 <math>N^2</math> 次复数相乘和 <math>N(N-1)</math> 次复数相加（可以通过削去琐碎运算（如乘以1）来节省 <math>O(N)</math> 次运算）。众所周知的基2库利-图基算法，<math>N</math> 为2的幂，可以只用 <math>(N/2)\log_{2} N</math> 次复数乘法（再次忽略乘以1的简化）和 <math>N\log_{2} N</math> 次加法就可以得到相同结果。在实际中，现代计算机通常的实际性能通常不受算术运算的速度和对复杂主体的分析主导，但是从<math>O(N^2)</math>到<math>O(N\log{}N)</math>的总体改进仍然能够体现出来。

一般的简化理论

假设一个 <math>m\times n</math> 型矩阵 <math>\mathbf{S}</math> 可分解成列向量以及行向量相乘：

<math>\mathbf{S}=\begin{bmatrix} a_1 \\ a_2 \\ \vdots \\ a_m\end{bmatrix}\begin{bmatrix} b_1 & b_2 & \cdots & b_n\end{bmatrix}</math>

若 <math>\begin{bmatrix} a_1 & a_2 & \cdots & a_m\end{bmatrix}^T</math> 有 <math>M_0</math> 个相异的非平凡值（ <math>a_m\ne\pm2^k,a_m\ne\pm2^ka_n </math> 其中 <math> m\ne n</math> ）　

<math>\begin{bmatrix} b_1 & b_2 & \cdots & b_n\end{bmatrix}</math> 有 <math>N_0</math> 个相异的非平凡值

则 <math>\mathbf{S}</math> 共需要 <math>M_0\times N_0</math> 个乘法。

<math>\begin{bmatrix} Z[1] \\ Z[2] \\ \vdots \\ Z[N] \end{bmatrix}= \mathbf{S}\begin{bmatrix} X[1] \\ X[2] \\ \vdots \\ X[N]\end{bmatrix}=\begin{bmatrix} a_1 \\ a_2 \\ \vdots \\ a_m\end{bmatrix}\begin{bmatrix} b_1 & b_2 & \cdots & b_n\end{bmatrix}\begin{bmatrix} X[1] \\ X[2] \\ \vdots \\ X[N]\end{bmatrix}</math>

Step 1：<math>Z_a=b_1X[1]+b_2X[2]+\cdots+b_nX[N]</math>

Step 2：<math>Z[1]=a_1Z_a,Z[2]=a_2Z_a,\cdots,Z[N]=a_mZ_a</math>

简化理论的变型：

<math>\mathbf{S}=\begin{bmatrix} a_1 \\ a_2 \\ \vdots \\ a_m\end{bmatrix}\begin{bmatrix} b_1 & b_2 & \cdots & b_n\end{bmatrix}+\mathbf{S}_1</math>

<math>\mathbf{S}_1</math> 也是一个 <math>M\times N</math> 的矩阵。

若 <math>\mathbf{S}_1</math> 有 <math>P_1</math> 个值不等于 <math>0</math> ，则 <math>\mathbf{S}</math> 的乘法量上限为 <math>M_0+N_0+P_1</math> 。

快速傅里叶变换乘法量的计算

假设 <math>N= P_1 \times P_2 \times \cdots \times P_k </math>，其中 <math>P_1,P_2, \cdots , P_k </math> 彼此互素。

<math>P_k</math> 点DFT的乘法量为 <math>B_k</math> ，则 <math>N</math> 点DFT的乘法量为：

<math>\frac{N}{P_1}B_1+\frac{N}{P_2}B_2+\cdots\cdots+\frac{N}{P_k}B_k</math>

假设 <math>N=P^c</math>，<math>P</math> 是一个素数。

若 <math>N_1=P^a</math> 点的DFT需要的乘法量为 <math>B_1</math>

且 <math>n_1\times n_2</math> 当中（ <math> n_1=0,1,\cdots,N_1-1, \quad n_2=0,1, \cdots , N_2-1</math> ）

有 <math>D_1</math> 个值不为 <math>\frac{N}{12}</math> 及 <math>\frac{N}{8}</math> 的倍数，

有 <math>D_2</math> 个值为 <math>\frac{N}{12}</math> 及 <math>\frac{N}{8}</math> 的倍数，但不为 <math>\frac{N}{4}</math> 的倍数，

则 <math>N</math> 点DFT的乘法量为：

<math>N_2B_1+N_1B_2+3D_1+2D_2</math>

库利-图基算法

主条目：库利－图基快速傅里叶变换算法

库利-图基算法是最常见的FFT算法。这一方法以分治法为策略递归地将长度为<math>N=N_1 N_2</math>的离散傅里叶变换分解为长度为<math>N_1</math>的<math>N_2</math>个较短序列的离散傅里叶变换，以及与<math>\Omicron (N)</math>个旋转因子的复数乘法。

这种方法以及FFT的基本思路在1965年J. W. Cooley和J. W. Tukey合作发表An algorithm for the machine calculation of complex Fourier series之后开始为人所知。但后来发现，实际上这两位作者只是重新发明了高斯在1805年就已经提出的算法（此算法在历史上数次以各种形式被再次提出）。

库利-图基算法最有名的应用，是将序列长为 <math>N</math> 的DFT分割为两个长为 <math>N/2</math> 的子序列的DFT，因此这一应用只适用于序列长度为2的幂的DFT计算，即基2-FFT。实际上，如同高斯和Cooley与Tukey都指出的那样，Cooley-Tukey算法也可以用于序列长度 <math>N</math> 为任意因数分解形式的DFT，即混合基FFT，而且还可以应用于其他诸如分裂基FFT等变种。尽管Cooley-Tukey算法的基本思路是采用递归的方法进行计算，大多数传统的算法实现都将显式的递归算法改写为非递归的形式。另外，因为Cooley-Tukey算法是将DFT分解为较小长度的多个DFT，因此它可以同任一种其他的DFT算法联合使用。

设计思想

下面，我们用 <math>N</math> 次单位根 <math>W_{N}</math> 来表示 <math>e^{-j\frac{2\pi}{N}}</math> 。

<math>W_{N}</math> 的性质：

1. 周期性，<math>W_{N}</math>具有周期<math>N</math>，即<math>W_{N}^{k+N}=W_{N}^{k}</math>
2. 对称性：<math>W_{N}^{k+N/2}=-W_{N}^{k}</math>。
3. 若<math>m</math>是<math>N</math>的约数，<math>W_{N}^{mkn}=W_{N/m}^{kn}</math>

为了简单起见，我们下面设待变换序列长度 <math>n=2^r</math> 。根据上面单位根的对称性，求级数 <math>y_k=\sum_{n=0}^{N-1} W_{N}^{kn}x_n</math> 时，可以将求和区间分为两部分：

<math>\begin{matrix}y_k=\sum_{n=2t} W_{N}^{kn} x_n + \sum_{n=2t+1} W_{N}^{kn}x_n\\= \sum_{t} W_{\frac{N}{2}}^{kt}x_{2t} + W_{N}^{k}\sum_{t} W_{\frac{N}{2}}^{kt}x_{2t+1}\\= F_{even}(k) + W_{N}^{k}F_{odd}(k)&&&&&&(i\in\mathbb{Z})\end{matrix}</math>

<math>F_{odd}(k)</math> 和 <math>F_{even}(k)</math> 是两个分别关于序列 <math>\left\{x_n\right\}_0^{N-1}</math> 奇数号和偶数号序列N/2点变换。由此式只需计算出 <math>y_k</math> 的前 <math>N/2</math> 个点，对于后N/2个点可以通过复指数函数的对称性快速求解。即，注意 <math>F_{odd}(k)</math> 和 <math>F_{even}(k)</math> 都是周期为 <math>N/2</math> 的函数，由单位根的对称性，有以下变换公式：

• <math>y_{k+\frac{N}{2}} = F_{even}(k) - W_{N}^{k}F_{odd}(k)</math>
• <math>y_k = F_{even}(k) + W_{N}^{k}F_{odd}(k)</math>。

这样，一个 <math>N</math> 点变换就分解成了两个 <math>N/2</math> 点变换。照这样可继续分解下去。这就是库利-图基快速傅里叶变换算法的基本原理。根据主定理不难分析出此时算法的时间复杂度为<math>\Omicron (N\log N)</math>.

算法实现

• 蝶形结网络和位反转（Bit Reversal）：

首先将<math>n=2^N</math>个输入点列按二进制进行编号，然后对各个编号按位倒置并按此重新排序。例如，对于一个8点变换，

001倒置以后变成 100

000 → 000

001 → 100

010 → 010

011 → 110

100 → 001

101 → 101

110 → 011

111 → 111

倒置后的编号为{0,4,2,6,1,5,3,7}。

然后将这n个点列作为输入传送到蝶形结网络中，注意将因子 <math>W_{N}^{k}</math> 逐层加入到蝶形网络中。

算法复杂度

由于按蝶形结网络计算 <math>n</math> 点变换要进行 <math>\log{} n</math> 层计算，每层计算n个点的变换，故算法的时间复杂度为<math>\Omicron (n \log n)</math> 。

其他算法

在Cooley-Tukey算法之外还有其他DFT的快速算法。对于长度 <math>N = N_1N_2</math> 且 <math>N_1</math> 与 <math>N_2</math> 互质的序列，可以采用基于中国剩余定理的互素因子算法将N长序列的DFT分解为两个子序列的DFT。与Cooley-Tukey算法不同的是，互素因子算法不需要旋转因子。

Rader-Brenner算法是类似于Cooley-Tukey算法，但是采用的旋转因子都是纯虚数，以增加加法运算和降低了数值稳定性为代价减少了乘法运算。这方法之后被split-radix variant of Cooley-Tukey所取代，与Rader-Brenner算法相比，有一样多的乘法量，却有较少的加法量，且不牺牲数值的准确性。

Bruun以及QFT算法是不断的把DFT分成许多较小的DFT运算。（Rader-Brenner以及QFT算法是为了2的指数所设计的算法，但依然可以适用在可分解的整数上。Bruun算法则可以运用在可被分成偶数个运算的数字）。尤其是Bruun算法，把FFT看成是 <math>z^N-1</math> ，并把它分解成 <math>z^{M-1}</math>与<math>z^{2M}+az^M+1</math> 的形式。

另一个从多项式观点的快速傅立叶变换法是Winograd算法。此算法把 <math>z^N-1</math> 分解成cyclotomic多项式，而这些多项式的系数通常为1，0，-1。这样只需要很少的乘法量（如果有需要的话），所以winograd是可以得到最少乘法量的快速傅立叶算法，对于较小的数字，可以找出有效率的算方式。更精确地说，winograd算法让DFT可以用 <math>2^k</math> 点的DFT来简化，但减少乘法量的同时，也增加了非常多的加法量。Winograd也可以利用剩余值定理来简化DFT。

Rader算法提出了利用点数为N（N为素数）的DFT进行长度为N-1的回旋折积来表示原本的DFT，如此就可利用折积用一对基本的FFT来计算DFT。另一个prime-size的FFT算法为chirp-Z算法。此法也是将DFT用折积来表示，此法与Rader算法相比，能运用在更一般的转换上，其转换的基础为Z转换（Rabiner et al., 1969）。

实数或对称资料专用的算法

在许多的运用当中，要进行DFT的资料是纯实数，如此一来经过DFT的结果会满足对称性：

<math>\mathbf{X}_{N-k}</math>=<math>\mathbf{X}_k^*</math>

而有一些算法是专门为这种情形设计的（e.g. Sorensen, 1987）。另一些则是利用旧有的算法（e.g. Cooley-Tukey），删去一些不必要的演算步骤，如此省下了记忆体的使用，也省下了时间。另一方面，也可以把一个偶数长度且纯实数的DFT，用长度为原本一半的复数型态DFT来表示（实数项为原本纯实数资料的偶数项，虚数项则为奇数项）。

在Matlab上用一次N点FFT计算两个N点实数信号x,y的FFT:

function [X,Y] = Real2FFT( x,y )

% N-point FFT is used for 2 real signals both with length N

N = length(x);

z = x+y*i ;

Z = fft(z);

X = 0.5*(Z+conj(Z(1+mod(0:-1:1-N,N))));

Y = 0.5*(Z-conj(Z(1+mod(0:-1:1-N,N))))/i;

end

一度人们认为，用离散哈特利转换（Discrete Hartley Transform）来处理纯实数的DFT会更有效率，但接着人们发现，对于同样点数的纯实数DFT，经过设计的FFT，可以比DHT省下更多的运算。Bruun算法是第一个试着从减少实数输入的DFT运算量的算法，但此法并没有成为人们普遍使用的方法。

对于实数输入，且输入为偶对称或奇对称的情形，可以更进一步的省下时间以及记忆体，此时DFT可以用离散余弦转换或离散正弦转换来代替（Discrete cosine/sine transforms）。由于DCT/DST也可以设计出FFT的算法，故在此种情形下，此方法取代了对DFT设计的FFT算法。

DFT可以应用在频谱分析以及做折积的运算，而在此处，不同应用可以用不同的算法来取代，列表如下：

用来做频谱分析的情况下，DFT可用下列的算法代替：

• DCT
• DST
• DHT
• 正交基底的扩展（orthogonal basis expantion）包括正交多项式（orthogonal polynomials）以及CDMA.
• Walsh（Hadamard）转换
• Haar转换
• 小波（wavelet）转换
• 时频分布（time-frequency distribution）

用来做折积的情况下，DFT可用下列的算法代替：

• DCT
• DST
• DHT
• 直接做折积（direct computing）
• 分段式DFT折积（sectioned DFT convolution）
• 威诺格拉德快速傅里叶变换算法
• 沃尔什（Walsh、Hadamard）转换
• 数论转换

单一路径延迟回授系统

单一路径延迟回授系统(英语：Single-path delay feedback，缩写为SDF)是一种用于实现快速傅里叶变换(Fast Fourier Transform)中运算的流水线式架构(pipeline architecture)。此架构的特点是资料从输入一直到最终的输出只会通过单一的路径，并使用蝶形结(butterfly diagram)做为资料的运算单元。经过蝶形结后的输出资料会先暂存在系统的移位寄存器(shift registers)或是随机存储器(RAM)当中，而由于只有单一路径的关系，对于每一级的蝶形结架构我们只需要一个复数乘法器来进行和FFT当中的旋转因子(twiddle factor)的乘积运算。

SDF的优点在于其架构简单并且利用硬件实现的成本较低，原因在于其单一路径的设计，使得资料会依序进行处理并输出，并不会在系统中加入多个复杂的运算单元以进行平行化的运算，事实上SDF的架构在流水线式快速傅里叶变换处理器(pipelined FFT processors)中具有最高的存储器使用效率，而由于存储器单元数量会随快速傅里叶变换的级数而指数增长，存储器使用效率进而成为影响电路面积和功耗的主要因素之一。因此在实现大型快速傅里叶变换处理器的情况下，SDF架构一直是被优先考量采用的选择。然而其缺点也同样来自于单一路径的设计，导致其吞吐量(throughput)和多路径延迟交换线路系统(英语：Multiple-path delay commutator，缩写为MDC)相比较低。

接着我们将以8个点的基-2单一路径延迟回授系统(8-point R2SDF)为例进行其算法细节的介绍，并且展示在硬件实现中每一个cycle的运算和中间结果的存储位置。

File:New R2SDF.jpg

8-point R2SDF Architecture

首先考虑系统输入为x₀, x₁, ..., x_7，并在前8个cycle依序输入。

• Cycle 0~3: x₀~x₃依序存入第一级BF-2上方的寄存器中。
• Cycle 4: x₀和x₄输入第一级BF-2后输出x₀^'和x₄^'，x₀^'存入第二级BF-2上方的寄存器中，x₄^'存入第一级BF-2上方的寄存器中。
• Cycle 5: x₁和x₅输入第一级BF-2后输出x₁^'和x₅^'，x₁^'存入第二级BF-2上方的寄存器中，x₅^'存入第一级BF-2上方的寄存器中。
• Cycle 6: x₂和x₆输入第一级BF-2后输出x₂^'和x₆^'，x₆^'存入第一级BF-2上方的寄存器中，x₀^'和x₂^'输入第二级BF-2后输出x₀^''和x₂^''，x₀^''存入第三级BF-2上方的寄存器中，x₂^''存入第二级BF-2上方的寄存器中。
• Cycle 7: x₃和x₇输入第一级BF-2后输出x₃^'和x₇^'，x₇^'存入第一级BF-2上方的寄存器中，x₁^'和x₃^'输入第二级BF-2后输出x₁^''和x₃^''，x₃^''存入第二级BF-2上方的寄存器中，x₀^''和x₁^''输入第三级BF-2后输出x₀^'''和x₁^'''，x₀^'''直接输出，x₁^'''存入第三级BF-2上方的寄存器中。(此为第一笔输出，此后每一个cycle皆会输出一笔资料。)
• Cycle 8: x₄^'乘上W⁰后存入第二级BF-2上方的寄存器中，x₂^''乘上W⁰后存入第三级BF-2上方的寄存器中，x₁^'''直接输出。
• Cycle 9: x₅^'乘上W¹后存入第二级BF-2上方的寄存器中，x₃^''乘上W²后和x₂^''输入第三级BF-2后输出x₂^'''和x₃^'''， x₂^'''直接输出，x₃^'''存入第三级BF-2上方的寄存器中。
• Cycle 10: x₆^'乘上W²后和x₄^'输入第二级BF-2后输出x₄^''和x₆^''，x₆^''存入第二级BF-2上方的寄存器中，x₄^''存入第三级BF-2上方的寄存器中，x₃^'''直接输出。
• Cycle 11: x₇^'乘上W³后和x₅^'输入第二级BF-2后输出x₅^''和x₇^''，x₇^''存入第二级BF-2上方的寄存器中，x₄^''和x₅^''输入第三级BF-2后输出x₄^'''和x₅^'''，x₄^'''直接输出，x₅^'''存入第三级BF-2上方的寄存器中。
• Cycle 12: x₆^''乘上W⁰后存入第三级BF-2上方的寄存器中，x₅^'''直接输出。
• Cycle 13: x₇^''乘上W²后和x₆^''输入第三级BF-2后输出x₆^'''和x₇^'''，x₆^'''直接输出，x₇^'''存入第三级BF-2上方的寄存器中。
• Cycle 14: x₇^'''直接输出。(此为最后一笔输出。)

此外，我们可以在蝶形结中的加法器和乘法器加上额外的寄存器(register)来降低系统的关键路径(critical path)，来避免某些时刻不同级之间的繁重运算必须挤在同一个cycle中运算完成，进而严重影响整体电路在timing上的表现。但如此的流水线式设计(pipeline design)也会增加整体电路的延迟(latency)和寄存器使用量。

相似架构之硬件实现比较

1. Radix-2 SDF: 2(log₄N-1) 个乘法器、4log₄N 个加法器、存储器大小为 N-1。
2. Radix-4 SDF: log₄N-1 个乘法器、8log₄N 个加法器、存储器大小为 N-1。
3. Radix-2² SDF: log₄N-1 个乘法器、4log₄N 个加法器、存储器大小为 N-1。
4. Radix-2 MDC: 2(log₄N-1) 个乘法器、4log₄N 个加法器、存储器大小为 1.5N-2。
5. Radix-4 MDC: 3(log₄N-1) 个乘法器、8log₄N 个加法器、存储器大小为 2.5N-4。
6. Radix-4 SDC: log₄N-1 个乘法器、3log₄N 个加法器、存储器大小为 2N-2。

复杂度以及运算量的极限

长久以来，人们对于求出快速傅里叶变换的复杂度下限以及需要多少的运算量感到很有兴趣，而实际上也还有许多问题需要解决。即使是用较简单的情形，即 <math>2^k</math> 点的DFT，也还没能够严谨的证明出FFT至少需要 <math>\Omega (N\log N)</math> （不比 <math>N\log N</math> 小）的运算量，目前也没有发现复杂度更低的算法。通常量学运算量的多寡会是运算效率好坏最主要的因素，但在现实中，有许多因素也会有很大的影响，如缓冲存储器以及CPU均有很大的影响。

在1978年，Winograd率先导出一个较严谨的FFT所需乘法量的下限： <math>\Theta (N)</math> 。当 <math>N=2^k</math> 时，DFT只需要 <math>4N-2\log_{2}^2N-2\log_{2}N-4</math> 次无理实数的乘法即可以计算出来。更详尽，且也能趋近此下限的算法也一一被提出（Heideman & Burrus, 1986; Duhamel, 1990）。很可惜的是，这些算法，都需要很大量的加法计算，目前的硬件无法克服这个问题。

对于所需加法量的数目，虽然我们可以在某些受限制的假设下，推得其下限，但目前并没有一个精确的下限被推导出来。1973年，Morgenstern在乘法常量趋近巨大的情形下（对大部分的FFT算法为真，但不是全部）推导出加法量的下限： <math>\Omega \left(N \log N \right)</math> 。Pan（1986）在假设FFT算法的不同步的情形有其极限下证明出加法量的下限 <math>\Omega (NlogN)</math> ，但一般来说，此假设相当的不明确。长度为 <math>N=2^k</math> 的情形下，在某些假设下，Papadimitriou（1979）提出使用Cooley-Tukey算法所需的复数加法量 <math>N\log_{2}N</math> 是最少的。到目前为止，在长度为 <math>N=2^k</math> 情况，还没有任何FFT的算法可以让复数的加法量 比<math>N\log_{2}N</math> 还少。

还有一个问题是如何把乘法量与加法量的总和最小化，有时候称作"演算复杂度"（在这里考虑的是实际的运算量，而不是渐近复杂度）。同样的，没有一个严谨下限被证明出来。从1968年开始，<math>N=2^k</math>点DFT而言，split-radix FFT算法需要最少的运算量，在 <math>N>1</math> 的情形下，其需要 <math>4N\log_{2}N-6N+8</math> 个乘法运算以及加法运算。最近有人导出更低的运算量： <math>\frac{34}{9}N\log_{2}N</math> 。（Johnson and Frigo, 2007; Lundy and Van Buskirk, 2007）

大多数尝试要降低或者证明FFT复杂度下限的人都把焦点放在复数资料输入的情况，因其为最简单的情形。但是，复数资料输入的FFT算法，与实数资料输入的FFT算法，离散余弦变换（DCT），离散哈特列变换（DHT），以及其他的算法，均有很大的关连性。故任何一个算法，在复杂度上有任何的改善的话，其他的算法复杂度也会马上获得改善（Duhamel & Vetterli, 1990）。

快速算法查表

对于 <math>N</math> 点的DFT:

<math>N</math> = 1~60

N	乘法数	加法数	N	乘法数	N	乘法数	N	乘法数
1	0	0	11	46	24	28	39	182
2	0	4	12	8	25	148	40	100
3	2	12	13	52	26	104	42	124
4	0	16	14	32	27	114	44	160
5	10	34	15	40	28	64	45	170
6	4	36	16	20	30	80	48	92
7	16	72	18	32	32	72	52	208
8	4	52	20	40	33	160	54	228
9	16	72	21	62	35	150	56	156
10	20	88	22	80	36	64	60	160

<math>N</math> < 1000

N	乘法数	N	乘法数	N	乘法数	N	乘法数
63	256	96	280	192	752	360	1540
64	204	104	468	204	976	420	2080
66	284	108	456	216	1020	480	2360
70	300	112	396	224	1016	504	2300
72	164	120	380	240	940	512	3180
80	260	128	560	252	1024	560	3100
81	480	144	436	256	1308	672	3496
84	248	160	680	288	1160	720	3620
88	412	168	580	312	1324	784	4412
90	340	180	680	336	1412	840	4580

<math>N</math> > 1000

N	乘法数	N	乘法数	N	乘法数	N	乘法数
1008	5356	1440	8680	2520	16540	4032	29488
1024	7436	1680	10420	2688	19108	4096	37516
1152	7088	2016	12728	2880	20060	4368	35828
1260	7640	2048	16836	3369	24200	4608	36812
1344	8252	2304	15868	3920	29900	5040	36860

其他 <math>N</math> 的算法:

(1)若 <math>N</math> 可被两个以上互素的数相乘得到

设 <math>N = P_1\times P_2</math> ，且 <math>P_1</math> 与 <math>P_2</math> 互素(无须 <math>P_1</math> 与 <math>P_2</math> 为素数):

则当输入信号长度为N所需之的乘法器 <math>=P_1 \times B_2+P_2 \times B_1</math>，

其中 <math>B_1</math> 为 <math>P_1</math>点DFT乘法量， <math>B_2</math> 为 <math>P_2</math> 点DFT乘法量。

例如: <math>N=65</math> 可以拆成 <math>65=5\times 13</math> ，其中5与13互素，

借由查表可得知5点 DFT乘法量为10，13点DFT乘法量为52，

所以65点DFT乘法量为 <math>5\times52 + 13\times10 = 390</math> 。

扩展:

设 <math>N = P_1\times P_2\times\cdot\cdot\cdot\times P_K</math>，且 <math>P_1\times P_2\times\cdot\cdot\cdot\times P_K</math> 互素，

<math>P_k</math> 点DFT乘法量为 <math>B_k</math> ，

则 <math>N</math> 点DFT可分解为 <math>N/P_1</math> 个<math>P_1</math>-point DFT+<math>N/P_2</math> 个 <math>P_2</math>-point DFT+<math>\cdot\cdot\cdot</math>+<math>N/P_K</math> 个<math>P_K</math>-point DFT ，

总乘法量为 <math>\frac{N}{P_1}B_1+\frac{N}{P_2}B_2+ \cdots +\frac{N}{P_K}B_K</math>

(2)若N不可被两个互素的数相乘得到

设 <math>N = P_1\times P_2</math> ，且 <math>P_1</math> 与 <math>P_2</math> 不互素:

且 <math>n \times m</math> 当中( <math>n = 1,2,...,P_1-1</math>，<math>m = 1,2,...,P_2-1</math> )，

有 <math>D_1</math> 个值不为 <math>N/12</math> 及 <math>N/8</math> 的倍数，

有 <math>D_2</math> 个值为 <math>N/12</math> 或 <math>N/8</math> 的倍数，但不为 <math>N/4</math> 的倍数。

则 <math>N</math> 点DFT所需之的乘法量 <math>=P_1 \times B_2+P_2 \times B_1+3D_1+2D_2</math>，

其中 <math>B_1</math> 为 <math>P_1</math> 点DFT乘法量， <math>B_2</math> 为 <math>P_2</math> 点DFT乘法量。

例如:16点DFT， <math>16=8 \times 2</math>

乘法量 <math>=2 \times 4 + 8 \times 0+3 \times 4+2 \times 2=24</math>

或 <math>16=4 \times 4</math>

乘法量 <math>=4 \times 0 + 4 \times 0 +3 \times 4+2 \times 4=20</math>

FFT的应用

快速傅里叶变换可将卷积化乘法并以对数级数降低运算量，已成数字信号与科学计算核心工具。

其应用涵盖：

1.音频与影像压缩

MP3、AAC 与 JPEG 均把信号分块后先作 FFT／MDCT，以把时域样本转到频域；高能量系数集中于低频，小幅子载波便能重现重要消息。接着结合人耳／视觉掩蔽模型及 Zig-zag 扫描，将低感知值系数量化为零，大幅降低比特率。最后用霍夫曼或算术编码存储系数与量化步阶，达到有损压缩与可调画质／音质的目的。若不经 FFT，逐点卷积将耗费 O(N²) 运算，无法在即时设备上完成。

2.无线通信

现代蜂窝网络与 Wi-Fi 系统皆采正交分频多工 (OFDM)。基站先将并发调变符号经 IFFT 合成等间隔子载波；终端则以 FFT 还原频域资料。此架构可在多径通道中保持子载波互不干扰，同时透过可变子载波间距支撑 5G NR 的 eMBB 与 mMTC 场景。运用循环前缀可把时域卷积化为频域乘法，等效频率选择通道简化为每载波一次复数乘法，计算量对比传统单载波大幅减少。

3.频谱分析与测试仪器

FFT 让示波器、功率分析仪与机房电力质量监控能在毫秒级显示功率频谱。将长度 N 的窗函数样本取 FFT 后，平方其复数幅度并适当标准化，即得单／双边功率谱密度 (PSD)。工程师可由此快速识别谐波、噪声底或机械转速边带；科学领域亦用来分析地震波与星体光谱。无须昂贵的扫频式分析器，即可精确估测频率分量与相位。

4.图像处理与快速卷积

空间滤波、去模糊及模板匹配常利用“乘频域、回时域”策略：对影像与滤波器 PSF 取 FFT，相乘后作 IFFT，即得卷积结果，计算量 <math>O(N^2)</math> 降为 <math>O(N\log{} N)</math> 。在盲去模糊或维纳解卷积中，亦可用频域除法抑制模糊并保留高频细节。此方法支持任意遮罩大小，远优于滑动视窗直接卷积，适用医学影像与天文摄影等高清晰度场景。

5.雷达／声纳脉冲压缩

雷达为兼顾高清晰与大探测距离，常发射长码调变脉冲并于接收端做匹配滤波。将回波与已知码序列分别取 FFT，相乘后 IFFT，即可在频域完成相关；此“脉冲压缩”技术能在固定峰值功率下获得窄等效脉冲宽，提升距离分辨率与信杂比，并大幅降低即时硬件乘加数。

6.多项式乘法与同态加密

在多项式乘法或卷积为瓶颈的应用（例如格基同态加密、FFT-based 大数计算）中，先将系数以 NTT/FFT 转到频域，再做逐点乘法，最后逆变换还原，即可把 <math>O(N^2)</math> 乘法降至 <math>O(N\log{} N)</math> 。加密函数库 SEAL、HElib 均内置此优化，使百万阶多项式运算在一般 CPU 上于毫秒内完成，直接左右现代隐私计算性能。

由此可见，FFT已由数学算法演变为支撑信息社会不可或缺的基础技术。

参阅

• 离散傅里叶变换
• 并行快速傅里叶变换
• 快速数论变换

延伸阅读

• Brenner, N.; Rader, C. A New Principle for Fast Fourier Transformation. IEEE Acoustics, Speech & Signal Processing. 1976, 24 (3): 264–266. doi:10.1109/TASSP.1976.1162805. 
• Brigham, E. O. The Fast Fourier Transform. New York: Prentice-Hall. 2002. 
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. 30. (Polynomials and the FFT). Introduction to Algorithms 2. MIT Press and McGraw-Hill. 2001. ISBN 0-262-03293-7. 
• Duhamel, Pierre. Algorithms meeting the lower bounds on the multiplicative complexity of length-2ⁿ DFTs and their connection with practical algorithms. IEEE Trans. Acoust. Speech. Sig. Proc. 1990, 38 (9): 1504–151. doi:10.1109/29.60070. 
• Duhamel, P.; Vetterli, M. Fast Fourier transforms: a tutorial review and a state of the art. Signal Processing. 1990, 19: 259–299. doi:10.1016/0165-1684(90)90158-U. 
• Edelman, A.; McCorquodale, P.; Toledo, S. The Future Fast Fourier Transform?. SIAM J. Sci. Computing. 1999, 20: 1094–1114. doi:10.1137/S1064827597316266. 
• D. F. Elliott, & K. R. Rao, 1982, Fast transforms: Algorithms, analyses, applications. New York: Academic Press.
• Funda Ergün, 1995, , Proc. 27th ACM Symposium on the Theory of Computing: 407–416.
• Frigo, M.; Johnson, S. G. The Design and Implementation of FFTW3 (PDF). Proceedings of the IEEE. 2005, 93: 216–231 [2008-06-22]. doi:10.1109/jproc.2004.840301. （原始内容存档 (PDF)于2019-07-16）. 
• H. Guo and C. S. Burrus, 1996, , Proc. SPIE Intl. Soc. Opt. Eng. 2825: 250–259.
• H. Guo, G. A. Sitton, C. S. Burrus, 1994, , Proc. IEEE Conf. Acoust. Speech and Sig. Processing (ICASSP) 3: 445–448.
• Steve Haynal and Heidi Haynal, "Generating and Searching Families of FFT Algorithms", Journal on Satisfiability, Boolean Modeling and Computation vol. 7, pp. 145–187 (2011).
• Heideman, Michael T.; Burrus, C. Sidney. On the number of multiplications necessary to compute a length-2ⁿ DFT. IEEE Trans. Acoust. Speech. Sig. Proc. 1986, 34 (1): 91–95. doi:10.1109/TASSP.1986.1164785. 
• Johnson, S. G.; Frigo, M. A modified split-radix FFT with fewer arithmetic operations (PDF). IEEE Trans. Signal Processing. 2007, 55 (1): 111–119 [2008-06-22]. doi:10.1109/tsp.2006.882087. （原始内容存档 (PDF)于2021-02-25）. 
• T. Lundy and J. Van Buskirk, 2007. "A new matrix approach to real FFTs and convolutions of length 2^k," Computing 80 (1): 23–45.
• Kent, Ray D. and Read, Charles (2002). Acoustic Analysis of Speech. ISBN 978-0-7693-0112-9. Cites Strang, G. (1994)/May–June). Wavelets. American Scientist, 82, 250–255.
• Morgenstern, Jacques. Note on a lower bound of the linear complexity of the fast Fourier transform. J. ACM. 1973, 20 (2): 305–306. doi:10.1145/321752.321761. 
• Mohlenkamp, M. J. A fast transform for spherical harmonics (PDF). J. Fourier Anal. Appl. 1999, 5 (2–3): 159–184. doi:10.1007/BF01261607. （原始内容 (PDF)存档于2007年2月6日）. 
• Nussbaumer, H. J. Digital filtering using polynomial transforms. Electronics Lett. 1977, 13 (13): 386–387. doi:10.1049/el:19770280. 
• V. Pan, 1986, , Information Proc. Lett. 22: 11–14.
• Christos H. Papadimitriou, 1979, , J. ACM 26: 95–102.
• D. Potts, G. Steidl, and M. Tasche, 2001. "Fast Fourier transforms for nonequispaced data: A tutorial （页面存档备份，存于互联网档案馆）", in: J.J. Benedetto and P. Ferreira (Eds.), Modern Sampling Theory: Mathematics and Applications (Birkhauser).
• Press, W.H.; Teukolsky, S.A.; Vetterling, W.T.; Flannery, B.P., Chapter 12. Fast Fourier Transform, Numerical Recipes: The Art of Scientific Computing 3, New York: Cambridge University Press, 2007 [2015-12-11], ISBN 978-0-521-88068-8, （原始内容存档于2011-08-11） 
• Rokhlin, Vladimir; Tygert, Mark. Fast algorithms for spherical harmonic expansions. SIAM J. Sci. Computing. 2006, 27 (6): 1903–1928. doi:10.1137/050623073. 
• Schatzman, James C. Accuracy of the discrete Fourier transform and the fast Fourier transform. SIAM J. Sci. Comput. 1996, 17: 1150–1166. doi:10.1137/s1064827593247023. 
• Shentov, O. V.; Mitra, S. K.; Heute, U.; Hossen, A. N. Subband DFT. I. Definition, interpretations and extensions. Signal Processing. 1995, 41 (3): 261–277. doi:10.1016/0165-1684(94)00103-7. 
• Sorensen, H. V.; Jones, D. L.; Heideman, M. T.; Burrus, C. S. Real-valued fast Fourier transform algorithms. IEEE Trans. Acoust. Speech Sig. Processing. 1987, 35 (35): 849–863. doi:10.1109/TASSP.1987.1165220.  See also Sorensen, H.; Jones, D.; Heideman, M.; Burrus, C. Corrections to "Real-valued fast Fourier transform algorithms". IEEE Transactions on Acoustics, Speech, and Signal Processing. 1987, 35 (9): 1353–1353. doi:10.1109/TASSP.1987.1165284. 
• Welch, Peter D. A fixed-point fast Fourier transform error analysis. IEEE Trans. Audio Electroacoustics. 1969, 17 (2): 151–157. doi:10.1109/TAU.1969.1162035. 
• Winograd, S. On computing the discrete Fourier transform. Math. Computation. 1978, 32 (141): 175–199. JSTOR 2006266. doi:10.1090/S0025-5718-1978-0468306-4.