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.

A binary pointer caught mid-changeThe lab design, sampled at the read clock 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.
012345clkwptr11101111000000010010seen110111101111011100000001read_level10180holds232emptylevel 8, holds 2
  1. 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.

  2. 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.

  3. Cycle 4

    Edge 24: the read side computes its level from 0111: eight words. The FIFO holds two.

  4. 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.

Two domains, one memory, two crossingsArrows show signals. Everything left of the memory runs on wclk, everything right of it on rclk.
Two domains, one memory, two crossingsArrows show signals. Everything left of the memory runs on `wclk`, everything right of it on `rclk`. wclk Write side wbin_q, wptr_q, full wclk wq1, wq2 read pointer, two wclkflops queue Memory 8 words of 8 bits rclk rq1, rq2 write pointer, tworclk flops rclk Read side rbin_q, rptr_q, empty write wordread wordwptr_qseenrptr_qseen
  1. Write

    The write side stores the word and steps its pointer in the same edge.

    Follow the calls, values and waits
    1. data word 16: Write side → Memory
  2. 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
    1. data wptr 0000: Write side → rq1, rq2
    2. data wptr 0000: rq1, rq2 → Read side
  3. 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
    1. data word 16: Memory → Read side
  4. The read pointer crosses back

    The write side computes full from its own pointer and its copy of the read pointer.

    Follow the calls, values and waits
    1. data rptr: Read side → wq1, wq2
    2. 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.

CountBinaryGrayCountBinaryGray
000000000810001100
100010001910011101
2001000111010101111
3001100101110111110
4010001101211001010
5010101111311011011
6011001011411101001
7011101001511111000

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.

The same edges with Gray pointersThe lab design after the fix, sampled at the read clock clk.
012345clkwptr10011000000000010011seen10111001100000000001read_levelholds232empty
  1. Cycle 1

    Edge 21: empty is 1 while the FIFO holds two words. The read side has not seen those writes yet.

  2. Cycle 2

    Edge 22: the pointer steps from 1000 to 0000, one bit, the Gray wrap from 15 to 0.

  3. Cycle 4

    Edge 24: read_level is 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

Design brief
PortDirectionWidthMeaning
wclk, wrst_ninput1write side clock and reset
write_eninput1write side: write a word
write_datainput[WIDTH-1:0]write side: the word
fulloutput1write side; registered in its own domain
rclk, rrst_ninput1read side clock and reset
read_eninput1a read is taken at an edge where read_en is 1 and empty was 0
read_validoutput1read_valid and the word follow one cycle after a read is taken
read_dataoutput[WIDTH-1:0]read side: the word
emptyoutput1read side; registered in its own domain
read_leveloutput[$clog2(DEPTH):0]words the read side can see; registered in its own domain
Clock
Crossing: only wptr_q and rptr_q cross, 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_en is 1 and empty was 0; read_valid and the word follow one cycle later
Parameters
DEPTH 8 words of WIDTH 8 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 benchBinaryGray
Edges where read_level was above the words held100
Words read back wrong, of 30000
Synthesis on this flow222 cells, 103 flops, 9 levels of logic244 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
  1. 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.

  2. 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.

  3. 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.

RTLIcarus Verilog · in your browser · Lint: Verilator service · Synthesize: Yosys service
Edit the design, then Run, Lint or Synthesize
Expected: 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 held

Original 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

Predict the outputThe program prints the Gray codes of 7 and 8, then their XOR. What is the output line?
module tb;
  function automatic logic [3:0] gray(input logic [3:0] b);
    return b ^ (b >> 1);
  endfunction
  initial begin
    logic [3:0] a, b;
    a = gray(4'd7);
    b = gray(4'd8);
    $display("%b %b %b", a, b, a ^ b);
    $finish(0);
  end
endmodule
Spot the bugEach option computes full from the 4-bit Gray write pointer wg and the synchronized read pointer rg of an 8-word FIFO. The bench tries every distance from 0 to 8 words. Which one fails?
ConceptWhy do Gray pointers make the flags of an asynchronous FIFO safe to use?
ConceptWhy must the depth of a Gray-pointer asynchronous FIFO be a power of two?
Read the waveformThese are edges 20 to 25 of the lab run with Gray pointers. Which reading is right?
Gray pointers, sampled at the read clock
012345clkseen10111001100000000001read_levelholds232empty

One value per read-clock edge, printed 1 ns after it. holds is the bench's count of words in the FIFO.

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.