快速傅里叶变换 · aiwiki.page

快速傅里叶变换（FFT）是一种高效计算离散傅里叶变换（DFT）或其逆变换的算法。FFT 并不定义另一种数学变换，而是重新组织 DFT 的计算过程，以复用中间结果。标准 FFT 方法将 $N$ 个采样点的变换所需的算术运算量从 $O(N^2)$ 降至 $O(N\log N)$ ，使大规模数据集的傅里叶分析切实可行。FFT 是信号处理和科学计算中的基础工具。(fftw.org)

数学定义

对于由复数组成的序列 $x_0,x_1,\ldots,x_{N-1}$ ，一种常见约定将 DFT 定义为

X_k=\sum_{n=0}^{N-1}x_n e^{-2\pi i nk/N}, \qquad k=0,\ldots,N-1,

其中 $i^2=-1$ 。其逆变换为

x_n=\frac{1}{N}\sum_{k=0}^{N-1}X_k e^{2\pi i nk/N}.

FFT 能更高效地计算这些有限项求和；在精确算术下，其结果与直接计算完全相同。不同实现采用的符号和归一化约定有所不同：有些将因子 $1/N$ 放在正变换中，而酉归一化约定则在正、逆两个方向上都使用 $1/\sqrt N$ 。(numpy.org)

DFT 是傅里叶变换的有限维对应形式。对于均匀采样的时域数据，其输出描述了离散网格上的频率分量。若采样频率为 $f_s$ ，则相邻频点的间隔为 $f_s/N$ 。在通常的输出排列中，零频分量位于首位，其后依次是正频率分量和解释为负频率的分量。(numpy.org)

直接计算需要求出 $N$ 个和，每个和都包含 $N$ 项。其平方级的计算复杂性与 FFT 接近线性的运算量形成对比。用大O记号表示的 $O(N\log N)$ 描述的是渐近增长规律，而非固定的执行时间或加速倍数。(sigproc.mit.edu)

库利–图基原理

最广为人知的 FFT 算法族是库利–图基算法。它采用分治法：将长度为合数的变换分解为较小的变换，再用复数相位因子组合这些变换的输出。(fftw.org)

基 2 分解

当 $N$ 为偶数时，将输入分为偶数索引和奇数索引两组采样点：

E_k=\sum_{m=0}^{N/2-1}x_{2m} e^{-2\pi i mk/(N/2)},

O_k=\sum_{m=0}^{N/2-1}x_{2m+1} e^{-2\pi i mk/(N/2)}.

记 $W_N=e^{-2\pi i/N}$ ，则原变换可写为

X_k=E_k+W_N^kO_k,

X_{k+N/2}=E_k-W_N^kO_k, \qquad 0\leq k<N/2.

因此，两个长度为 $N/2$ 的变换只需额外进行线性数量的运算，就能得到全部 $N$ 个输出。这种成对的加减运算称为蝶形运算，而 $W_N^k$ 称为旋转因子。(sigproc.mit.edu)

当 $N=2^m$ 时，反复进行递归分解会产生 $\log_2 N$ 个阶段。对应的递推关系为

T(N)=2T(N/2)+O(N),

由此得到 $T(N)=O(N\log N)$ 。加速来自对子计算结果的复用以及复指数的结构，而不是舍弃某些项或对变换进行近似。(sigproc.mit.edu)

其他因数分解

库利–图基算法并不限于长度为二的幂的情形。若 $N=ab$ ，就可以将其分解为长度为 $a$ 和 $b$ 的变换，并配合旋转因子乘法及索引重排。混合基算法结合不同的因子；分裂基算法则结合不同规模的分解，通常将一个长度为 $N/2$ 的变换与两个长度为 $N/4$ 的变换组合起来。(fftw.org)

算法族与变换长度

不同的 FFT 方法利用不同的算术结构：

素因子算法，又称古德–托马斯算法，利用 $N$ 的互素因子，避免相应的库利–图基分解所需的阶段间旋转因子。
雷德算法将长度为素数 $p$ 的变换中除零频项以外的部分，转换为长度为 $p-1$ 的循环卷积。
布鲁斯坦算法利用二次相位因子将 DFT 改写为卷积。它适用于任意长度，包括素数长度。
分裂基方法通过组合不同的递归分解，力求减少算术运算次数。(fftw.org)

因此，FFT 本身并不要求输入长度为二的幂。具有小素因子的长度往往便于计算，但高效实现也能以 $O(N\log N)$ 次运算完成素数长度的变换。将数据填充到另一长度可能缩短执行时间，但也会改变所计算的变换。(fftw.org)

实数与多维变换

对于实数输入，输出具有共轭对称性：

X_{N-k}=\overline{X_k},

其中索引按模 $N$ 解释。因此，约一半的频域数值是冗余的。实数输入 FFT 算法利用这种对称性来减少计算量和存储需求。零频系数是实数；当 $N$ 为偶数时，奈奎斯特频率处的系数也是实数。(numpy.org)

多维 DFT 具有可分离性：沿数组的每个维度分别进行一维变换，即可完成计算。例如，二维变换可以先对每一行进行变换，再对每一列进行变换。对于维数固定、包含 $M$ 个元素的数组，这种方法的算术运算量为 $O(M\log M)$ 。多维 FFT 为图像处理和计算科学中的应用提供了支持。(fftw.org)

应用

频谱分析

FFT 将采样信号转换为频域表示，从而可以分析振荡、幅度和相位。它被用于音频分析及其他信号处理领域。对连续的数据片段分别进行变换，可以观察频谱内容随时间的变化，而不是只得到整段记录的单一频谱。(numpy.org)

快速卷积与滤波

卷积定理将一个域中的卷积与另一个域中的乘法联系起来。采用上述归一化约定，有

x\circledast h= \operatorname{IDFT}\!\left( \operatorname{DFT}(x)\operatorname{DFT}(h) \right),

其中乘法为逐元素相乘， $\circledast$ 表示循环卷积。这为长序列的滤波提供了一种高效途径。(mathworks.com)

循环卷积并不天然等同于线性卷积。对于长度分别为 $L$ 和 $M$ 的序列，必须将两者补零至相同的变换长度，且该长度至少为 $L+M-1$ ，才能得到完整的线性卷积而不发生回绕。基于 FFT 的多项式乘法也以同样的系数卷积关系为基础。(mathworks.com)

数值计算

傅里叶变换方法也能辅助求解偏微分方程。沿空间维度进行变换可以简化适用的微分算子，但变换的选择必须与问题的边界条件相匹配。相关的快速余弦变换和快速正弦变换适用于不同的对称性和边界条件要求。(fftw.org)

实现与数值精度

性能并非仅由算术运算次数决定。内存访问、缓存行为、数据布局和处理器能力的影响，可能超过运算次数上的小幅差异。因此，优化实现会将小型专用变换内核与不同的分解方式和执行策略结合起来。(fftw.org)

一些程序库会在执行前构建一个执行计划，针对特定的变换长度、数据布局和机器选择实现方式。重复执行变换时，可以复用这一计划，从而分摊规划开销。FFTW 是这种自适应方法的典型代表。(fftw.org)

在浮点运算中，中间运算会引入舍入误差。因此，不同 FFT 算法即使对应同一个精确变换，也可能产生略有差异的数值输出。实现得当的库利–图基方法具有良好的数值稳定性，但旋转因子的精度十分重要：若生成这些因子时所用的递推方式选择不当，就可能累积显著误差。(fftw.org)

结果解释与局限

FFT 加快的是计算过程，并不能消除采样数据本身的局限。尤其是，补零会使有限长度记录的频谱采样更加密集，却不会提高其分辨相近频率分量的内在能力。这种能力取决于原始观测时长和采样率。(mathworks.com)

归一化方式和输出顺序也很重要。原始系数、归一化幅度和功率谱是不同的表示形式；实数输入的单边频谱需要恰当处理冗余的负频率分量。比较不同实现时，必须考虑各自的符号、缩放和排列约定。(numpy.org)

如果只需要少量频率分量，就不一定要计算完整的 FFT。专用方法或剪枝方法可以只计算选定的输出，但节省多少计算量，取决于所需输出的数量以及实现本身的开销。(fftw.org)

历史

类似 FFT 的分解方法早于电子计算机出现。卡尔·弗里德里希·高斯在 1805 年描述过一种方法，后来被认定为库利–图基方法的早期形式。这一联系是通过后来的历史研究确立的。(ftp.fftw.org)

现代 FFT 的广泛应用始于詹姆斯·W.·库利和约翰·W.·图基于 1965 年发表的论文《复傅里叶级数的机器计算算法》。他们阐明了如何通过对变换长度进行因数分解，大幅减少计算工作量。此后的研究发展出更多算法、针对实数数据和多维数据的方法，以及面向特定计算机体系结构优化的实现。(research.ibm.com)

参考来源

FFTW Home Pagefftw.org
Discrete Fourier Transform (numpy.fft) — NumPy v2.2 Manualnumpy.org
FFTW FAQ - Section 3fftw.org
Fast Fourier Transform — 6.300: Signal Processingsigproc.mit.edu
The Design and Implementation of FFTW3fftw.org
Introduction (FFTW 3.3.11)fftw.org
Amplitude Estimation and Zero Paddingmathworks.com
Multi-dimensional Transforms (FFTW 3.3.11)fftw.org
Equalization, Convolution, and Cyclic Prefix Additionmathworks.com
More DFTs of Real Data (FFTW 3.3.11)fftw.org