Asynchronous FIFO (Gray-Code Pointers)

Hard · Clock Domain Crossing · Memories & FIFOs

Implement an asynchronous FIFO: a queue whose write side and read side run on two unrelated clocks. It is the standard way to move a stream of multi-bit data between clock domains.

How it works (and what makes it hard)

The storage is an ordinary memory with 2**ADDR_W entries. The write side owns a write pointer (clocked by wclk) and the read side owns a read pointer (clocked by rclk). The hard part is the flags:

• wfull lives in the write domain, but depends on the read pointer;
• rempty lives in the read domain, but depends on the write pointer.

So each pointer must cross into the other domain through a two-flop synchronizer. A multi-bit binary counter cannot be synchronized bit by bit: going from 0111 to 1000 changes four bits, and a destination flop sampling during the change could see any mix, such as 1111. The fix is to pass the pointers in Gray code, where consecutive values differ in exactly one bit. Then a synchronized pointer is always either the old value or the new value. Either one is safe, because the other domain then sees the FIFO as fuller (wfull side) or emptier (rempty side) than it really is. That is the safe direction.

Two more classic details:

• Pointers have one extra bit (ADDR_W + 1 bits). The low ADDR_W bits address the memory;

the extra bit tells apart "pointers equal because empty" from "pointers equal because the writer is a full lap ahead".

• Full means the write pointer is exactly 2**ADDR_W ahead of the read pointer. Work out what

that means for the Gray codes of the two pointers. (It is not the same rule as for binary pointers.)

Simulation cannot show metastability or the multi-bit sampling hazard, so two structural rules are required but cannot be graded (a design that breaks them may pass the tests here and still fail in silicon):

• Each pointer crosses into the other domain in Gray code. A FIFO that synchronizes binary

pointers can see a mix of old and new bits and compute a completely wrong flag.

• Each pointer passes through two flip-flops clocked by the destination clock before any

logic uses it. With one flop (even followed by a registered flag), a metastable value can reach the flag logic. The two-flop rule is also why the flags have a minimum latency (see below), and that part is graded.

Specification

module async_fifo #(
    parameter int WIDTH  = 8,
    parameter int ADDR_W = 3      // depth = 2**ADDR_W, ADDR_W >= 2
) (
    input  logic             wclk,
    input  logic             wrst,    // synchronous to wclk, active-high
    input  logic             winc,    // write request
    input  logic [WIDTH-1:0] wdata,
    output logic             wfull,
    input  logic             rclk,
    input  logic             rrst,    // synchronous to rclk, active-high
    input  logic             rinc,    // read request (pop)
    output logic [WIDTH-1:0] rdata,
    output logic             rempty
);

Let stored be the number of entries written and not yet read: accepted writes minus accepted reads, counted over all clock edges so far.

• Capacity. The FIFO holds exactly 2**ADDR_W entries (8 with the default parameters).
• Write. On a rising edge of wclk with wrst = 0: if winc = 1 and wfull = 0, wdata is

appended. If winc = 1 while wfull = 1, the write is ignored (the FIFO is unchanged).

• Read (show-ahead). Whenever rempty = 0, rdata shows the oldest stored entry (no

read request needed to see it). On a rising edge of rclk with rrst = 0: if rinc = 1 and rempty = 0, that entry is removed. If rinc = 1 while rempty = 1, the read is ignored. rdata is not checked while rempty = 1.

• Safety (must always hold). A write is never accepted while stored = 2**ADDR_W (no

overflow), rempty is never 0 while stored = 0 (no underflow), and entries come out exactly once, in order.

• Pessimism is allowed, but bounded. Because of the synchronizers, wfull may stay 1 for a

while after a read made room, and rempty may stay 1 for a while after a write. Both flags must become exact once 4 rising edges of their own clock have passed since the other side's last transfer:

• if no read was accepted during the last 4 wclk edges, then wfull = (stored == 2**ADDR_W);
• if no write was accepted during the last 4 rclk edges, then rempty = (stored == 0).

Each side's own transfers must be reflected immediately: for example, a write that makes the FIFO full must make wfull = 1 in the very next wclk cycle.

• ...and the other side cannot be seen too early. Because each pointer passes through two

synchronizer flops, a write cannot make rempty fall before the second rclk rising edge after the write's wclk edge, and a read cannot make wfull fall before the second wclk rising edge after the read's rclk edge. (In the cycle that starts at the first such edge, the flag must still treat that transfer as not having happened.) A FIFO whose flags react sooner has no real synchronizer.

• Reset. wrst is synchronous to wclk and rrst to rclk. On every wclk edge with

wrst = 1, wfull becomes 0 and the write side forgets everything; on every rclk edge with rrst = 1, rempty becomes 1 and the read side forgets everything. Neither reset may act between edges of its own clock. The tests assert wrst and rrst together, hold them for at least 5 cycles of the slower clock with winc = rinc = 0, and release them together. After reset the FIFO is empty.

The hidden tests run the two clocks at 10 ns / 17 ns, 17 ns / 10 ns and 10 ns / 12.3 ns, with a Python scoreboard that catches lost, duplicated, reordered or overwritten entries. They build the FIFO with the default parameters and also with other values of WIDTH and ADDR_W, so derive every width and depth from the parameters.

Example (not to scale)

Three writes (A, B, C) on the fast wclk. rempty falls a few rclk cycles later, after the write pointer has crossed the synchronizer. rdata shows A without a request; each rinc edge pops one entry.

Sign up free to solve Asynchronous FIFO (Gray-Code Pointers) in your browser.

More Clock Domain Crossing problems

• Pulse Synchronizer (Toggle CDC)
• Two-Flop Synchronizer