快速傅里叶变换

算法词条：快速傅里叶变换

英文名称	Fast Fourier Transform (FFT)
核心定义	离散傅里叶变换（DFT）的高效计算算法，将计算复杂度从 O(N²) 降至 O(N log N)
核心思想	分治法（Divide and Conquer），利用旋转因子的周期性与对称性大幅削减冗余运算
核心单元	蝶形运算（Butterfly Operation）、码位倒置（Bit-Reversal）、同址计算
根本目标	实现信号时域与频域之间的实时转换，支撑现代通信、多媒体与科学计算的底层算力

1 概述

快速傅里叶变换（Fast Fourier Transform，简称 FFT）并不是一种新的数学变换，而是离散傅里叶变换（Discrete Fourier Transform, DFT）的一种高效计算策略。DFT 是计算机处理离散信号频谱分析的数学基石，但其直接计算的运算量极其庞大。

FFT 通过巧妙利用 DFT 核函数的数学特性，将长序列的 DFT 递归分解为短序列的 DFT，从而实现了计算效率的指数级跃升。例如，对于 N=1024 点的变换，直接 DFT 需要约 100 万次复数乘法，而 FFT 仅需约 1 万次，运算速度提升了上百倍。正是 FFT 的诞生，使得 MP3 音频压缩、JPEG 图像处理、4G/5G 通信（OFDM 技术）以及 MRI 医学成像等现代技术得以实时实现。

2 历史溯源与时代背景

2.1 高斯的早期手稿

早在 1805 年，德国数学家高斯（Carl Friedrich Gauss）在研究小行星轨道时，就已经构思出了类似 FFT 的快速算法，将计算量从 O(N²) 降到了 O(N log N)。但高斯从未公开发表这一成果，手稿在其去世后才被发现，被尘封了近 160 年。

2.2 库利-图基算法与冷战背景

现代 FFT 的广泛应用归功于 1965 年詹姆斯·库利（James W. Cooley）与约翰·图基（John W. Tukey）发表的六页论文。

• 时代背景：冷战高峰期，美国为了监测苏联的地下核试验，需要通过全球地震台网实时分析地震波形，以区分自然地震与核爆炸。当时的计算机（如 IBM 7094）计算 DFT 需要数小时，完全无法满足实时决策需求。
• 算法诞生：库利与图基在 IBM 沃森研究中心合作，利用分治思想提出了库利-图基算法（Cooley-Tukey Algorithm），将计算时间缩短了百倍，直接推动了数字信号处理学科的独立与爆发。

3 物理本质与核心原理

FFT 的核心在于挖掘 DFT 公式中旋转因子（Twiddle Factor）$W_N=e^{-j2\pi /N}$ 的数学冗余性。

3.1 旋转因子的三大特性

DFT 的直接计算之所以慢，是因为存在大量重复运算。旋转因子具备以下三个关键性质，为优化提供了数学基础：

• 周期性：$W_N^{k+N}=W_N^k$（保证矩阵有重复结构）
• 对称性：$W_N^{k+N/2}=-W_N^k$（一次乘法的结果可用于两个输出，即蝶形共享）
• 可约性（降阶）：$W_N^{2k}=W_{N/2}^k$（支持将长序列递归分解为半长序列）

3.2 分治策略与蝶形运算

以最经典的按时间抽取基-2 FFT（DIT-FFT）为例，其算法流程如下：

1. 奇偶分组：将长度为 N 的输入序列 $x[n]$ 按时间下标的奇偶性，分解为两个长度为 N/2 的子序列。
2. 递归分解：对子序列继续分解，直到分解为 2 点 DFT。
3. 蝶形运算 (Butterfly Operation)：将分解后的结果逐级合并。一个标准的蝶形运算包含一次复数乘法和两次复数加法，其数学表达为：

$\{\begin{array}{c}{X}_{m+1}(p)=X_m(p)+W_N^k\cdot X_m(q)\\ X_{m+1}(q)=X_m(p)-W_N^k\cdot X_m(q)\end{array}$

整个 N 点 FFT 由 ${\log }_{2}N$ 级蝶形运算构成，结构高度规整，极其利于硬件流水线设计。

3.3 码位倒置与同址计算

• 码位倒置 (Bit-Reversal)：在基-2 DIT-FFT 中，为了保证每一级蝶形运算的输入地址匹配，输入序列需要按照二进制索引的“位逆序”进行重排（例如 N=8 时，自然序 1(001) 需与 4(100) 交换）。
• 同址计算 (In-place Computation)：每一级蝶形运算的输出可以直接覆盖输入的存储单元，无需额外的数组缓冲，极大节省了内存空间并提升了缓存命中率。

4 核心算法分类

根据分解逻辑与基数的不同，FFT 衍生出了多种变体以适应不同的工程需求：

分类维度	算法变体	核心特点与适用场景
抽取方式	按时间抽取 (DIT)	输入序列需码位倒置，输出自然有序。结构规整，是通用软件库（如 FFTW）的基础模板。
抽取方式	按频率抽取 (DIF)	输入自然有序，输出需码位倒置。利于流水线化硬件设计，常用于专用集成电路。
分解基数	基-2 / 基-4 算法	要求序列长度 N 为 2 或 4 的整数幂。基-4 算法进一步减少了复数乘法次数，效率比基-2 更高。
混合策略	混合基 / 分裂基	适用于任意长度的序列（如素因子算法），或通过混合不同基数进一步优化运算量。

5 关键技术指标与工程优化

在实际工程应用中，FFT 的性能不仅取决于算法本身，还受以下因素影响：

参数名称	符号/单位	核心定义与工程意义
频谱泄漏	Spectral Leakage	由于信号截断（非周期截断）导致能量扩散到邻近频点。需通过加窗函数（如汉宁窗、海明窗）来平滑信号两端，抑制旁瓣干扰。
频率分辨率	$\Delta f$ (Hz)	能够区分两个相邻频率分量的最小间隔，由采样时长决定（$\Delta f=1/T$）。增加 FFT 点数（补零）只能增加谱线密度，不能提高物理分辨率。
量化误差	Quantization Error	在定点 DSP 或 FPGA 中实现 FFT 时，蝶形运算的舍入噪声会逐级累积，需合理分配字长以防止溢出和精度恶化。

6 典型应用与实战场景

FFT 是现代信息技术的“心脏”，其应用贯穿了从底层硬件到上层应用的每一个角落：

应用领域	典型实例	核心作用与原理
现代通信	4G LTE / 5G NR / Wi-Fi 6	作为正交频分复用（OFDM）技术的核心，利用 FFT/IFFT 将高速串行数据流映射到多个正交子载波上，极大提升了频谱利用率和抗多径衰落能力。
音频与图像	MP3 / JPEG / 语音识别	音频压缩利用 FFT 提取频域特征（如 MFCC）；图像压缩（JPEG）中的离散余弦变换（DCT）本质上是实数 FFT 的变种。
科学仪器	示波器 / 频谱分析仪	实时将采集的时域波形转换为频域谱线，支持瞬态信号捕获、谐波失真分析及故障诊断。
大数计算	密码学 / 大整数乘法	利用“时域卷积等于频域乘积”的性质，将多项式乘法（大整数乘法）的复杂度从 O(N²) 降至 O(N log N)，是高性能密码学运算的基础。

7 核心设计准则与常见误区

1. 补零与分辨率的误区：在进行 FFT 前对信号尾部补零（Zero Padding）可以增加频谱的采样点数，使谱线看起来更光滑，但这不能提高真实的物理频率分辨率。真实的分辨率只取决于信号的有效采样时长。
2. 窗函数的选择：不加窗（即矩形窗）会导致严重的频谱泄漏。选择窗函数是在“主瓣宽度”（频率分辨力）与“旁瓣衰减”（抗干扰能力）之间做权衡。例如，振动分析常用汉宁窗，而雷达信号处理倾向于高旁瓣抑制的布莱克曼窗。
3. 实数 FFT 的优化：如果输入信号是纯实数（如大多数传感器采集的数据），直接套用复数 FFT 会浪费一半的算力。工程中常采用专门的实数 FFT（RFFT）算法，将运算量和存储空间再减半。

8 学科发展与历史溯源

• 1805年：高斯在手稿中首次提出快速算法思想，但未发表。
• 1965年：库利与图基发表论文，FFT 算法正式问世，解决了核试验监测的实时计算瓶颈。
• 20世纪70年代至今：随着超大规模集成电路的发展，FFT 被固化到专用的 DSP 芯片和 FPGA IP 核中。现代数学库（如 Intel MKL、FFTW）能够根据 CPU 缓存结构自动调度最优的 FFT 算法组合。

9 常见物理常数与参考

• DFT 定义式：$X[k]=\sum _{n=0}^{N-1}x[n]\cdot e^{-j2\pi kn/N}$
• 基-2 FFT 运算量：约 $\frac{N}{2}{\log }_{2}N$ 次复数乘法，$N{\log }_{2}N$ 次复数加法。
• 卷积定理：$x[n]*h[n]\leftrightarrow X(k)\cdot H(k)$，即时域卷积可通过频域相乘（两次 FFT + 一次 IFFT）来加速实现。

10 参见

• 离散傅里叶变换 (DFT)
• 数字信号处理 (DSP)
• 正交频分复用 (OFDM)
• 窗函数
• 蝶形运算