3、FFT算法详解：基2时间抽取(DIT)与频率抽取(DIF)算法
好，咱们今天来啃一块硬骨头——FFT算法。说实话，我刚入行那会儿，看到FFT的蝶形图就头疼。但后来在雷达信号处理项目中，发现这玩意儿是绕不开的坎。你想想看，一个1024点的DFT，直接算要一百多万次复数乘法，而FFT只要五千次左右。这差距，简直就是自行车和火箭的区别。
FFT的核心思想其实就一句话：分而治之。把一个大DFT拆成若干个小DFT，再组合起来。今天咱们重点讲两种最经典的分解方式：时间抽取（DIT）和频率抽取（DIF）。
3.1 从DFT到FFT：为什么能加速？
先回顾一下DFT公式：
X[k] = Σ x[n] * W_N^(nk), n=0 to N-1其中W_N = e^(-j2π/N)，也就是旋转因子。直接算的话，每个X[k]需要N次复数乘加，总共N²次。N=1024时，就是一百万次操作。这在FPGA上跑实时系统？想都别想。
FFT利用了旋转因子的两个性质：
- 周期性：W_N^(k+N) = W_N^k
- 对称性：W_N^(k+N/2) = -W_N^k
嗯，这里要注意，正是这两个性质让我们能把大DFT拆成小DFT。我在做OFDM基带处理时，就靠这个把处理延迟从毫秒级降到了微秒级。
3.2 基2时间抽取（DIT-FFT）
DIT算法，说白了就是按时间序号n的奇偶性来拆分。我个人习惯叫它「奇偶分家法」。
假设N=8，我们把输入序列x[0]~x[7]分成两组：
- 偶数点：x[0], x[2], x[4], x[6]
- 奇数点：x[1], x[3], x[5], x[7]
然后分别做4点DFT，再通过旋转因子组合起来。这个过程可以递归下去，直到变成2点DFT。
核心公式长这样：
X[k] = G[k] + W_N^k * H[k]
X[k+N/2] = G[k] - W_N^k * H[k]其中G[k]是偶数点的N/2点DFT，H[k]是奇数点的N/2点DFT。
关键点：DIT的输入是乱序的（bit-reversed order），输出是自然顺序。在FPGA实现时，我建议先做bit-reverse重排，再送进蝶形运算单元。
我曾经在一个项目中，因为没处理好输入数据的位反转，结果仿真波形全乱了。排查了两天才发现是地址映射搞反了。嗯，从那以后我写地址生成逻辑时都会画个真值表。
3.3 基2频率抽取（DIF-FFT）
DIF算法正好反过来——它按输出频率序号k的奇偶性来拆分。说白了，就是把输出频谱分成两半来算。
还是以N=8为例，DIF先把输入序列分成前后两半：
- 前半：x[0]~x[3]
- 后半：x[4]~x[7]
然后先做加减运算和旋转因子乘法，再分别做4点DFT。公式如下：
a[n] = x[n] + x[n+N/2]
b[n] = (x[n] - x[n+N/2]) * W_N^n其中a[n]用来算偶数频率点，b[n]用来算奇数频率点。
个人经验：DIF的输入是自然顺序，输出是bit-reversed顺序。如果你在FPGA里用流水线结构，DIF往往更容易实现，因为输入数据可以顺序读取，不需要预先重排。
3.4 DIT vs DIF：到底选哪个？
很多初学者会纠结这个问题。我直接说结论：两者计算量完全一样，区别在于数据流的方向。
| 对比项 | DIT（时间抽取） | DIF（频率抽取） |
|---|---|---|
| 输入顺序 | bit-reverse（乱序） | 自然顺序 |
| 输出顺序 | 自然顺序 | bit-reverse（乱序） |
| 旋转因子位置 | 在蝶形运算之前乘 | 在蝶形运算之后乘 |
| FPGA实现难度 | 需要输入重排逻辑 | 需要输出重排逻辑 |
| 常用场景 | 软件实现、定点化 | 流水线结构、硬件实现 |
你想想看，如果你的数据源是ADC连续采样的，那自然顺序输入就很方便。这时候用DIF，数据进来直接处理，最后在输出端做一次bit-reverse就行。反过来，如果你要做的是频域滤波，输入数据已经存在RAM里了，那用DIT可能更顺手。
避坑指南：我曾经在实现一个1024点DIF-FFT时，忽略了旋转因子的索引计算。DIF的旋转因子索引是n（时域索引），而DIT的是k（频域索引）。搞混了的话，算出来的频谱会完全不对。建议写代码前先画个4点的蝶形图，把每个节点的系数标清楚。
3.5 蝶形运算单元：FFT的基本积木
不管是DIT还是DIF，最底层的运算单元都是蝶形运算。一个基2蝶形包含：
- 1次复数加法
- 1次复数减法
- 1次复数乘法（乘旋转因子）
在FPGA里，我通常这样实现：
// 伪代码：DIT蝶形运算
// 输入：a, b, W（旋转因子）
// 输出：A, B
temp = b * W; // 复数乘法
A = a + temp; // 加法
B = a - temp; // 减法注意这里的乘法器资源消耗。一个复数乘法需要4个实数乘法和2个实数加法。对于N点FFT，总共需要(N/2)*log2(N)个蝶形。N=1024时，就是5120个蝶形，每个蝶形4个实数乘法——总共20480次实数乘法。这个数字在FPGA资源规划时一定要心里有数。
3.6 旋转因子的生成与存储
旋转因子W_N^k = cos(2πk/N) - j*sin(2πk/N)。在FPGA里，我建议提前算好存到ROM里，而不是实时计算。原因很简单：实时算三角函数太费资源了。
存储策略有两种：
- 全表存储：存N/2个旋转因子（利用对称性可减半）
- 增量计算：只存一个初始值，用CORDIC算法迭代生成
我个人偏好全表存储。虽然多占点BRAM，但胜在速度快、逻辑简单。在Xilinx的7系列FPGA上，一个1024点的旋转因子表大概占2-3个Block RAM，完全能接受。
小技巧：旋转因子的精度很关键。我一般用16位量化，其中1位符号位、1位整数位、14位小数位。这样既能保证SNR在80dB以上，又不会浪费太多资源。如果你对精度要求更高，可以考虑用18x18的DSP48硬核做乘法。
3.7 实战要点总结
好了，讲了这么多，我帮你捋一下重点：
- 理解分治思想：FFT的本质就是递归拆分，把大问题变小
- 分清DIT和DIF：一个按输入奇偶拆，一个按输出奇偶拆，数据流方向不同
- 蝶形运算是核心：加、减、乘旋转因子，三步走
- 旋转因子提前存：别在FPGA里实时算三角函数
- 注意位反转：不管是输入还是输出，总有一端是乱序的
下一章咱们会把这些理论落实到具体的FPGA架构设计上，包括流水线结构、定点化处理、以及如何用Verilog写出高效的FFT模块。到时候我会拿一个实际项目中的例子来拆解，保证让你看得过瘾。