🔢 第08课：格雷码指针

一、格雷码的数学性质

格雷码（Gray Code / Reflected Binary Code）是以Frank Gray命名的编码方式。在异步FIFO中使用的格雷码具有特殊性质：

1.1 反射构造法

二、二进制与格雷码的互转

2.1 二进制→格雷码

最简公式：gray = bin XOR (bin >> 1)

原理：格雷码的第i位 = 二进制的第i位 XOR 第i+1位。这是"差分编码"——每个格雷码位编码了二进制相邻位的差异。

// bin_to_gray.v
// 二进制转格雷码 — 组合逻辑，单周期完成
module bin_to_gray #(
    parameter WIDTH = 5
)(
    input  wire [WIDTH-1:0] bin,
    output wire [WIDTH-1:0] gray
);

    assign gray = bin ^ (bin >> 1);

endmodule

2.2 格雷码→二进制

这是逆变换，需要从最高位开始逐位恢复：

bin[MSB] = gray[MSB]

bin[i] = gray[i] XOR bin[i+1]

// gray_to_bin.v
// 格雷码转二进制 — 逐位异或恢复
module gray_to_bin #(
    parameter WIDTH = 5
)(
    input  wire [WIDTH-1:0] gray,
    output wire [WIDTH-1:0] bin
);

    assign bin[WIDTH-1] = gray[WIDTH-1];

    genvar i;
    generate
        for (i = WIDTH-2; i >= 0; i = i - 1) begin : gen_g2b
            assign bin[i] = gray[i] ^ bin[i+1];
        end
    endgenerate

endmodule

2.3 格雷码递增器

在异步FIFO中，指针需要递增。最直接的方法是：格雷码→二进制→加1→格雷码。但也可以直接在格雷码空间递增：

// gray_counter.v
// 格雷码计数器
// 方法：格雷码→二进制→加1→格雷码
module gray_counter #(
    parameter WIDTH = 5
)(
    input  wire             clk,
    input  wire             rst_n,
    input  wire             inc,     // 递增使能
    output wire [WIDTH-1:0] gray_out,
    output wire [WIDTH-1:0] bin_out
);

    reg [WIDTH-1:0] bin_cnt;

    always @(posedge clk or negedge rst_n) begin
        if (!rst_n)
            bin_cnt <= {WIDTH{1'b0}};
        else if (inc)
            bin_cnt <= bin_cnt + 1'b1;
    end

    assign bin_out  = bin_cnt;
    assign gray_out = bin_cnt ^ (bin_cnt >> 1);

endmodule

三、格雷码满空判断的严格推导

这是异步FIFO设计中最需要严谨推导的部分。

四、格雷码满空判断的Verilog实现

// gray_fifo_flags.v
// 基于格雷码指针的异步FIFO满空标志生成
module gray_fifo_flags #(
    parameter ADDR_WIDTH = 4   // 指针宽度 = ADDR_WIDTH + 1
)(
    // 写域
    input  wire [ADDR_WIDTH:0] wr_ptr_gray,
    input  wire [ADDR_WIDTH:0] rd_ptr_gray_sync,  // 同步到写域的读指针
    output wire                full,
    // 读域
    input  wire [ADDR_WIDTH:0] rd_ptr_gray,
    input  wire [ADDR_WIDTH:0] wr_ptr_gray_sync,  // 同步到读域的写指针
    output wire                empty
);

    // ========== 空判断 ==========
    // 格雷码直接比较
    assign empty = (wr_ptr_gray_sync == rd_ptr_gray);

    // ========== 满判断 ==========
    // 格雷码：最高2位取反，其余位相同
    wire [ADDR_WIDTH:0] full_cmp;
    assign full_cmp = {~rd_ptr_gray_sync[ADDR_WIDTH:ADDR_WIDTH-1],
                       rd_ptr_gray_sync[ADDR_WIDTH-2:0]};
    assign full = (wr_ptr_gray == full_cmp);

endmodule

五、格雷码采样的一致性保证

格雷码的关键优势：即使采样窗口内指针正在变化，最多只有1位不确定。那么这1位不确定会导致什么？

六、格雷码的特殊情况：溢出

当指针从2^N - 1递增到0时（溢出回绕），格雷码的变化是否符合单位距？

// 验证格雷码的循环性
// 5位格雷码（指针宽度5，深度16）
// 当二进制从 10000 (16) → 00000 (0) 时：
//   格雷码：11000 → 00000
//   变化了3位！不是单位距！

// 但在异步FIFO中，指针宽度是 ADDR_WIDTH+1
// 深度2^ADDR_WIDTH = 2^4 = 16
// 指针从0到31循环（5位），不会只走0-15
// 额外位的存在使得指针绕一圈后二进制从16变32

// 实际上：指针在0-31之间循环
// 5位格雷码：0→1→3→2→6→7→5→4→12→13→15→14→10→11→9→8→24→...
// 每步都只变1位，包括 31→0（11110→00000，也只变1位！）
// 因为5位格雷码的首尾也是单位距

七、格雷码指针的仿真验证

// tb_gray_counter.v
// 格雷码计数器和满空判断验证
\`timescale 1ns/1ps

module tb_gray_counter;

    reg         clk, rst_n, inc;
    wire [4:0]  gray_out, bin_out;

    gray_counter #(.WIDTH(5)) uut (
        .clk(clk), .rst_n(rst_n), .inc(inc),
        .gray_out(gray_out), .bin_out(bin_out)
    );

    reg [4:0] prev_gray;
    integer   errors;

    initial begin
        $dumpfile("gray_counter.vcd");
        $dumpvars(0, tb_gray_counter);

        clk = 0; rst_n = 0; inc = 0;
        errors = 0;
        #20 rst_n = 1;
        #10;

        // 测试1: 连续递增32次，验证格雷码单位距
        $display("--- Test 1: Unit distance check ---");
        inc = 1;
        prev_gray = 0;
        repeat(32) begin
            @(posedge clk);
            #1;  // 等待输出稳定
            if ($countbits(gray_out ^ prev_gray, '1) != 1) begin
                $display("ERROR: Non-unit distance! prev=%b curr=%b diff=%b",
                         prev_gray, gray_out, gray_out ^ prev_gray);
                errors = errors + 1;
            end
            prev_gray = gray_out;
        end

        // 测试2: 验证环绕（31→0）
        $display("--- Test 2: Wrap-around ---");
        if ($countbits(gray_out ^ 5'b00000, '1) != 1) begin
            $display("ERROR: Wrap-around not unit distance!");
            errors = errors + 1;
        end else
            $display("Wrap-around OK: %b -> %b", prev_gray, 5'b00000);

        // 测试3: 验证bin↔gray转换一致性
        $display("--- Test 3: Round-trip consistency ---");
        inc = 0;
        repeat(32) begin
            @(posedge clk);
            inc = 1;
            @(posedge clk);
            inc = 0;
            // 验证: bin_to_gray(bin) == gray
            wire [4:0] expected_gray = bin_out ^ (bin_out >> 1);
            if (gray_out !== expected_gray) begin
                $display("ERROR: gray mismatch at bin=%b", bin_out);
                errors = errors + 1;
            end
        end

        $display("=== Gray Counter Test: %0d errors ===", errors);
        $finish;
    end

    always #5 clk = ~clk;

endmodule

八、非2幂深度的格雷码变体

如果FIFO深度不是2的幂怎么办？有几种方案：

九、格雷码的硬件优化

在实际硬件中，格雷码指针的处理可以进一步优化：

9.1 避免格雷码→二进制的转换

满空判断中，空条件可以直接比较格雷码，无需转换。但可编程满/空需要计算元素个数，必须转回二进制。为了减少转换逻辑的延迟，可以：

// gray_diff_counter.v
// 格雷码差值计算器 — 用于可编程满空标志
// 将两侧格雷码分别转二进制后相减
module gray_diff_counter #(
    parameter WIDTH = 5   // 格雷码指针宽度
)(
    input  wire [WIDTH-1:0] wr_gray,
    input  wire [WIDTH-1:0] rd_gray_sync,
    output wire [WIDTH-1:0] count
);

    // 格雷码→二进制
    wire [WIDTH-1:0] wr_bin, rd_bin_sync;

    assign wr_bin[WIDTH-1] = wr_gray[WIDTH-1];
    assign rd_bin_sync[WIDTH-1] = rd_gray_sync[WIDTH-1];

    genvar i;
    generate
        for (i = WIDTH-2; i >= 0; i = i - 1) begin : gen_g2b
            assign wr_bin[i]      = wr_gray[i]      ^ wr_bin[i+1];
            assign rd_bin_sync[i] = rd_gray_sync[i] ^ rd_bin_sync[i+1];
        end
    endgenerate

    // 元素个数 = 写指针 - 读指针
    assign count = wr_bin - rd_bin_sync;

endmodule

9.2 格雷码比较器的直接实现

满条件可以不经过二进制转换，直接在格雷码空间比较：

// gray_full_detector.v
// 直接格雷码满检测器
// 无需二进制转换，纯组合逻辑
module gray_full_detector #(
    parameter WIDTH = 5
)(
    input  wire [WIDTH-1:0] wr_gray,
    input  wire [WIDTH-1:0] rd_gray_sync,
    output wire             full
);

    // 满条件：wr_gray最高2位取反 == rd_gray_sync最高2位
    //         wr_gray其余位 == rd_gray_sync其余位
    assign full = (wr_gray[WIDTH-1] != rd_gray_sync[WIDTH-1]) &&
                  (wr_gray[WIDTH-2] != rd_gray_sync[WIDTH-2]) &&
                  (wr_gray[WIDTH-3:0] == rd_gray_sync[WIDTH-3:0]);

endmodule

9.3 面积优化：指针宽度选择

十、关键概念总结