One extra bit

A FIFO with 2^AW entries uses pointers with AW + 1 bits. The lower AW bits address the memory, and the extra top bit counts laps.

Equal pointers mean empty. Pointers that differ only in the top bit mean full, with the write pointer exactly one lap ahead.

Binary to Gray

Each Gray step flips exactly one bit, including the wrap from the last value to zero. The conversion back is a running XOR from the top bit down.

The Gray conversion and the full comparison are small: a row of XORs and a 5-bit comparator. Both pointers cross as Gray code.

Convert to Gray before the pointer register, so the Gray value is itself a flop and cannot glitch (see the bus lesson).

The full comparison in the Gray domain

The write side compares its next pointer with the synchronised read pointer, both in Gray code. In binary, full means same lower bits with opposite top bits.

In Gray code that becomes top two bits inverted, remaining bits equal. The final section proves this identity for every pointer value.

Derive it with a four-entry FIFO

For depth 4, AW=2 and the binary pointer has three bits: one lap bit followed by two address bits. Start with an ideal snapshot where the read pointer is 001 (address 1, lap 0). Hold the read pointer fixed: a write pointer of 001 is empty; after four accepted writes it becomes 101 (address 1, lap 1), which is full. The address is the same but the write pointer is one complete memory lap ahead. Each pointer addresses the slot for its next read or write.

Read each ring clockwise from slot 0; the arrows show which slot each pointer will use next.

• In both rings the two pointers point at slot 1, so the address bits alone cannot tell empty from full.

• On the left the lap bits are equal: nothing is unread. On the right the write pointer has gone round once more: all four slots are unread.

• The binary difference gives the occupancy directly: 1 - 1 = 0 and 5 - 1 = 4.

Each table row pairs a read pointer with the write pointer four entries ahead: w = (r + 4) mod 8.

Within each row, the read and write pointers differ in two Gray bits and only one binary bit. These are pointers four entries apart; consecutive Gray steps still change only one bit. For three-bit binary b2 b1 b0, Gray is g2=b2, g1=b2 XOR b1, g0=b1 XOR b0. A full-distance lap flips b2 alone: g2 flips because it is b2, g1 flips because it contains b2, and g0 stays the same. The same argument works at any power-of-two depth of at least 2: only the top two Gray equations contain the binary lap bit.

That is why flipping only the top Gray bit is wrong. For read Gray=001 (binary 001), the full Gray target is 111; changing only its top bit gives 101, which decodes to binary 110 (6), not the required binary 101 (5).

From the picture to the registered flag

Before each write-domain edge, combinational logic computes accepted_write = winc & ~wfull, using the current registered flag, then wbin_next = wbin + accepted_write and its Gray value. Compare that next Gray value with the synchronized read Gray value with its top two bits inverted. With the read pointer held at binary 1 and its synchronized Gray value at 001, the fourth accepted write advances the local pointer from 4 to 5 and registers full on that same edge. The fourth word is stored at address 0; the new full flag blocks a fifth write. Comparing the old pointer instead would register full one edge late and could allow an overwrite.

The distance interpretation assumes writes stop at full and reads stop at empty, keeping true occupancy between 0 and depth. In hardware the remote pointer is delayed by synchronization: a stale read pointer makes the write side overestimate occupancy, so full can assert before the FIFO is truly full or stay asserted after a read frees a slot. A stale write pointer makes the read side underestimate occupancy, so empty can remain asserted while unread words exist. With correctly synchronized Gray pointers, both effects are conservative: they may delay progress but do not permit overwrites or reads of unwritten words. Neither binary pointer nor the full flag is sent unsynchronized across the clocks.

Common mistakes

Testbench

An exhaustive check of one-bit Gray steps, round-trip conversion and the full-detect identity.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

module gray_check;
  localparam int W = 5;                               // 5-bit pointers: a 16-entry FIFO needs AW + 1 = 5 bits
  function automatic logic [W-1:0] bin2gray(logic [W-1:0] b);
    return (b >> 1) ^ b;
  endfunction
  function automatic logic [W-1:0] gray2bin(logic [W-1:0] g);
    logic [W-1:0] b;
    b[W-1] = g[W-1];
    for (int i = W - 2; i >= 0; i--) b[i] = b[i+1] ^ g[i];
    return b;
  endfunction

  int errors = 0, flips;
  logic [W-1:0] g0, g1, diff, back;
  initial begin
    for (int n = 0; n < 2**W; n++) begin
      g0 = bin2gray(W'(n));
      g1 = bin2gray(W'(n + 1));                        // n + 1 wraps from 31 back to 0
      diff = g0 ^ g1;
      flips = $countones(diff);
      if (flips != 1) errors++;                        // consecutive pointers differ in exactly one bit (also across the wrap)
      back = gray2bin(g0);
      if (back !== W'(n)) errors++;                    // converting back gives the original number
    end
    // the "full" comparison: Gray code of (rptr + DEPTH) is Gray code of rptr with its two top bits inverted
    for (int r = 0; r < 2**W; r++) begin
      g0 = bin2gray(W'(r));
      g1 = bin2gray(W'(r + 16));                       // write pointer exactly one lap ahead
      if (g1 !== {~g0[W-1:W-2], g0[W-3:0]}) errors++;
    end
    if (errors == 0) $display("PASS: 32 pointer values: one-bit steps (including wrap), exact round trip, and the full-detect identity {~g[4:3], g[2:0]}");
    else $display("FAIL: %0d errors", errors);
    $finish;
  end
endmodule

Related topics

• The complete design