FFT——快速傅里叶变换通俗解释

FFT，也就是快速傅里叶变换，是一种快速计算离散傅里叶变换（DFT）的方法。如果你有一组等间隔采样点，DFT 会告诉你这些样本中包含了多少不同的离散频率模式。

关键点在于，FFT 并不会改变结果。它得到的 DFT 数值与直接套公式计算完全相同，只是中间少做了大量重复工作。

一句话理解 FFT

FFT 是一种更快的算法，用来计算 DFT 所定义的那组频域数值。

假设你有样本 $x_0, x_1, \dots, x_{N-1}$ 。DFT 会生成数值 $X_0, X_1, \dots, X_{N-1}$ ，定义为

X_k = \sum_{n=0}^{N-1} x_n e^{-i 2 \pi kn / N}

每个 $X_k$ 都表示数据与某一种离散频率模式匹配得有多强。

如果这些样本是以采样率 $f_s$ 等间隔取得的，那么相邻频率 bin 之间的间隔是

\frac{f_s}{N}

这个条件很重要。如果不知道采样率，你仍然可以得到 DFT 的各个 bin，但无法把它们标成赫兹这样的实际物理频率。

FFT 是一类高效计算 DFT 的算法。它最核心的技巧，是复用复指数因子中的结构，而不是从头反复计算几乎相同的求和。

最容易直观理解的版本是基 2 FFT。它在 $N$ 是 $2$ 的幂时最自然，会先把一个长度为 $N$ 的变换拆成两个长度为 $N/2$ 的变换，再把结果合并起来。

对于直接计算 DFT，运算量大致按 $N^2$ 增长。对于常见的 FFT 方法，运算量则降到大约 $N \log N$ 。

这就是 FFT 在实际中如此重要的原因。输入规模小时，两种方法都可能还算能接受；但输入一大，FFT 就会快得非常明显。

FFT 不会直接把每个样本都与每个频率模式逐一比较，而是先把问题拆成更小的变换，再用相位因子把结果重新组合。

一种标准拆分方式是：

这就是分治法在频率分析中的应用。

考虑下面这个 4 点信号

x = [1, 0, 1, 0]

这个模式在 $1$ 和 $0$ 之间交替出现，所以我们预期它会表现出一定的频率结构，而不是得到一个完全平坦的结果。

按偶数索引和奇数索引拆分：

x_{\text{even}} = [1, 1], \qquad x_{\text{odd}} = [0, 0]

偶数部分的 2 点 DFT 是

E = [2, 0]

奇数部分的 2 点 DFT 是

O = [0, 0]

对于 4 点 FFT，合并步骤为

X_k = E_k + W_4^k O_k, \qquad X_{k+2} = E_k - W_4^k O_k, \qquad k = 0,1

其中

W_4 = e^{-i 2 \pi / 4}

因为 $O_k = 0$ ，所以合并过程特别简单：

X = [2, 0, 2, 0]

现在来解释这个结果。

$X_0 = 2$ 是零频项，因此它反映了样本的非零平均值。 $X_2$ 的非零值则刻画了这个 4 点例子中模式的交替部分。如果你先减去均值，那么 $X_0$ 项就会消失，交替成分会更清楚地显现出来。

这个例子虽然很小，但思路是可以推广的：先求更小的变换，再把它们合并，而不是每次都把整个求和重新算一遍。

并不是。FFT 只是更快地计算 DFT 的一种方法。

只有在已知采样间隔时，bin 的位置才能对应到实际物理频率。如果采样率是 $f_s$ ，那么对于等间隔采样，bin 间隔就是 $f_s/N$ 。

零填充会让频谱看起来更平滑，因为它更细地采样了底层变换，但它并不会增加新的实测数据。

去均值、加窗以及谨慎选择采样方式都可能非常重要。如果忽略这些条件，FFT 输出对给定样本来说在数学上仍然是正确的，但在解释时可能会产生误导。

凡是你需要从采样数据中快速获得频域信息的地方，都会用到 FFT。常见例子包括频谱分析、滤波、图像处理、振动分析、微分方程的数值求解，以及快速多项式或卷积计算。

原因很实际：很多运算在从样本域转到频域之后，会变得更容易或更高效。

取一段正弦波在一个完整周期内的 $8$ 个等间隔采样点，用计算器或脚本算出它的 DFT。然后给它加上一个常数偏移，再比较新的输出。观察 $X_0$ 变大，是理解 FFT 分离了什么内容的一种简单方式。

上传你的问题，几秒钟内获得经过验证的分步解答。