2、数字信号处理基础回顾：离散傅里叶变换(DFT)与快速傅里叶变换(FFT)原理
各位同学，咱们今天聊聊DFT和FFT。说实话，这两个东西是数字信号处理的基石，也是我们做FPGA加速卷积网络绕不开的坎儿。我当年刚接触这块时，也觉得公式挺唬人，但后来在项目中用多了，发现其实就那么回事。
2.1 从连续到离散：为什么需要DFT？
你想想看，现实世界中的信号都是连续的，比如声音、电压。但FPGA处理不了连续的东西，它只认0和1，只认离散的采样点。傅里叶变换告诉我们，任何信号都能分解成不同频率的正弦波叠加。但那是针对连续信号的。
DFT就是干这个的——把连续傅里叶变换搬到离散域。说白了，就是给计算机和FPGA吃的傅里叶变换。
DFT的数学定义长这样：
X[k] = Σ(n=0 to N-1) x[n] · e^(-j·2π·k·n/N)其中N是采样点数，x[n]是时域信号，X[k]是频域结果。嗯，这里要注意，k代表的是频率索引，不是实际频率值。实际频率需要换算：f = k · fs / N，fs是采样率。
核心理解：DFT的本质就是做相关性计算。每个X[k]其实是在问：「信号x[n]里面，频率为k的成分有多大？」
2.2 DFT的计算代价——一个让人头疼的问题
直接按公式算DFT，复杂度是O(N²)。什么意思呢？假设你采了1024个点，就要算1024×1024 ≈ 100万次复数乘法和加法。我在项目中遇到过用DSP做实时频谱分析，采样率才10kHz，点数是2048，结果DSP算到冒烟都跟不上。
为什么会这样？因为每个X[k]都要遍历所有N个x[n]做乘累加。N个X[k]就是N²次操作。
| 采样点数N | DFT复数乘法次数 | FFT复数乘法次数 | 加速比 |
|---|---|---|---|
| 64 | 4,096 | 192 | ~21x |
| 256 | 65,536 | 1,024 | ~64x |
| 1024 | 1,048,576 | 5,120 | ~205x |
| 4096 | 16,777,216 | 24,576 | ~682x |
看到没？N越大，FFT的优势越明显。4096点时，FFT比DFT快了近700倍。这就是为什么实际工程中没人直接算DFT。
2.3 FFT的核心思想——分而治之
FFT不是新的变换，它只是DFT的一种快速算法。最经典的是Cooley-Tukey算法，核心思想就四个字：分而治之。
具体怎么分？把N点DFT拆成两个N/2点DFT。一个处理偶数索引，一个处理奇数索引。然后利用旋转因子的对称性和周期性，把结果合并起来。
我习惯用8点FFT来理解这个过程：
原始8点DFT:
X[0..7] = DFT(x[0..7])
拆成两个4点DFT:
偶数部分: E[0..3] = DFT(x[0], x[2], x[4], x[6])
奇数部分: O[0..3] = DFT(x[1], x[3], x[5], x[7])
合并公式:
X[k] = E[k] + W⁸ₖ · O[k] (k = 0,1,2,3)
X[k+4] = E[k] - W⁸ₖ · O[k] (k = 0,1,2,3)
其中W⁸ₖ = e^(-j·2π·k/8) 是旋转因子这个拆分可以递归进行，直到变成2点DFT。2点DFT就简单了，就是加减法。整个计算量从N²降到了N·log₂(N)。
个人经验：我在做FPGA实现时，最喜欢用基-2的FFT结构。因为它的数据流非常规整，每次都是两两配对做蝶形运算。你想想看，这种规则性对硬件设计来说简直是福音——流水线好安排，控制逻辑简单，资源利用率也高。
2.4 蝶形运算——FFT的基本单元
FFT的每次迭代都由蝶形运算组成。一个蝶形运算长这样：
输入: a, b, 旋转因子W
输出:
a' = a + W · b
b' = a - W · b画出来就像蝴蝶的两只翅膀，所以叫蝶形运算。每个蝶形只需要一次复数乘法和两次复数加法。
我曾经踩过一个坑：在FPGA里实现时，以为旋转因子可以实时计算。结果发现e^(-j·2π·k/N)用CORDIC算法算一次要十几个时钟周期，整个FFT的吞吐量直接崩了。后来老老实实改用查找表，把旋转因子提前算好存到ROM里，速度一下就上来了。
避坑指南：旋转因子的精度直接影响FFT结果。我曾经用16位定点数存旋转因子，结果SNR差了将近10dB。建议至少用18位，如果资源允许，24位更好。另外要注意，旋转因子是对称的，只存1/4象限就够了，能省不少BRAM。
2.5 位反转——一个容易被忽略的细节
FFT的输入顺序和输出顺序是不一样的。输入需要按位反转的顺序排列，输出才是自然顺序。比如8点FFT：
自然顺序: 0, 1, 2, 3, 4, 5, 6, 7
二进制: 000, 001, 010, 011, 100, 101, 110, 111
位反转后: 000, 100, 010, 110, 001, 101, 011, 111
实际输入: 0, 4, 2, 6, 1, 5, 3, 7在FPGA里实现位反转很简单，把地址线的顺序反过来接就行。但要注意，如果用的是流水线结构的FFT，位反转可以在数据加载阶段完成，不额外消耗时钟。
2.6 FFT在卷积网络中的应用
好了，说了这么多理论，咱们回到正题——FFT怎么加速卷积？
核心依据是卷积定理：时域卷积等于频域相乘。也就是说：
x[n] * h[n] ↔ X[k] · H[k]用FFT做卷积的步骤：
- 对输入特征图和卷积核分别做FFT，变换到频域
- 在频域做逐点乘法
- 对结果做IFFT，变回时域
对于大尺寸卷积核（比如7×7、5×5），这种方法的计算量远小于直接卷积。我做过对比，在FPGA上用FFT做7×7卷积，比传统方法快了将近5倍。
关键点：FFT加速卷积的前提是卷积核尺寸较大。对于3×3的小卷积核，FFT的额外开销反而可能得不偿失。我在实际项目中一般以5×5为分界线——大于等于5×5用FFT，小于5×5用直接卷积。
嗯，DFT和FFT的基础就讲到这里。下一节咱们会深入FFT的FPGA实现细节，包括流水线结构设计、定点数精度分析、以及如何用FFT IP核做卷积加速。这些东西我在项目里摸爬滚打了好几年，踩过的坑不少，到时候一一跟大家分享。