The Synchronous FIFO and the Full/Empty Problem

The previous article set out what a FIFO is for. This one builds the single-clock version.

Here is a puzzle to sit with before writing any code. A FIFO’s write pointer and read pointer both start at 0. Write nothing, read nothing: the pointers are equal and the FIFO is empty. Now write until the FIFO is completely full, and the write pointer wraps all the way round to where it started, equal to the read pointer again. Two opposite conditions, the same pointer values. How do you tell them apart?

The obvious approach fails

If wr_ptr == rd_ptr is your only test, you cannot distinguish “nothing has been written” from “the FIFO is full and the write pointer has lapped once”. Whatever logic you build on top of that comparison gets one of the two states wrong: either it reports full as empty and the consumer reads garbage, or it reports empty as full and the producer refuses to write into space that is free.

The fix: one extra bit

The standard trick, and it really is standard, you will see it in essentially every synchronous FIFO, is to make the pointers one bit wider than needed to address the memory. For DEPTH entries you need $\log_2(\text{DEPTH})$ bits to address any entry; make the pointer $\log_2(\text{DEPTH}) + 1$ bits.

The rule this buys you:

• Empty: the pointers are exactly equal, including the extra top bit.
• Full: the lower address bits are equal (same location), but the top bit differs, meaning the write pointer has wrapped exactly once more than the read pointer.

wire full  = (wr_ptr[PTR_WIDTH-1]   != rd_ptr[PTR_WIDTH-1]) &&
             (wr_ptr[PTR_WIDTH-2:0] == rd_ptr[PTR_WIDTH-2:0]);
wire empty = (wr_ptr == rd_ptr);

The extra bit is counting laps around the memory, not addresses within it. Equal addresses with equal lap counts means nothing new since the last read: empty. Equal addresses with different lap counts means the writer has lapped the reader: full.

The complete synchronous FIFO

`timescale 1ns / 1ps
`default_nettype none

module sync_fifo #(
    parameter DATA_WIDTH = 8,
    parameter DEPTH      = 16,             // must be a power of 2 for this pointer scheme
    parameter ADDR_WIDTH = $clog2(DEPTH)
) (
    input  wire                   clk, rst_n,
    input  wire                   wr_en,
    input  wire [DATA_WIDTH-1:0]  wdata,
    output wire                   full,
    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, rd_ptr;   // ADDR_WIDTH+1 bits: the extra bit is the trick

    // Write side
    always @(posedge clk or negedge rst_n) begin
        if (!rst_n) begin
            wr_ptr <= 0;
        end else if (wr_en && !full) begin
            mem[wr_ptr[ADDR_WIDTH-1:0]] <= wdata;
            wr_ptr <= wr_ptr + 1'b1;
        end
    end

    // Read side
    always @(posedge clk or negedge rst_n) begin
        if (!rst_n) begin
            rd_ptr <= 0;
            rdata  <= {DATA_WIDTH{1'b0}};
        end else if (rd_en && !empty) begin
            rdata  <= mem[rd_ptr[ADDR_WIDTH-1:0]];
            rd_ptr <= rd_ptr + 1'b1;
        end
    end

    assign empty = (wr_ptr == rd_ptr);
    assign full  = (wr_ptr[ADDR_WIDTH]   != rd_ptr[ADDR_WIDTH]) &&
                   (wr_ptr[ADDR_WIDTH-1:0] == rd_ptr[ADDR_WIDTH-1:0]);
endmodule

Note wr_en && !full and rd_en && !empty guarding every pointer movement. This is the FIFO enforcing its own backpressure. A producer that ignores full and asserts wr_en anyway does not corrupt the FIFO; the write is ignored rather than wrapping the pointer into unread data. That is a safety net, not a substitute for the producer respecting full. A producer that relies on the guard is still losing data, just failing safely instead of corrupting the buffer.

Note also mem[wr_ptr[ADDR_WIDTH-1:0]]: only the lower bits address the memory. The top bit exists purely for full/empty detection and never takes part in addressing.

Why the power-of-two restriction

This scheme relies on the pointer wrapping at a power-of-two boundary, so that “the top bit flips” coincides exactly with “the address bits wrap to zero”. A depth of 10, say, needs either extra comparison logic to detect the wrap explicitly or a separate occupancy counter. That is more logic for a depth that is rarely a hard requirement; padding up to the next power of two usually costs an acceptable amount of unused memory in exchange for the simpler, faster comparison.

Testbench: filling, draining and the boundaries

module tb_sync_fifo;
    parameter DATA_WIDTH = 8, DEPTH = 4;   // small depth to exercise wrap quickly
    reg clk = 0, rst_n, wr_en, rd_en;
    reg [DATA_WIDTH-1:0] wdata;
    wire [DATA_WIDTH-1:0] rdata;
    wire full, empty;

    sync_fifo #(.DATA_WIDTH(DATA_WIDTH), .DEPTH(DEPTH)) dut (
        .clk(clk), .rst_n(rst_n), .wr_en(wr_en), .wdata(wdata), .full(full),
        .rd_en(rd_en), .rdata(rdata), .empty(empty)
    );

    always #5 clk = ~clk;

    integer i;
    initial begin
        $dumpfile("tb.vcd");
        $dumpvars(0, tb_sync_fifo);

        rst_n = 0; wr_en = 0; rd_en = 0; wdata = 0;
        @(negedge clk); rst_n = 1;

        if (!empty) $display("FAIL: expected empty after reset");

        // Fill completely
        for (i = 0; i < DEPTH; i = i + 1) begin
            wdata = i; wr_en = 1;
            @(negedge clk);
        end
        wr_en = 0;
        if (!full) $display("FAIL: expected full after writing DEPTH entries");
        else $display("PASS: FIFO reports full after %0d writes", DEPTH);

        // Attempt an overflow write: should be ignored
        wdata = 8'hFF; wr_en = 1;
        @(negedge clk);
        wr_en = 0;

        // Drain completely, checking order and that the overflow write did nothing
        for (i = 0; i < DEPTH; i = i + 1) begin
            rd_en = 1;
            @(negedge clk);
            rd_en = 0;
            if (rdata !== i)
                $display("FAIL: expected %0d, got %0d (overflow write may have corrupted data)", i, rdata);
        end

        if (!empty) $display("FAIL: expected empty after draining all entries");
        else $display("PASS: FIFO drained in order, no corruption from the overflow write");

        $finish;
    end
endmodule

The overflow write in the middle is the important part. It checks that the guarded write logic protected the contents, not only that a normal fill and drain works.

One mistake I want to warn about: a design with wrong full/empty detection almost never fails on the first few reads and writes. Short tests rarely reach the exact pointer wrap where the bug lives. It shows up only once the FIFO has been filled and drained enough times for the pointers to wrap at least once. A testbench that writes 4 entries into a depth-4 FIFO and reads them back once can pass cleanly and hide a bug that would corrupt data in any longer-running system. Run the fill and drain several times over.

The extra pointer bit is the whole trick: it is a lap count, and equal lap counts mean empty while different lap counts mean full. Guard every pointer update with the matching flag and an accidental overflow write or underflow read fails safely. In the next article we meet Gray code, which is what makes this same pointer scheme safe when the two sides no longer share a clock.