Gray Code Pointers

The previous article built a FIFO with one clock. Before we can build one with two clocks, the pointers need a different encoding, and this article is about why.

In Module 3 we built a two-flop synchronizer for a single bit. It works because a single bit has only one thing that can go wrong at the synchronizing flop: it may go metastable and then settle to either its old or its new value, and either outcome is a valid bit. Try to synchronize a 4-bit binary counter the same way, four independent two-flop synchronizers, and a new failure mode appears that a single bit can never have.

The multi-bit crossing problem

Say a binary counter goes from 0111 to 1000. Every bit flips at once. If you sample that value with an unrelated clock, there is no guarantee all four bits are captured at the same instant relative to the transition. Some may be sampled just before it and some just after:

$$0111 \rightarrow 1000$$

A sampling edge landing in the middle of the transition can capture 1100, or 0000, or any other mix of old and new bits, a value the counter never held, invented by the different bits settling at slightly different times. This is a different problem from single-bit metastability, and a two-flop synchronizer on each bit does nothing about it. Each synchronizer only guarantees that its own bit resolves to a clean 0 or 1; it says nothing about whether the four bits are consistent with each other.

The fix: never let more than one bit change at once

Gray code is a binary encoding with the one property that matters here: any two adjacent values in the sequence differ in exactly one bit. If only one bit ever changes at a time, a sampling edge catching the transition mid-flight sees either the old value or the new value, cleanly, because there is no second bit that could be caught in a different state.

Check the step from 3 to 4. Binary goes 011 to 100, all three bits flipping, exactly the dangerous case. Gray goes 010 to 110, only the top bit changes. Every adjacent pair in the table has this property, including the wrap from 7 back to 0 (100 to 000, again one bit).

Converting binary to Gray

The conversion is a single XOR:

$$\text{gray} = \text{binary} \oplus (\text{binary} \gg 1)$$

function [WIDTH-1:0] bin_to_gray;
    input [WIDTH-1:0] bin;
    begin
        bin_to_gray = bin ^ (bin >> 1);
    end
endfunction

Converting Gray back to binary

The reverse is a cascaded XOR, where each binary bit depends on all the higher Gray bits:

function [WIDTH-1:0] gray_to_bin;
    input [WIDTH-1:0] gray;
    integer i;
    reg [WIDTH-1:0] bin;
    begin
        bin[WIDTH-1] = gray[WIDTH-1];
        for (i = WIDTH-2; i >= 0; i = i - 1)
            bin[i] = bin[i+1] ^ gray[i];
        gray_to_bin = bin;
    end
endfunction

You need this whenever the receiving side wants to do arithmetic on the synchronized pointer, for instance to compute how many entries are in the FIFO. For the plain full and empty flags the next article shows that a comparison in Gray code is enough.

A Gray-code counter for FIFO pointers

You do not have to count in binary and convert every cycle. A counter can keep both representations, which is what real FIFO pointer logic does:

module gray_counter #(parameter WIDTH = 4) (
    input  wire             clk, rst_n, en,
    output reg [WIDTH-1:0]  gray_out
);
    reg [WIDTH-1:0] bin_count;

    always @(posedge clk or negedge rst_n) begin
        if (!rst_n) begin
            bin_count <= 0;
            gray_out  <= 0;
        end else if (en) begin
            bin_count <= bin_count + 1'b1;
            gray_out  <= (bin_count + 1'b1) ^ ((bin_count + 1'b1) >> 1);
        end
    end
endmodule

bin_count is for local arithmetic and addressing on this side of the boundary; gray_out is the value that is safe to hand across to the other clock domain. The asynchronous FIFO in the next article uses exactly this pair: each side keeps its own pointer in binary for its own bookkeeping, and only the Gray version ever crosses.

Gray code does not make a value cross clock domains faster, and it does not remove the need for a two-flop synchronizer on the receiving side; you still need that for the single-bit metastability reasons from Module 3. What Gray code guarantees is that if a sampling edge catches the value mid-transition, the result is still one of the two genuinely valid values. Gray code and the synchronizer solve two different problems and you need both. One without the other is still broken.

Practice Exercise

Verify by hand that the Gray code transition from decimal 7 to decimal 0 (the wrap in a 3-bit counter) changes exactly one bit, using the binary-to-Gray formula.

Synchronizing a multi-bit binary value across clock domains is unsafe in a way a single bit is not: when more than one bit changes at once, a misaligned sampling edge can capture a value the source never held. Gray code guarantees exactly one bit changes between adjacent values, including at the wrap, which together with the ordinary two-flop synchronizer is the standard way a counter crosses between clocks. In the next article we put Gray pointers to work in the asynchronous FIFO.