傅里叶变换家族
核心概念
"把信号投影到不同频率的正弦/余弦基底上，求每个基底的权重（系数）"
变换层次（理论→实践）
| 名称 | 输入信号 | 输出 | 计算复杂度 | 实现难度 |
|---|---|---|---|---|
| 连续傅里叶变换 | 连续、非周期 | 连续频谱 | — | 几乎不可能 |
| 傅里叶级数 | 连续（周期）频谱 | 离散频谱 | — | 困难 |
| 离散时间傅里叶变换 | 离散、非周期 | 连续（周期）频谱 | — | 几乎不可能 |
| 离散傅里叶变换 | 离散、有限长 | 离散频谱 | O(N²) | 可算但很慢 |
| 快速傅里叶变换 | 同DFT | 同DFT | O(N log N) | ★ 快速且容易 ★ |
旋转因子 (Twiddle Factor)
WN = e-j2π/N
理解FFT的关键钥匙 - 单位圆上的N次等分点
WNN = 1
周期性：W^N = 1
WNN/2 = -1
对称性：W^(N/2) = -1
WN/2 = WN2
约化性质：W_{N/2} = W²
时域 ↔ 频域
探索不同时域信号在频域中的表现形式
DFT 公式
X[k] = Σn=0N-1 x[n] · e-j2πkn/N
时域信号
频域幅度谱
相位谱
傅里叶级数逼近
观察周期信号如何由谐波叠加构成
傅里叶级数公式
x(t) = a0 + Σn=1∞ (ancos(nω₀t) + bnsin(nω₀t))
信号逼近（绿色=当前，红色=目标）
单个谐波分量
傅里叶系数
FFT 蝶形运算图
可视化 Cooley-Tukey 基-2 FFT 算法
蝶形运算
A' = A + WNk · B
B' = A - WNk · B
位反序排列
信号流图
DFT vs FFT 性能对比
比较计算复杂度：O(N²) vs O(N log N)
理论运算次数
| N | DFT (N²) | FFT (N log₂N) | 加速 |
|---|
执行时间 (毫秒)
运算次数
加速比
实时音频频谱分析
使用 FFT 实时可视化音频频率内容
频谱
时域波形
峰值频率
-- Hz
峰值幅度
-- dB
实际应用领域 (2025)
音频处理
MP3/AAC 压缩、回声消除、变调、音高检测
★★★★★ 核心
无线通信
OFDM（4G/5G/6G/WiFi）、频域均衡
★★★★★ 核心中的核心
图像处理
JPEG 压缩、去噪、锐化、超分辨率
★★★★☆ 重要
医学成像
MRI 重建、CT 算法
★★★★★ 至关重要
雷达/声呐
脉冲压缩、目标检测
★★★★☆ 核心
地震信号处理
层析成像、去噪
★★★★ 非常重要
大整数/多项式乘法
密码学、计算机代数（Schönhage–Strassen 算法）
★★★★☆ 核心
机器学习
FNet、时序模型加速、注意力机制替代方案
★★★→★★★★ 发展中