KNOWECON WIKI

ARTICLE

快速傅里叶变换

快速傅里叶变换 (Fast Fourier Transform) 快速傅里叶变换，英文为 Fast Fourier Transform，通常缩写为 FFT，是一种高效计算离散傅里叶变换 (DFT) 及其逆变换的算法。FFT 将 DFT 的计算复杂度从朴素的 O(N^2) 降至 O(N N) ，使得实时频谱分析和大规模信号处理成为可能。该算法的核心思想由 Co

浏览 0 更新 2025-11-09

快速傅里叶变换 (Fast Fourier Transform)

快速傅里叶变换，英文为 Fast Fourier Transform，通常缩写为 FFT，是一种高效计算离散傅里叶变换 (DFT) 及其逆变换的算法。FFT 将 DFT 的计算复杂度从朴素的 O(N2) O(N^2) 降至 O(Nlog⁡N) O(N \log N) ，使得实时频谱分析和大规模信号处理成为可能。该算法的核心思想由 Cooley 和 Tukey 于 1965 年正式发表，但其数学根源可追溯至高斯在 1805 年的手稿。FFT 被广泛认为是二十世纪最重要的数值算法之一，深刻影响了信号处理、通信工程、图像处理、音频分析和金融时间序列分析等领域。

离散傅里叶变换 (DFT)

离散傅里叶变换将一个长度为 N N 的复数序列 {xn}n=0N−1 \{x_n\}_{n=0}^{N-1} 转换为另一个复数序列 {Xk}k=0N−1 \{X_k\}_{k=0}^{N-1} ，其定义为：

Xk=∑n=0N−1xn⋅e−i2πkn/N,k=0,1,…,N−1X_k = \sum_{n=0}^{N-1} x_n \cdot e^{-i 2\pi k n / N}, \quad k = 0, 1, \ldots, N-1

其中 e−i2πkn/N e^{-i 2\pi k n / N} 称为旋转因子 (twiddle factor)，记作 WNkn W_N^{kn} 。DFT 将信号从时域变换到频域，揭示信号中各频率分量的幅度和相位。逆变换 (IDFT) 的形式为：

xn=1N∑k=0N−1Xk⋅ei2πkn/N,n=0,1,…,N−1x_n = \frac{1}{N} \sum_{k=0}^{N-1} X_k \cdot e^{i 2\pi k n / N}, \quad n = 0, 1, \ldots, N-1

直接按定义计算 DFT 需要对每个 k k 求和 N N 项，总复杂度为 O(N2) O(N^2) 。当 N N 较大（如 106 10^6 ）时，这种计算在实际中不可行，这正是 FFT 要解决的核心问题。

Cooley-Tukey 算法的核心思想

Cooley-Tukey FFT 采用分治法策略，将大小为 N N 的 DFT 递归地分解为两个大小为 N/2 N/2 的 DFT。其前提是 N N 为复合数，最常用的形式是基-2 FFT（要求 N N 为 2 的幂）。

令 N=2M N = 2M ，将原始序列按偶数下标和奇数下标拆分为两个子序列：

  • 偶数项：em=x2m,m=0,1,…,M−1 e_m = x_{2m}, \quad m = 0, 1, \ldots, M-1
  • 奇数项：om=x2m+1,m=0,1,…,M−1 o_m = x_{2m+1}, \quad m = 0, 1, \ldots, M-1

则 DFT 可以重写为：

Xk=∑n=0N−1xnWNkn=∑m=0M−1x2mWN2km+∑m=0M−1x2m+1WNk(2m+1)=∑m=0M−1emWMkm+WNk∑m=0M−1omWMkm=Ek+WNk⋅Ok\begin{aligned} X_k &= \sum_{n=0}^{N-1} x_n W_N^{kn} \\ &= \sum_{m=0}^{M-1} x_{2m} W_N^{2km} + \sum_{m=0}^{M-1} x_{2m+1} W_N^{k(2m+1)} \\ &= \sum_{m=0}^{M-1} e_m W_{M}^{km} + W_N^k \sum_{m=0}^{M-1} o_m W_{M}^{km} \\ &= E_k + W_N^k \cdot O_k \end{aligned}

其中 Ek E_k 和 Ok O_k 分别是偶序列和奇序列的长度为 M M 的 DFT。利用周期性 WNk+M=−WNk W_N^{k+M} = -W_N^k ，可得：

Xk=Ek+WNkOk,Xk+M=Ek−WNkOk,k=0,1,…,M−1X_k = E_k + W_N^k O_k, \quad X_{k+M} = E_k - W_N^k O_k, \quad k = 0, 1, \ldots, M-1

这一对计算称为蝶形运算 (butterfly operation)。递归应用此分解，总共需要 log⁡2N \log_2 N 层，每层 O(N) O(N) 次操作，最终总复杂度为 O(Nlog⁡N) O(N \log N) 。

时间复杂度分析

朴素 DFT 与 FFT 的差距是巨大的。以 N=106 N = 10^6 为例：

  • DFT：约 1012 10^{12} 次复乘，在通用 CPU 上需数小时甚至数天。
  • FFT：约 Nlog⁡2N≈2×107 N \log_2 N \approx 2 \times 10^7 次运算，可在毫秒级完成。

这一加速比（约 5×104 5 \times 10^4 倍）使得实时频谱分析、卷积运算和大规模滤波成为可行。在经济学和金融学中，FFT 被广泛用于谱分析 (spectral analysis)、协整检验中的频域方法、期权定价中的特征函数反演等场景。

位逆序重排与迭代实现

在实际实现中，递归通常被转换为迭代形式以提高效率。迭代 FFT 首先将输入序列进行位逆序排列 (bit-reversal permutation)：将每个下标表示为二进制并反转比特顺序后得到新位置。例如 N=8 N=8 时，下标 1 (二进制 001) 被移至位置 4 (二进制 100)。重排后，从大小 2 的 DFT 开始逐层合并，每层进行蝶形运算，最终得到完整的 DFT 结果。这种原地计算 (in-place) 策略仅需 O(N) O(N) 额外空间，是库实现（如FFTW、NumPy 的 fft 模块）的常见做法。

FFT 的变体与应用

除了基-2 Cooley-Tukey 算法，FFT 还有多种变体：

  1. 混合基 FFT：当 N N 不是 2 的幂时，可分解为多个小素数因子（如 N=2a3b5c N = 2^a 3^b 5^c ），分别应用小尺寸 DFT，由 Winograd 或 Rader 算法处理。
  2. 实数 FFT：当输入为纯实数时，利用共轭对称性 XN−k=Xk∗ X_{N-k} = X_k^* 可将计算量减半。
  3. 短时傅里叶变换 (STFT)：对信号加窗后分段做 FFT，生成频谱图 (spectrogram)，用于分析非平稳信号的时频特性。
  4. 多维 FFT：通过逐维变换将一维 FFT 推广到二维及以上，广泛应用于图像压缩（如JPEG）和卷积神经网络中的快速卷积。

在经济数据分析中，FFT 常用于识别商业周期的频率成分、消除季节性噪声、计算自相关函数的快速估计，以及在高频交易中分析订单流的微观结构特征。理解 FFT 的原理和应用，是掌握现代定量分析工具链的关键一环。