查看“︁快速傅里叶变换”︁的源代码

{| class="wikitable" style="float:right; width:320px; margin-left:1em;"
|+ style="font-weight:bold; font-size:1.2em;" | 算法词条：快速傅里叶变换
|-
! 英文名称
| 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）<math>W_N = e^{-j2\pi/N}</math> 的数学冗余性。

=== 3.1 旋转因子的三大特性 ===
DFT 的直接计算之所以慢，是因为存在大量重复运算。旋转因子具备以下三个关键性质，为优化提供了数学基础：
* '''周期性'''：<math>W_N^{k+N} = W_N^k</math>（保证矩阵有重复结构）
* '''对称性'''：<math>W_N^{k+N/2} = -W_N^k</math>（一次乘法的结果可用于两个输出，即蝶形共享）
* '''可约性（降阶）'''：<math>W_N^{2k} = W_{N/2}^k</math>（支持将长序列递归分解为半长序列）

=== 3.2 分治策略与蝶形运算 ===
以最经典的'''按时间抽取基-2 FFT'''（DIT-FFT）为例，其算法流程如下：
# '''奇偶分组'''：将长度为 N 的输入序列 <math>x[n]</math> 按时间下标的奇偶性，分解为两个长度为 N/2 的子序列。
# '''递归分解'''：对子序列继续分解，直到分解为 2 点 DFT。
# '''蝶形运算 (Butterfly Operation)'''：将分解后的结果逐级合并。一个标准的蝶形运算包含一次复数乘法和两次复数加法，其数学表达为：
<center>
<math>\begin{cases} 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{cases}</math>
</center>
整个 N 点 FFT 由 <math>\log_2 N</math> 级蝶形运算构成，结构高度规整，极其利于硬件流水线设计。

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

== 4 核心算法分类 ==

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

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

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

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

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

== 6 典型应用与实战场景 ==

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

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

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

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

== 8 学科发展与历史溯源 ==

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

== 9 常见物理常数与参考 ==
* '''DFT 定义式'''：<math>X[k] = \sum_{n=0}^{N-1} x[n] \cdot e^{-j2\pi kn/N}</math>
* '''基-2 FFT 运算量'''：约 <math>\frac{N}{2} \log_2 N</math> 次复数乘法，<math>N \log_2 N</math> 次复数加法。
* '''卷积定理'''：<math>x[n] * h[n] \leftrightarrow X(k) \cdot H(k)</math>，即时域卷积可通过频域相乘（两次 FFT + 一次 IFFT）来加速实现。

== 10 参见 ==
* [[离散傅里叶变换]] (DFT)
* [[数字信号处理]] (DSP)
* [[正交频分复用]] (OFDM)
* [[窗函数]]
* [[蝶形运算]]

[[Category:应用数学]]
[[Category:信号处理]]
[[Category:算法]]
[[Category:电子工程]]