Gray codes and the asynchronous FIFO
Build the asynchronous FIFO that carries a stream between two clocks, and see why its pointers cross in Gray code: a sample is then late, never wrong.
- Lesson
- R6.4
- Time
- 35 min
- Runs on
- Your browser
- Check
- 5 questions
An asynchronous FIFO sent its write pointer to the read side in binary. The pointer stepped from 1111 to 0000, and the read side caught three old bits and one new: 0111, a position the pointer never held. For one cycle the read side counted eight words waiting when the FIFO held two.
clk. wptr is the pointer on the crossing wires, seen the read side's copy after two flops, holds the words really in the FIFO.- Cycle 2
Edge 22: a write moved the pointer from 1111 to 0000, all four bits at once, less than 1.5 ns before this edge.
- Cycle 3
Edge 23: the first flop had caught bit 3 new and bits 2 to 0 old. Two flops later the read side holds 0111.
- Cycle 4
Edge 24: the read side computes its level from 0111: eight words. The FIFO holds two.
- Cycle 5
Edge 25: the next sample is clean, and the level is back below the truth.
Edges 20 to 25 of the lab run. The bench models what a real flop does when its input changes at the edge; the model is described below.
Only the pointers cross
An asynchronous FIFO moves a stream of words between two clocks that have no fixed relation. The memory is written by the write clock and read by the read clock. Each side keeps its own pointer, a count of the words it has written or read.
Each pointer has one more bit than the address, the lap bit. It flips each time the pointer wraps. Equal pointers mean empty; pointers equal except for the lap bit mean full, one whole lap apart.
wclk, everything right of it on rclk.- Write
The write side stores the word and steps its pointer in the same edge.
Follow the calls, values and waits
- data word 16: Write side → Memory
- The write pointer crosses
The pointer goes through two read-clock flops. The read side compares it with its own pointer to compute
empty.Follow the calls, values and waits
- data wptr 0000: Write side → rq1, rq2
- data wptr 0000: rq1, rq2 → Read side
- Read
The word itself never goes through a synchronizer. By the time the read side sees the pointer, the word has sat still in memory for two cycles.
Follow the calls, values and waits
- data word 16: Memory → Read side
- The read pointer crosses back
The write side computes
fullfrom its own pointer and its copy of the read pointer.Follow the calls, values and waits
- data rptr: Read side → wq1, wq2
- data rptr: wq1, wq2 → Write side
Read the diagram as text
- Write side: wbin_q, wptr_q, full
- wq1, wq2: read pointer, two wclk flops
- Memory: 8 words of 8 bits
- rq1, rq2: write pointer, two rclk flops
- Read side: rbin_q, rptr_q, empty
- Write side → Memory: write word
- Memory → Read side: read word
- Write side → rq1, rq2: wptr_q
- rq1, rq2 → Read side: seen
- Read side → wq1, wq2: rptr_q
- wq1, wq2 → Write side: seen
Each flag is computed in its own domain, from one local pointer and one synchronized copy.
Why a binary pointer tears
A pointer is four bits that cross through four flops. If two bits change at once and the edge lands in the middle, each flop decides for itself. The read side gets a mix of old and new bits: a torn value.
Gray code fixes it by changing one bit per step. Binary to Gray is g = b ^ (b >> 1). Gray back to binary is a running XOR from the top bit down. A torn sample of a Gray pointer has only one bit in doubt, so it reads as the old position or the new one.
| Count | Binary | Gray | Count | Binary | Gray |
|---|---|---|---|---|---|
| 0 | 0000 | 0000 | 8 | 1000 | 1100 |
| 1 | 0001 | 0001 | 9 | 1001 | 1101 |
| 2 | 0010 | 0011 | 10 | 1010 | 1111 |
| 3 | 0011 | 0010 | 11 | 1011 | 1110 |
| 4 | 0100 | 0110 | 12 | 1100 | 1010 |
| 5 | 0101 | 0111 | 13 | 1101 | 1011 |
| 6 | 0110 | 0101 | 14 | 1110 | 1001 |
| 7 | 0111 | 0100 | 15 | 1111 | 1000 |
Four-bit binary against Gray. Every Gray step changes one bit, including the wrap from 15 (1000) back to 0 (0000).
Late, never early
Each side sees the other pointer two or three cycles late. With Gray code the copy is always a real position the pointer held. So the read side can only underestimate the words waiting, and the write side can only underestimate the free space.
That makes the flags conservative: empty may stay 1 after a word arrives, and full may stay 1 after a word leaves. Neither ever says "go" too soon. In the lab, empty fell three read edges after a write into an empty FIFO, 18 times out of 19, and four edges once.
clk.- Cycle 1
Edge 21:
emptyis 1 while the FIFO holds two words. The read side has not seen those writes yet. - Cycle 2
Edge 22: the pointer steps from 1000 to 0000, one bit, the Gray wrap from 15 to 0.
- Cycle 4
Edge 24:
read_levelis 1 with two words held. Low is safe; the read side just waits a cycle.
Edges 20 to 25 of the lab run after the fix: the level never rises above the words held.
Full in Gray is a one-line test. One lap apart, the top two Gray bits are inverted and the rest equal, because the lap bit also flips the next bit's Gray code. The lab decodes both pointers to binary instead, and compares the lap bit and the address.
The depth must be a power of two. A pointer that counted 0 to 11 would wrap from Gray 1110 to 0000, changing three bits at once.
The lab: binary to Gray
| Port | Direction | Width | Meaning |
|---|---|---|---|
| wclk, wrst_n | input | 1 | write side clock and reset |
| write_en | input | 1 | write side: write a word |
| write_data | input | [WIDTH-1:0] | write side: the word |
| full | output | 1 | write side; registered in its own domain |
| rclk, rrst_n | input | 1 | read side clock and reset |
| read_en | input | 1 | a read is taken at an edge where read_en is 1 and empty was 0 |
| read_valid | output | 1 | read_valid and the word follow one cycle after a read is taken |
| read_data | output | [WIDTH-1:0] | read side: the word |
| empty | output | 1 | read side; registered in its own domain |
| read_level | output | [$clog2(DEPTH):0] | words the read side can see; registered in its own domain |
- Clock
- Crossing: only
wptr_qandrptr_qcross, each through two flops; the bench reads them and the first flops by name - Reset
- both sides reset at once by the bench; resetting two domains properly is the next lesson
- Latency
- a read is taken at an edge where
read_enis 1 andemptywas 0;read_validand the word follow one cycle later - Parameters
DEPTH8 words ofWIDTH8 bits; pointers of 4 bits, one of them the lap bit- Corner cases
- a pointer caught mid-change; the wrap from 15 to 0; full and empty in the same run
Binary on the wires
// How a pointer is coded on the wires that cross: plain binary.
function automatic logic [AW:0] to_wire(input logic [AW:0] b);
return b;
endfunction
function automatic logic [AW:0] from_wire(input logic [AW:0] w);
return w;
endfunction
Up to four bits change per step. A sample can be a position the pointer never held.
Gray on the wires
// How a pointer is coded on the wires that cross: Gray code, one bit changes per step.
function automatic logic [AW:0] to_wire(input logic [AW:0] b);
return b ^ (b >> 1);
endfunction
function automatic logic [AW:0] from_wire(input logic [AW:0] w);
logic [AW:0] b;
for (int i = 0; i <= AW; i++) b[i] = ^(w >> i); // bit i is the XOR of bits AW down to i
return b;
endfunction
One bit changes per step. A sample is the old or the new position.
The lab ships with binary pointers. Run it: the read side sees more words than the FIFO holds at 10 edges. Replace the two functions with the Gray versions and run again.
| Measured on the lab bench | Binary | Gray |
|---|---|---|
Edges where read_level was above the words held | 10 | 0 |
| Words read back wrong, of 300 | 0 | 0 |
| Synthesis on this flow | 222 cells, 103 flops, 9 levels of logic | 244 cells, 109 flops, 9 levels of logic |
The data checker stays clean in both runs: here a torn level lasts one cycle. Logic that trusts read_level for a burst of reads would act on words that are not there.
Asked in interviews
Design an asynchronous FIFO. What crosses between the clocks?
Only the two pointers, each through a two-flop synchronizer. The words stay in the memory, written on one clock and read on the other, and they are read only after the pointer that covers them has crossed.
Why Gray-code the pointers?
A binary step can change several bits, and a synchronizer can catch some old and some new. A Gray step changes one bit, so the far side sees the old or the new position. Its flags are late, never early.
How is full computed with Gray pointers?
Compare the write pointer with the synchronized read pointer: the top two bits inverted and the rest equal means one lap apart. Or decode both to binary and compare the lap bit and the address.
Try it
The six e20 to e25 lines are the hook's trace. A line that starts with an edge and "the read side sees" is a torn level; the bench prints the first three of the ten.
With the Gray functions the window prints the second trace, no torn level appears, and the last line ends 0 edges where read_level was above the words held. Synthesize: 222 cells become 244, and 103 flops become 109. With binary coding, each crossing copy equals its count, so the synthesizer merged them; in Gray only the top bits still match.
Synthesize the design to measure its cells and inspect the mapped gates.
e20 wptr=1110 seen=1101 read_level=1 holds=2 empty=0 e21 wptr=1111 seen=1110 read_level=0 holds=2 empty=1 e22 wptr=0000 seen=1111 read_level=1 holds=3 empty=0 e23 wptr=0000 seen=0111 read_level=1 holds=2 empty=0 e24 wptr=0001 seen=0000 read_level=8 holds=2 empty=0 e24 the read side sees 8 words, the FIFO holds 2 e25 wptr=0010 seen=0001 read_level=0 holds=2 empty=1 e50 the read side sees 9 words, the FIFO holds 2 e89 the read side sees 15 words, the FIFO holds 2 300 words sent, 300 read back, 0 wrong; 10 edges where read_level was above the words heldOriginal design · 222 cells · 103 flip-flops · 0 latches · 9 logic levels. Synthesis uses Yosys; counts depend on the toolchain.
Read included file: tb.sv
`timescale 1ns/1ps
module tb;
logic clk = 0;
always #5 clk = ~clk; // the sampling clock: rising edges at 5, 15, 25, ... ns
logic wclk = 0; // the second clock: rising edges at 2.6, 15.6, ... ns
initial begin
#2.6;
forever begin wclk = 1; #6.5; wclk = 0; #6.5; end
end
logic rst_n = 1; // falls at 1 ns: a real edge, so asynchronous resets act before any clock
int edge_n = -1; // the number of the last rising edge of clk
always @(posedge clk) edge_n = edge_n + 1;
localparam int N = 300; // words the producer sends: 0, 1, 2, ...
logic write_en = 0, read_en = 0, full, empty, read_valid;
logic [7:0] write_data = 0, read_data;
logic [3:0] read_level;
int sent = 0, taken = 0, answers = 0, wrong = 0, over = 0, expect_q = 0, wcyc = 0;
// Producer (write domain): offers the next number at 20 of every 32 write-clock edges.
always @(posedge wclk) begin
if (write_en && !full) sent++; // a write is taken at an edge where full was 0
wcyc++;
#1 write_en = rst_n && sent < N && (wcyc % 32) < 20;
write_data = sent[7:0];
end
// Consumer (read domain): asks for a word, except at 12 of every 40 edges.
always @(posedge clk) begin
if (read_en && !empty) taken++; // a read is taken at an edge where empty was 0
#0.5 read_en = rst_n && (edge_n % 40) < 28;
end
// A model of the crossing (bench only): when a pointer bit changes less than 1.5 ns before the
// sampling edge, the first flop catches its old or its new value, picked at random from a fixed
// seed. Real flops do this; zero-delay RTL flops never do.
logic [3:0] w_old = 0, w_now = 0, r_old = 0, r_now = 0;
realtime w_t = -100, r_t = -100;
int unsigned seed = 1;
always @(dut.wptr_q) begin w_old = w_now; w_now = dut.wptr_q; w_t = $realtime; end
always @(dut.rptr_q) begin r_old = r_now; r_now = dut.rptr_q; r_t = $realtime; end
always @(posedge clk) if ($realtime - w_t < 1.5) #0.1 for (int i = 0; i < 4; i++) begin
seed = seed * 1103515245 + 12345;
if (seed[16]) dut.rq1_wptr[i] = w_old[i];
end
always @(posedge wclk) if ($realtime - r_t < 1.5) #0.1 for (int i = 0; i < 4; i++) begin
seed = seed * 1103515245 + 12345;
if (seed[16]) dut.wq1_rptr[i] = r_old[i];
end
// The checks, once per read-clock edge: the level against the words held, every answer
// against the next number. After a wrong answer the checker follows on from it.
task automatic check();
if (edge_n >= 20 && edge_n <= 25)
$display("e%0d wptr=%b seen=%b read_level=%0d holds=%0d empty=%b", edge_n, dut.wptr_q, dut.rq2_wptr, read_level, sent - taken, empty);
if (read_level > sent - taken) begin
over++;
if (over <= 3) $display("e%0d the read side sees %0d words, the FIFO holds %0d", edge_n, read_level, sent - taken);
end
if (read_valid) begin
answers++;
if (read_data !== expect_q[7:0]) begin
wrong++;
if (wrong <= 3) $display("e%0d read %0d, expected %0d", edge_n, read_data, expect_q);
expect_q = read_data;
end
expect_q++;
end
endtask
afifo dut (.wclk(wclk), .wrst_n(rst_n), .write_en(write_en), .write_data(write_data), .full(full),
.rclk(clk), .rrst_n(rst_n), .read_en(read_en), .read_valid(read_valid), .read_data(read_data),
.empty(empty), .read_level(read_level));
// Advance to the next rising edge of clk, wait for the design to settle, then print.
task automatic tick();
@(posedge clk); #1;
check();
endtask
initial begin
#1 rst_n = 0; tick(); tick(); rst_n = 1; // asserted at 1 ns, clk edges 0 and 1 in reset, released 1 ns after edge 1
while (answers < N && edge_n < 2000) tick();
$display("%0d words sent, %0d read back, %0d wrong; %0d edges where read_level was above the words held", sent, answers, wrong, over);
$finish(0); // quiet: no "$finish called" line
end
endmodule
Check yourself
Remember
- An asynchronous FIFO writes words on one clock and reads them on another; only the two pointers cross, each through two flops.
- A binary pointer can change several bits at once, so a synchronizer can catch a position it never held.
- A Gray pointer changes one bit per step, so a sample is the old or the new position, and the flags are late, never early.
- Pointers carry one extra lap bit; in Gray, full is the top two bits inverted and the rest equal, and the depth must be a power of two.