快速傅里叶变换(FFT)

快速傅里叶变换(Fast Fourier Transform,简称 FFT)是一类用于快速计算离散傅里叶变换(DFT)及其逆变换的算法。它将长度为 n 的序列的变换复杂度从直接计算的 O(n²) 降低到 O(n log n),使大规模频谱分析在工程上成为可能。

概述

离散傅里叶变换把时域信号分解为不同频率的正弦分量,是信号处理的核心工具,但直接按定义计算需要 n² 次复数乘法,序列稍长便难以承受。1965 年,美国数学家詹姆斯·库利(James Cooley)与约翰·图基(John Tukey)发表了著名的分治算法,即库利-图基算法;后来人们发现高斯早在十九世纪初的手稿中已有类似思想。FFT 的出现直接推动了数字信号处理学科的形成。

核心原理

库利-图基算法利用了单位复根的对称性与周期性,采用分治策略:

• 将长度为 n 的序列按下标奇偶拆成两个长度为 n/2 的子序列,分别递归求变换。
• 利用旋转因子把两个子结果按蝶形运算合并,得到整体的变换结果。
• 递归深度为 log n,每层合并代价为 O(n),总复杂度 O(n log n)。

常见实现还包括适合任意合数长度的混合基算法、针对素数长度的 Rader 与 Bluestein 算法,以及避免递归开销的迭代位逆序实现。工程中广泛使用的 FFTW 库能针对硬件自动选择最优方案。

应用场景

FFT 的应用几乎遍及所有涉及频域的领域:音频与图像的频谱分析和滤波、通信系统中的正交频分复用(OFDM)、雷达与医学成像、卷积的快速计算等。在算法竞赛与计算机代数中,FFT 还被用来做多项式乘法与大整数乘法,把逐位相乘的 O(n²) 降为 O(n log n)。

常见问题

问:FFT 与 DFT 是什么关系？答:DFT 是数学定义的变换本身,FFT 只是计算这一变换的快速算法,二者结果完全相同,区别仅在计算效率。

问:FFT 要求序列长度必须是 2 的幂吗？答:最经典的基 2 库利-图基算法要求长度为 2 的幂,实践中常用补零凑齐;但混合基、Bluestein 等算法可以处理任意长度。

问:为什么多项式乘法可以用 FFT 加速？答:多项式乘法对应系数序列的卷积,而卷积在频域中变成逐点相乘,因此先做 FFT、逐点相乘、再做逆变换即可。