Python 带你深入浅出 DFT / FFT，就是这么简单！

1. 前言

傅里叶变换，在信号处理领域有着举足轻重的地位，其快速变换 —— FFT，被 IEEE 和 American Institute of Physics 的刊物评选为 20 世纪对科学和工程技术影响最大的十大算法之一 [1]。即使在 AI 兴起的今天，FFT 在图像识别、语音交互等场景发挥着关键作用，助力 AI 应用。

如果你对傅里叶变换一直不得其法，或者苦于无法上手，那么这篇用 Python 介绍傅里叶变换的文章，也许对你有所帮助。

按惯例声明一下：我的解释不一定是对的，还可能存在错误，有时我自己也不知道在说什么。所以仅供参考，欢迎讨论。

2. 傅里叶变换与 DFT 简介

傅里叶变换（Fourier Transform，FT）的核心思想是频率分解，即，信号是由不同频率的正（余）弦波组合而成，信号可以在时域和频域之间来回转换。

由于傅里叶变换是一种连续变换，在数字世界中，离散傅里叶变换（Discrete Fourier Transform，DFT）便成为适用的方式。

DFT 的数学公式非常经典，值得在此引用一下：

其中：

N：时域样本的总数量。
n：当前时域样本的索引，n∈[0, N−1]。
m：当前频域样本的索引，m∈[0, N−1]。
x[n]：当前时域样本。
X[m]：当前频域样本。

我们来“肤浅的”介绍一下物理含义（深入的我不会）。

2.1 正（余）弦波组合

DFT 输出的是一组频率样本的序列，其中每一个频率样本 X[m] 是一个复数，由 m 作为索引。

复数的实部和虚部，对应了时域序列分别与余弦波、正弦波的相关性（Correlation）运算：

相当于是将余弦波、正弦波作为相关性运算的参考信号，参考信号有 N 种频率，而且与采样频率有关：

由于正弦波和余弦波相互正交，可以用复数表示，并且通过欧拉公式可以用复指数 e 表示。

总之，DFT 的输出是一组频率样本的序列，每一个频率样本是复数，复数的实部和虚部分别对应了特定频率正弦波、余弦波相关性运算的结果。

2.2 幅度与相位

因为 DFT 输出的每一个频率样本是复数，其幅度与相位，按如下方式计算：

作为入门级，我们看频谱图的幅度比较多。相位则体现的是正弦波、余弦波之间的超前或滞后关系。

2.3 频率区间（Bin）

DFT 输入的离散信号序列长度为 N 个， DFT 输出的频率数量也是 N 个，所以频率也是离散的。

这 N 个频率将频带从 0（直流）到 Fs（采样频率）均匀划分，每个区间就是 bin，就像直方图里有很多“条状”那样。

要提高频率分辨率，就是减小 bin 的话，需要更长的信号序列，以获得更大的 N 。

2.4 正频率与负频率

根据奈奎斯特采样定理，DFT 中大于 N/2 索引的频率会发生混叠，这部分可以平移至负频率，这样整个频带范围变为 -Fs/2 到 +Fs/2。

对于 DFT 输入是实数信号序列的情况，因频谱前半部分与后半部分具有对称性，我们只需关注前半部分，即正频率。

3. Python 中的实现

3.1 快速傅里叶变换（FFT）

快速傅里叶变换（FFT），是离散傅里叶变换（DFT）实现。它具有复杂的数学理论支撑，利用了各种对称性、周期性、计算机硬件特性设计算法，代码效率比 DFT 要快很多。

下述展示了基于经典公式相关性运算的 DFT ，与 FFT 运算的速度比较：

对于这部分，我们只需要知道 FFT 是 DFT 的实现，而且在很多地方，会常常看到 DFT / FFT 混用，比如 Python 。

3.2 Python 库（scipy.fft）

Python 中 DFT / FFT 的实现来自于 scipy.fft 库的支持，里面有很多函数，在此一览：

在查看文档时，同时还会看到两个类似的库，scipy.fftpack 和 numpy.fft，这两个都是旧版，SciPy 更推荐使用 scipy.fft 。

3.3 Python FFT 函数解析

scipy.fft 库里最重要的函数应该是 fft() 与 fftfreq() 的组合使用。

我们假设定义了一个由 N 个样本的信号序列 normalized_signal，采样率是 SAMPLE_RATE，这样构造 FFT 代码片段如下：

# Number of N samples in normalized_signal
yf = fft(normalized_signal)
xf = fftfreq(N, 1 / SAMPLE_RATE)

plt.plot(xf, np.abs(yf))
plt.show()

其中：

fft() 用于对信号序列进行 DFT / FFT 变换，作为频谱图 Y轴的变量；
fftfreq() 用于计算 fft() 输出的每个离散频率，作为频谱图 X轴的变量；

我们前面说了，DFT 的结果是复数，在绘图的时候，调用了 np.abs() 计算每个频率的幅度。

另外，DFT / FFT 里面有负频率，如果输入信号只有实数，则可以调用 rfft() 与 rfftfreq() 的组合，即实数（real） FFT，它们只展示正频率。但请注意，rfft() 的结果仍然是复数。

4. 代码实例

以下展示两个代码实例，第一个是构建一个正弦信号的组合并进行 FFT ；第二个是构建一个方波并进行 FFT。

代码及运行效果如下图所示，我在右下的交互命令行里还展示了 FFT 的数值，可以看到每个频率样本都是复数。

代码运行环境是 Spyder 6，代码链接见托管地址，可以下载尝试运行。

5. 参考资料

5.1 引用出处

5.2 傅里叶变换扩展阅读

5.3 代码托管

https://gitee.com/gilbertjuly/digital-signal-processing-code/tree/master/02_fft

欢迎关注我的微信公众号“疯狂的运放”，及时收到最新的推文。