4、FPGA上的FFT实现：流水线结构与基2蝶形运算单元设计

好，咱们接着往下聊。上一章我们把FFT的数学原理和并行架构理了一遍，这一章要动真格的了——在FPGA上把FFT真正跑起来。

说实话，FFT在FPGA上的实现，核心就两个东西：流水线结构和基2蝶形运算单元。这两个搞定了，剩下的都是体力活。

4.1 为什么非要用流水线？

你想想看，一个1024点的FFT，如果串行算，得算多久？每个蝶形运算都要等上一个算完，那延迟简直没法看。

我在项目中遇到过这样一个场景：雷达信号处理，数据是一帧一帧连续来的。如果FFT处理速度跟不上数据输入速度，那整个系统就崩了。说白了，就是实时性要求逼着我们必须用流水线。

流水线的思路其实很简单：把FFT的每一级运算拆开，用独立的硬件单元去处理。数据像流水一样，一级一级往下传。第一级算完的结果，马上交给第二级，同时第一级开始处理下一组数据。

嗯，这里要注意：流水线不是免费的午餐。它用面积换速度，资源消耗会大一些。但现在的FPGA资源越来越丰富，这点代价完全值得。

4.2 基2蝶形运算单元——FFT的原子操作

基2蝶形运算，说白了就是FFT最基本的计算单元。一个蝶形运算干两件事：加法和旋转因子乘法。

数学表达式很简单：

// 蝶形运算公式
// 输入：a, b（复数）
// 输出：A, B（复数）
// W = 旋转因子

A = a + b * W
B = a - b * W

你看，就一个加法、一个减法、一个复数乘法。但别小看它，整个FFT就是靠无数个这样的蝶形运算堆起来的。

我个人习惯把蝶形运算单元设计成一个独立的模块，这样方便复用。下面是我常用的Verilog代码框架：

module butterfly #(
    parameter DATA_WIDTH = 16
)(
    input  wire clk,
    input  wire rst_n,
    input  wire signed [DATA_WIDTH-1:0] a_re, a_im,
    input  wire signed [DATA_WIDTH-1:0] b_re, b_im,
    input  wire signed [DATA_WIDTH-1:0] w_re, w_im,
    output reg  signed [DATA_WIDTH-1:0] A_re, A_im,
    output reg  signed [DATA_WIDTH-1:0] B_re, B_im
);

    // 内部寄存器
    reg signed [DATA_WIDTH-1:0] b_w_re, b_w_im;
    
    // 第一步：计算 b * W
    always @(posedge clk or negedge rst_n) begin
        if (!rst_n) begin
            b_w_re <= 0;
            b_w_im <= 0;
        end else begin
            b_w_re <= b_re * w_re - b_im * w_im;
            b_w_im <= b_re * w_im + b_im * w_re;
        end
    end
    
    // 第二步：计算 A = a + b*W, B = a - b*W
    always @(posedge clk or negedge rst_n) begin
        if (!rst_n) begin
            A_re <= 0; A_im <= 0;
            B_re <= 0; B_im <= 0;
        end else begin
            A_re <= a_re + b_w_re;
            A_im <= a_im + b_w_im;
            B_re <= a_re - b_w_re;
            B_im <= a_im - b_w_im;
        end
    end

endmodule

4.3 流水线结构的具体设计

好了，有了蝶形运算单元，接下来就是怎么把它们串起来。

一个N点基2FFT，需要log2(N)级流水线。每一级包含N/2个蝶形运算单元。比如1024点FFT，就是10级流水线，每级512个蝶形单元。

但这里有个坑：每一级的旋转因子不一样。第一级用W^0，第二级用W^0和W^(N/4)，第三级更复杂。我曾经在这个问题上栽过跟头——旋转因子表没算对，结果仿真出来全是错的。

我建议的做法是：提前把旋转因子算好，存到ROM里。每一级从ROM里读对应的因子。

级数	蝶形单元数量	旋转因子数量	旋转因子值
第1级	N/2	1	W^0
第2级	N/2	2	W^0, W^(N/4)
第3级	N/2	4	W^0, W^(N/8), W^(2N/8), W^(3N/8)
...	...	...	...
第k级	N/2	2^(k-1)	W^(0), W^(N/2^k), ...

你看这个规律：每一级的旋转因子数量翻倍。第1级只有1个，第2级2个，第3级4个……到第10级就是512个。

4.4 数据重排——容易被忽略的细节

流水线FFT还有一个关键点：数据怎么在各级之间传递。

基2FFT要求数据按比特反转顺序输入。但流水线结构里，每一级输出的数据顺序是乱的，需要重新排序才能喂给下一级。

我常用的方法是：用双口RAM做数据缓冲。每一级算完的结果，先写到RAM里，下一级再从RAM里按正确的顺序读出来。

4.5 实战经验总结

最后，我把自己做FFT加速的一些经验列出来，供你参考：

• 位宽选择：输入数据16位，内部运算建议扩展到18位或20位。防止溢出。我一般用18位，刚好适配DSP48的输入位宽。
• 截位策略：每一级运算完，结果要截位。我习惯用舍入+饱和的方式，比直接截断精度高不少。
• 流水线深度：每一级之间加1-2个流水线寄存器，可以提升最高频率。代价是增加几个时钟周期的延迟，但换来的时序收敛很值得。
• 旋转因子精度：旋转因子用16位定点数表示，量化误差控制在0.001%以内。这个精度对于大多数应用足够了。

嗯，说到这儿，FFT的流水线实现基本就这些了。下一章我们聊聊怎么把这些模块整合成一个完整的FFT加速器，以及怎么和外部接口对接。

你想想看，掌握了这些，一个高性能的FFT加速器就离你不远了。