Difficulty: Hard · Puzzle 3 of 6 · Topic: FIFO, Arbitration and Credit Puzzles
An asynchronous FIFO has depth 8 and 4-bit pointers (binary 0-15, Gray-coded for crossing). Using only the Gray values, full is wptr_gray == {~rptr_gray[3:2], rptr_gray[1:0]} and empty is wptr_gray == rptr_gray. For the six (wptr, rptr) pairs in the code, which are full, which are empty? Also: how many words does each hold?
`timescale 1ns/1ns
module tb;
localparam int AW = 3; // depth 8 -> pointers are AW+1 = 4 bits
function automatic bit [AW:0] b2g(bit [AW:0] b); return b ^ (b >> 1); endfunction
// Gray-pointer flags, evaluated with the other side's pointer already in Gray code
function automatic bit is_full (bit [AW:0] wg, bit [AW:0] rg);
return wg == {~rg[AW:AW-1], rg[AW-2:0]}; // top TWO bits inverted, the rest equal
endfunction
function automatic bit is_empty(bit [AW:0] wg, bit [AW:0] rg);
return wg == rg;
endfunction
task automatic show(int w, int r);
bit [AW:0] wg = b2g(w[AW:0]), rg = b2g(r[AW:0]);
$display("wptr=%2d (gray %b) rptr=%2d (gray %b) words=%0d full=%0b empty=%0b",
w, wg, r, rg, (w - r) & 15, is_full(wg, rg), is_empty(wg, rg));
endtask
initial begin
int bad = 0;
show(8, 0); show(0, 0); show(8, 8); show(7, 0); show(9, 1); show(12, 5);
// exhaustive check against the binary definition, legal occupancy 0..8 only
for (int w = 0; w < 16; w++)
for (int r = 0; r < 16; r++) begin
int words;
words = (w - r) & 15;
if (words <= 8) begin
if (is_full (b2g(w[AW:0]), b2g(r[AW:0])) != (words == 8)) bad++;
if (is_empty(b2g(w[AW:0]), b2g(r[AW:0])) != (words == 0)) bad++;
end
end
$display("gray flags disagree with binary occupancy in %0d cases", bad);
#1 $finish;
end
endmoduleConvert with g = b ^ (b >> 1). Then apply the two comparisons. Cross-check with the word count (wptr - rptr) mod 16.
1) (8, 0): gray 1100 vs 0000. Inverting the top two bits of 0000 gives 1100 -> full (8 words).
2) (0, 0): equal -> empty. (8, 8): gray 1100 = 1100 -> empty (the pointers wrapped together, 0 words).
3) (7, 0): gray 0100 vs 0000; neither full nor empty (7 words).
4) (9, 1): gray 1101 vs 0001; inverting the top two bits of 0001 gives 1101 -> full (8 words).
5) (12, 5): gray 1010 vs 0111; not full (7 words).
6) An exhaustive check over all legal occupancies confirms the Gray rule matches the binary definition in every case.Answer: Full: (8,0) and (9,1). Empty: (0,0) and (8,8). Not full or empty: (7,0) with 7 words and (12,5) with 7 words.
Checked by running the code in Verilator 5; the printed output supports the answer above. The Gray-code flags are checked against the binary word count for every legal (wptr, rptr) pair; zero disagreements.
In binary, 'full' means MSBs differ and the rest equal. In Gray code the same state shows up as the TOP TWO bits inverted and the rest equal, because the Gray reflection flips the second bit too. Copying the binary rule (invert only the MSB) never reports full.
Why not compare binary pointers directly across the two clock domains? Model answer: A binary increment such as 0111 -> 1000 changes several bits at once; a synchronizer can capture some old and some new bits, producing a value that was never on the bus (for example 1111). Gray code changes one bit per increment, so the captured value is always either the old or the new pointer and the error is only a conservative one-cycle delay.