Project: How Does a Synchronous FIFO Know When It Is Full?

By giving each pointer one more bit than it needs to address the memory. The read and write pointers both count from 0, and the FIFO is empty when they are equal. When the write pointer has gone all the way round and caught up with the read pointer, the address bits are equal again, but the extra top bit differs, because the writer has wrapped once more than the reader. That one bit is what tells full from empty.

What you'll learn

  • Why equal addresses alone can't tell full from empty
  • The extra-bit pointer scheme and the count it gives for free
  • A complete synchronous FIFO in Verilog
  • A self-checking testbench with a queue model and random traffic

Conventions and assumptions

One clock for both reading and writing (a synchronous FIFO; crossing clock domains needs an asynchronous FIFO with Gray-coded pointers). DEPTH is a power of 2. Read data appears on the clock after rd_en. Simulated in Icarus Verilog 12 and linted with Verilator 5.036 with -Wall, with no warnings.

Step 1: the full and empty problem

A 16-entry FIFO needs 4 address bits. Start with both pointers at 0: empty. Write 16 times and the write pointer wraps back to 0, equal to the read pointer again, but now the FIFO is full. With only 4 bits the two states look identical. Use 5-bit pointers and the write pointer reaches 16 (binary 10000) while the read pointer is 0 (00000): the low 4 bits match and the top bit differs, so full. The count is simply wr_ptr − rd_ptr in 5 bits.

Synchronous FIFO structureA write port and a read port share a 16-word memory. Five-bit write and read pointers address it; comparing them gives full, empty and the count.Write portwr_en, wr_dataMemory16 x 8 bitsRead portrd_en, rd_datawr_ptr5 bitsrd_ptr5 bitsComparefull, empty, countaddraddr
Each pointer has one bit more than the address needs. Equal pointers mean empty; pointers differing only in the top bit mean full.
wr_ptrrd_ptrLow 4 bits equal?Top bitsState
0000000000yessameempty
1000000000yesdifferfull, 16 entries
0001111110no5 entries (3 − 30 mod 32)
1010000100yesdifferfull

Step 2: the Verilog

sync_fifo.v
// Synchronous FIFO: one clock for both sides. DEPTH must be a power of 2.
// The pointers carry one extra bit: equal pointers mean empty, and pointers
// that differ only in that top bit mean full.
module sync_fifo #(parameter WIDTH = 8, parameter DEPTH = 16, parameter AW = $clog2(DEPTH)) (
  input  wire             clk,
  input  wire             rst,
  input  wire             wr_en,
  input  wire [WIDTH-1:0] wr_data,
  input  wire             rd_en,
  output reg  [WIDTH-1:0] rd_data,
  output wire             full,
  output wire             empty,
  output wire [AW:0]      count
);
  reg [WIDTH-1:0] mem [0:DEPTH-1];
  reg [AW:0] wr_ptr, rd_ptr;

  wire do_write = wr_en && !full;     // writes when full are dropped
  wire do_read  = rd_en && !empty;    // reads when empty are ignored

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

  always @(posedge clk) begin
    if (rst) begin
      wr_ptr <= 0;
      rd_ptr <= 0;
      rd_data <= 0;
    end else begin
      if (do_write) begin
        mem[wr_ptr[AW-1:0]] <= wr_data;
        wr_ptr <= wr_ptr + 1'b1;
      end
      if (do_read) begin
        rd_data <= mem[rd_ptr[AW-1:0]];   // data appears the clock after rd_en
        rd_ptr <= rd_ptr + 1'b1;
      end
    end
  end
endmodule

Writes when full and reads when empty are simply dropped, so the pointers never pass each other. A write is also dropped when the FIFO is full even if a read happens on the same clock; allowing that write is a small extension, at the cost of a longer path into the full logic.

Step 3: a testbench with a model

The testbench keeps its own circular queue. Before each clock it decides, exactly as the FIFO should, whether the write and read happen, updates the model, and remembers what the read should return. After the clock it checks the data, and before each clock it checks full, empty and count against the model's size. Directed tests fill past full and drain past empty; then 5,000 clocks of random pushes and pops exercise everything in between.

tb_sync_fifo.v: the model
  task drive(input w, input r, input [W-1:0] d);
    reg do_w, do_r;
    begin
      @(negedge clk);
      if (full !== (n == D) || empty !== (n == 0) || count !== n) begin errors = errors + 1; $display("flags: n %0d full %b empty %b count %0d", n, full, empty, count); end
      wr_en = w; rd_en = r; wr_data = d;
      do_w = w && (n < D); do_r = r && (n > 0);
      if (w && !do_w) dropped = dropped + 1;
      if (r && !do_r) ignored = ignored + 1;
      if (do_r) begin expect_data = model[head]; expect_valid = 1; head = (head + 1) % D; reads = reads + 1; end
      if (do_w) begin model[tail] = d; tail = (tail + 1) % D; writes = writes + 1; end
      n = n + do_w - do_r;
      step;
    end
  endtask

What the simulation shows

Icarus Verilog output
after filling: full 1, count 16, dropped 4
after draining: empty 1, count 0, ignored 2
2426 writes, 2419 reads, 55 dropped when full, 123 ignored when empty, 0 errors
PASS

Common mistakes

  • Using address-width pointers, so full and empty can't be told apart.
  • Letting a write through when full, which overwrites the oldest data.
  • Forgetting that read data arrives a clock after rd_en, and checking it too early.
  • Using this design between two clock domains. The pointers would be sampled mid-change; use an asynchronous FIFO with Gray-coded pointers.
FIFO filling to fullWith writes on every clock the count climbs 13, 14, 15, 16; full rises at 16 and the next two writes are dropped; one read brings the count back to 15.droppedclkwr_enrd_encount1314151615full
Near the top of a 16-deep FIFO: once full is high, writes are dropped until a read makes room.

Check your understanding

  • Q1. How many pointer bits does a 64-entry FIFO need? Answer: 7: six for the address and one wrap bit.
  • Q2. wr_ptr = 01000 and rd_ptr = 11000 in a 16-deep FIFO. Full or empty? Answer: full. The low bits match and the top bits differ.
  • Q3. Why can't the count be computed from the address bits alone? Answer: when they are equal it can be 0 or 16; the extra bit resolves it.

Related

Sources

Last verified

Simulated in Icarus Verilog 12 and linted with Verilator 5.036 on 14 November 2026; the output above is copied from that run, and the pointer arithmetic is checked in the site's tests (lib/projectNumbers.test.js). The full files are in the site's repository under scripts/projects/fifo.