快速傅里叶算法FFT
快速傅里叶变换（FFT）是一种用于将信号从时域转换到频域的算法。 它通过对信号进行离散傅里叶变换（DFT）的快速计算，大大提高了计算效率。
傅里叶的核心思想：
任何一个周期函数，都可以表示成一堆不同频率、不同幅度的正弦波（+ 余弦波）的和
FFT 的计算公式及优化实现
FFT 的计算公式，其实是 DFT（离散傅里叶变换） 的优化实现。我们先看 DFT 的公式，再说 FFT 的本质和公式
DFT（离散傅里叶变换）公式
假设你有一个长度为 ( N ) 的离散信号 ( x[n] )，其 DFT 为：
$$ X[k] = \sum_{n=0}^{N-1} x[n] \cdot e^{-j \cdot \frac{2\pi}{N}kn} \quad \text{for } k = 0, 1, 2, ..., N-1 $$
每个部分含义：
- ( x[n] )：原始时域信号第 ( n ) 个样本
- ( X[k] )：第 ( k ) 个频率分量（结果是复数）
- $$ e^{-j \cdot \frac{2\pi}{N}kn}：复指数，对应一个频率为 ( k/N ) 的旋转因子 $$
- ( j )：虚数单位，( j^2 = -1 )
FFT 是怎么优化 DFT 的
思想核心：分治法 + 利用对称性
FFT 并没有改变 DFT 的数学本质，只是优化计算过程 —— 通过把 N 点 DFT 拆成两个 N/2 点的 DFT 来减少重复计算。
FFT 核心变形（Cooley-Tukey）
假设 ( N ) 是 2 的幂，把 DFT 拆成“偶数项”和“奇数项”：
$$ X[k] = \sum{n=0}^{N/2-1} x[2n] \cdot W_N^{2kn} + \sum{n=0}^{N/2-1} x[2n+1] \cdot W_N^{(2n+1)k} $$
记： $$ 旋转因子：W_N = e^{-j \cdot \frac{2\pi}{N}} $$
- 所以公式可以变成：
$$ X[k] = E[k] + W_N^k \cdot O[k] $$ $$ X[k + N/2] = E[k] - W_N^k \cdot O[k] $$
其中：
- ( E[k] )：偶数项的 FFT
- ( O[k] )：奇数项的 FFT
这个过程就是 蝶形运算（Butterfly） 的基础。
FFT 的效率
- DFT 是 ( O(N^2) )
- FFT 是 ( O(N \log_2 N) )
当 N 很大（比如音频中 N=2048、4096）时，FFT 极大提升性能，是实时音频分析的基础。