3、快速傅里叶变换(FFT)原理：基2时间抽取算法推导、蝶形运算单元、位反转排序
好，咱们进入FFT的核心部分。说实话，很多同学一听到“快速傅里叶变换”就觉得头大，觉得数学推导太复杂。其实你想想看，FFT说白了就是DFT的一种高效算法，它没有改变变换的本质，只是把计算过程优化了。
我记得我刚入行那会儿，第一次在FPGA上实现FFT，也是对着蝶形图看了半天。后来发现，只要理解了“分而治之”这个思想，一切就豁然开朗了。
3.1 从DFT到FFT：为什么要“快速”？
先回顾一下DFT的公式：
X(k) = Σ x(n) * W_N^(nk), n=0 to N-1, k=0 to N-1其中W_N = e^(-j2π/N)，也就是旋转因子。
直接计算这个公式，复杂度是O(N²)。N=1024时，需要大约100万次复数乘法和加法。这在FPGA上跑，资源消耗巨大，延迟也高。
FFT的核心思想是什么？就是利用旋转因子的周期性和对称性，把大点数的DFT分解成若干个小点数的DFT。这就是“分而治之”。
关键点：FFT将O(N²)的计算复杂度降低到O(N log₂N)。N=1024时，从100万次降到约1万次，效率提升100倍。
3.2 基2时间抽取算法推导
基2时间抽取，英文叫Decimation-in-Time，简称DIT。为什么叫“时间抽取”？因为它是按时间序号n的奇偶性来分解序列的。
推导过程其实不复杂，咱们一步步来。
第一步：奇偶分解
假设N是2的整数次幂，比如N=8。我们把x(n)分成两组：
- 偶数序号：x(0), x(2), x(4), x(6)
- 奇数序号：x(1), x(3), x(5), x(7)
那么DFT公式可以写成：
X(k) = Σ x(2r) * W_N^(2rk) + Σ x(2r+1) * W_N^((2r+1)k)
= Σ x(2r) * (W_N²)^(rk) + W_N^k * Σ x(2r+1) * (W_N²)^(rk)注意这里W_N² = e^(-j4π/N) = e^(-j2π/(N/2)) = W_(N/2)。
所以：
X(k) = A(k) + W_N^k * B(k)其中A(k)和B(k)分别是N/2点的DFT。
第二步：利用周期性
A(k)和B(k)都是以N/2为周期的。所以对于k从0到N/2-1：
X(k) = A(k) + W_N^k * B(k)
X(k + N/2) = A(k) - W_N^k * B(k)为什么会这样？因为W_N^(k+N/2) = -W_N^k。这就是蝶形运算的基础。
我的经验：我在项目中遇到过一个问题，就是旋转因子的计算精度。如果你用定点数实现，W_N^k的量化误差会累积。我建议用CORDIC算法或者查表法来生成旋转因子，精度可控。
3.3 蝶形运算单元
蝶形运算，名字很形象。你看它的结构图，就像一只蝴蝶展开翅膀。
一个基2蝶形运算单元完成以下操作：
输出1 = 输入A + 输入B * W
输出2 = 输入A - 输入B * W其中W是旋转因子。这个运算只需要一次复数乘法和两次复数加法。
在FPGA上实现时，我一般这样设计：
- 输入A和B来自两个不同的存储器地址
- 旋转因子W从ROM中读取
- 复数乘法器用DSP48单元实现
- 加减法用LUT+Carry链实现
注意：我曾经踩过一个坑——蝶形运算的流水线深度没算对。如果你用流水线实现，输入A和B的到达时间必须对齐，否则结果会错位。建议在乘法器前后各加一级寄存器，保证时序收敛。
对于N=8的FFT，需要多少级蝶形运算？答案是log₂8 = 3级。每一级有N/2 = 4个蝶形单元。所以总共需要12个蝶形运算。
| 级数 | 蝶形单元数量 | 旋转因子 |
|---|---|---|
| 第1级 | 4 | W_N^0 |
| 第2级 | 4 | W_N^0, W_N^2 |
| 第3级 | 4 | W_N^0, W_N^1, W_N^2, W_N^3 |
你看，每一级的旋转因子数量在增加，但每个蝶形单元只用一个旋转因子。
3.4 位反转排序
这个知识点，很多初学者容易忽略。但我要说，位反转排序是FFT的“隐形骨架”。
为什么需要位反转？因为时间抽取算法把输入序列按奇偶重新排列了。经过三级分解后，输入数据的顺序变成了“位反转”后的顺序。
举个例子，N=8时：
- 原始索引：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
所以，输入数据要按0, 4, 2, 6, 1, 5, 3, 7的顺序送入蝶形运算网络。
在FPGA上实现位反转，我常用的方法有两种：
- 查表法：预先计算好位反转后的地址映射，存到ROM里。简单直接，适合N固定的场景。
- 硬件计算：用移位寄存器实现。比如对于N=1024，需要10位地址，用10个D触发器做反向移位。
我的建议：如果你用Xilinx的IP核，位反转是自动处理的。但如果你自己写RTL代码，我建议用查表法。虽然多占一点BRAM，但时序好控制，调试也方便。
嗯，这里要注意一点：位反转排序可以在数据输入时做，也可以在FFT计算之前做。我个人习惯在数据写入RAM时直接按位反转地址写入，这样后续的蝶形运算就不用再操心地址问题了。
3.5 小结
基2时间抽取FFT，核心就三件事：
- 把大DFT拆成小DFT，利用旋转因子的周期性简化计算
- 用蝶形运算单元实现加减法和乘法
- 用位反转排序把输入数据重新排列
你想想看，这三件事串起来，就是一套完整的FFT计算流程。下一章我会讲如何在FPGA上具体实现这些模块，包括流水线设计、资源优化、以及如何避免常见的时序问题。
说实话，FFT在FPGA上的实现，难点不在于算法本身，而在于如何把算法映射到硬件上，同时兼顾速度、面积和精度。这个咱们后面慢慢聊。