2、数学基础回顾：离散傅里叶变换（DFT）与快速傅里叶变换（FFT）原理
好，咱们进入正题。这一章是数学基础，但我保证不会让你睡着。
DFT 和 FFT，说白了就是「把信号从时域搬到频域」的工具。你想想看，我们平时看到的波形图，横轴是时间，纵轴是幅度。但很多时候，藏在波形里的信息，在频域里才看得清楚。
我个人习惯，做信号处理之前，先问自己一个问题：我到底想知道什么？ 如果答案是「某个频率成分有多强」，那 DFT 就是你的菜。
2.1 从连续到离散：为什么需要 DFT？
傅里叶变换的原始版本是连续的，公式长这样：
X(f) = ∫ x(t) · e^(-j2πft) dt但计算机不认识连续信号。它只认离散的点。所以就有了 DFT——离散傅里叶变换。
DFT 的公式：
X[k] = Σ_{n=0}^{N-1} x[n] · e^(-j2πkn/N)这里，x[n] 是时域采样点，X[k] 是频域结果。N 是采样点数。
核心理解： DFT 就是把 N 个时域点，通过 N 个不同频率的复指数相乘再求和，得到 N 个频域点。
嗯，这里要注意：DFT 的结果是对称的。前一半是正频率，后一半是负频率。实际应用中，我们通常只看前一半。
2.2 计算复杂度：DFT 的痛点
直接算 DFT，复杂度是 O(N²)。什么意思？
假设 N=1024，你需要做大约 100 万次复数乘法和加法。这在 1960 年代，简直是噩梦。
我记得有一次，我在一个嵌入式项目里用 DFT 做频谱分析。采样点才 256 个，单片机算得直冒烟。那时候我就想，要是没有 FFT，这活儿真没法干。
| N（采样点数） | DFT 计算量（约） | FFT 计算量（约） |
|---|---|---|
| 64 | 4,096 | 384 |
| 256 | 65,536 | 2,048 |
| 1024 | 1,048,576 | 10,240 |
| 4096 | 16,777,216 | 49,152 |
看到差距了吧？N 越大，FFT 的优势越明显。
2.3 FFT：巧妙的「分而治之」
FFT 的全称是「快速傅里叶变换」。它不是一种新的变换，而是 DFT 的一种高效算法。
最经典的版本是 Cooley-Tukey 算法。它的核心思想就四个字：分而治之。
具体怎么做？
- 把 N 点的 DFT 拆成两个 N/2 点的 DFT。
- 再拆成四个 N/4 点的 DFT。
- 一直拆到只剩下 2 点 DFT。
为什么会这么快？因为每次拆分，计算量都减半。最终复杂度从 O(N²) 降到了 O(N log₂N)。
我的经验： 实际写代码时，FFT 要求 N 是 2 的幂次方。比如 256、512、1024。如果不是，可以补零（zero-padding）到最近的 2 的幂。
2.4 蝶形运算：FFT 的基本单元
FFT 的运算结构，画出来像蝴蝶翅膀，所以叫「蝶形运算」。
一个 2 点蝶形运算的公式：
X[0] = x[0] + x[1]
X[1] = x[0] - x[1]就这么简单。但组合起来，就能算出整个频谱。
我曾经在调试一个雷达信号处理系统时，发现 FFT 结果总是不对。查了半天，原来是蝶形运算里的旋转因子（twiddle factor）算错了。那个旋转因子是 W_N^k = e^(-j2πk/N)，索引一错，全盘皆输。
避坑指南： 我曾经因为旋转因子的索引从 0 开始还是从 1 开始搞混，浪费了整整一个下午。建议你写代码时，先把旋转因子表算好，存成数组，别在循环里实时算。
2.5 从 FFT 到 CNN：为什么我们要学这个？
你可能会问：「我是做深度学习的，学 FFT 干嘛？」
好问题。其实，FFT 和 CNN 有很深的联系。
- 卷积定理： 时域卷积等于频域相乘。用 FFT 做卷积，速度可以比直接卷积快很多。
- 频谱特征： 很多 CNN 模型（比如语音识别、振动分析）会先用 FFT 提取频谱特征，再送进网络。
- 模型加速： 有些研究把 FFT 嵌入到 CNN 的卷积层里，减少计算量。
说白了，FFT 是连接「传统信号处理」和「深度学习」的一座桥。你掌握了它，就能在两者之间自由切换。
2.6 一个简单的 FFT 实现（Python）
下面是一个最简化的 FFT 实现，帮你理解核心逻辑：
import numpy as np
def fft(x):
N = len(x)
if N <= 1:
return x
even = fft(x[0::2])
odd = fft(x[1::2])
T = [np.exp(-2j * np.pi * k / N) * odd[k] for k in range(N // 2)]
return [even[k] + T[k] for k in range(N // 2)] + \
[even[k] - T[k] for k in range(N // 2)]
# 测试
x = np.array([0, 1, 0, 0, 0, 0, 0, 0])
print(fft(x))这段代码只有十几行，但包含了 FFT 的核心：递归拆分 + 蝶形合并。
建议： 实际项目中别自己写 FFT，直接用 numpy.fft 或 scipy.fft。它们经过高度优化，比手写的快得多。
2.7 本章小结
来，咱们捋一捋：
- DFT 是把离散信号从时域变到频域的工具。
- 直接算 DFT 太慢，复杂度 O(N²)。
- FFT 用分治策略，把复杂度降到 O(N log₂N)。
- 蝶形运算是 FFT 的基本单元，旋转因子是关键。
- FFT 在 CNN 里可以用来加速卷积、提取频谱特征。
下一章，我们会把 FFT 和卷积神经网络真正结合起来。到时候你会发现，原来这两个东西可以配合得这么默契。
嗯，今天就到这儿。记得动手跑一下上面的代码，感受一下 FFT 的魔力。