The Asynchronous FIFO

The previous article gave us Gray-coded pointers. This one uses them to build the FIFO that carries data between two unrelated clocks.

Real systems rarely have one clock end to end. A USB PHY runs on its own clock, a DDR controller on another, the processor core on a third. The moment two of these need to exchange a stream of data, not a single bit but a stream, you need an asynchronous FIFO, where the write side and the read side run on independent clocks. Nearly every clock domain crossing that carries more than a bit or a simple handshake goes through one of these.

One memory, two clocks, pointers crossing both ways

The memory array itself does not care about clocks. A dual-port RAM like the one from Section 7.1 can have one port written by wr_clk and the other read by rd_clk, with no synchronization on the data path, as long as each side only touches locations the other side has finished with. That guarantee is what the pointers provide, which means the pointers, not the data, are what has to cross the clock boundary.

Both pointers travel. wr_ptr has to reach the read side so empty can be computed there, and rd_ptr has to reach the write side so full can be computed there. Each crossing uses exactly the tools from the last two articles: Gray-code the pointer before it crosses, then run it through a two-flop synchronizer on the receiving side.

Full and empty in Gray code

The synchronous FIFO compared binary pointers directly. Gray code does not preserve ordinary arithmetic comparison, but the same idea (compare the address, then check the wrap indicator) still works in Gray code’s own terms:

• Empty, checked in the read clock domain: the read pointer equals the synchronized write pointer, both in Gray. Direct equality works as in the binary case, since two Gray values are equal exactly when the binary values were.
• Full, checked in the write clock domain: the write pointer’s Gray code equals the synchronized read pointer’s Gray code, except that the top two bits must both be inverted. This looks odd the first time, but it is the Gray-code equivalent of “same address, different wrap bit”. Because of how Gray code is built, a wrap shows up as the top two bits differing rather than one.

wire full = (wr_ptr_gray[PTR_WIDTH-1]   != rd_ptr_gray_sync[PTR_WIDTH-1]) &&
            (wr_ptr_gray[PTR_WIDTH-2]   != rd_ptr_gray_sync[PTR_WIDTH-2]) &&
            (wr_ptr_gray[PTR_WIDTH-3:0] == rd_ptr_gray_sync[PTR_WIDTH-3:0]);

The complete asynchronous FIFO

`timescale 1ns / 1ps
`default_nettype none

module async_fifo #(
    parameter DATA_WIDTH = 8,
    parameter DEPTH      = 16,
    parameter ADDR_WIDTH = $clog2(DEPTH)
) (
    // Write side
    input  wire                   wr_clk, wr_rst_n,
    input  wire                   wr_en,
    input  wire [DATA_WIDTH-1:0]  wdata,
    output wire                   full,
    // Read side
    input  wire                   rd_clk, rd_rst_n,
    input  wire                   rd_en,
    output reg  [DATA_WIDTH-1:0]  rdata,
    output wire                   empty
);
    reg [DATA_WIDTH-1:0] mem [0:DEPTH-1];

    reg [ADDR_WIDTH:0] wr_ptr_bin, wr_ptr_gray;
    reg [ADDR_WIDTH:0] rd_ptr_bin, rd_ptr_gray;

    // Two-flop synchronizers carrying each Gray pointer into the OTHER clock domain
    reg [ADDR_WIDTH:0] rd_ptr_gray_s1, rd_ptr_gray_sync;   // rd_ptr, synchronized into wr_clk
    reg [ADDR_WIDTH:0] wr_ptr_gray_s1, wr_ptr_gray_sync;   // wr_ptr, synchronized into rd_clk

    // ---- Write domain ----
    always @(posedge wr_clk or negedge wr_rst_n) begin
        if (!wr_rst_n) begin
            wr_ptr_bin <= 0; wr_ptr_gray <= 0;
        end else if (wr_en && !full) begin
            mem[wr_ptr_bin[ADDR_WIDTH-1:0]] <= wdata;
            wr_ptr_bin  <= wr_ptr_bin + 1'b1;
            wr_ptr_gray <= (wr_ptr_bin + 1'b1) ^ ((wr_ptr_bin + 1'b1) >> 1);
        end
    end

    always @(posedge wr_clk or negedge wr_rst_n) begin
        if (!wr_rst_n) begin
            rd_ptr_gray_s1 <= 0; rd_ptr_gray_sync <= 0;
        end else begin
            rd_ptr_gray_s1   <= rd_ptr_gray;        // stage 1
            rd_ptr_gray_sync <= rd_ptr_gray_s1;     // stage 2: now safe to use in wr_clk domain
        end
    end

    assign full = (wr_ptr_gray[ADDR_WIDTH]   != rd_ptr_gray_sync[ADDR_WIDTH]) &&
                  (wr_ptr_gray[ADDR_WIDTH-1] != rd_ptr_gray_sync[ADDR_WIDTH-1]) &&
                  (wr_ptr_gray[ADDR_WIDTH-2:0] == rd_ptr_gray_sync[ADDR_WIDTH-2:0]);

    // ---- Read domain ----
    always @(posedge rd_clk or negedge rd_rst_n) begin
        if (!rd_rst_n) begin
            rd_ptr_bin <= 0; rd_ptr_gray <= 0; rdata <= {DATA_WIDTH{1'b0}};
        end else if (rd_en && !empty) begin
            rdata      <= mem[rd_ptr_bin[ADDR_WIDTH-1:0]];
            rd_ptr_bin  <= rd_ptr_bin + 1'b1;
            rd_ptr_gray <= (rd_ptr_bin + 1'b1) ^ ((rd_ptr_bin + 1'b1) >> 1);
        end
    end

    always @(posedge rd_clk or negedge rd_rst_n) begin
        if (!rd_rst_n) begin
            wr_ptr_gray_s1 <= 0; wr_ptr_gray_sync <= 0;
        end else begin
            wr_ptr_gray_s1   <= wr_ptr_gray;        // stage 1
            wr_ptr_gray_sync <= wr_ptr_gray_s1;     // stage 2: now safe to use in rd_clk domain
        end
    end

    assign empty = (rd_ptr_gray == wr_ptr_gray_sync);
endmodule

The structure is symmetric. The write domain keeps its own pointer and synchronizes the other side’s pointer in; the read domain is the mirror image. Neither side ever touches the other’s raw binary pointer or its clock. Everything that crosses is Gray-coded first and double-flopped on arrival, per the previous article’s rule.

The flags are conservative, and that is correct

The synchronized pointer is two clock cycles stale by the time it can be used, so full and empty computed from it are always conservative. The FIFO may report “full” for a couple of extra write cycles after the reader has actually freed space, and “empty” for a couple of read cycles after the writer has actually put something in. This is expected behaviour, not a bug: an asynchronous FIFO is always slightly more pessimistic about its own state than a synchronous one, and that pessimism is the price of safety across an unrelated clock boundary. Size the FIFO with a little headroom over the burst calculation from the first article to account for it.

Practice Exercise

Explain, in terms of synchronizer latency, why the write side’s full flag can stay at 1 for up to two wr_clk cycles after the reader has drained an entry, and why the staleness can never cause the opposite, dangerous mistake.

The asynchronous FIFO is the payoff of the last two articles: a dual-port memory that does not care about clocks, Gray pointers double-flopped across the boundary in both directions, full/empty logic adapted to Gray code, and a built-in conservatism from synchronizer latency. In the next article we verify it, which turns out to be a different kind of testbench from anything in Module 6.