Skip to content
Tutorials Center
My learning

Topics

Lesson 36 of 37 ยท Projects and Practice

Project: A Synchronous FIFO

Design a synchronous FIFO in Verilog with read and write pointers, full and empty detection using an extra pointer bit, a self-checking testbench and a depth calculation.

A FIFO (first in, first out buffer) is the glue of digital systems: it smooths bursty data between a producer and a consumer, lets a fast block talk to a slow one, and, in its asynchronous form, carries data between clock domains. Nearly every chip contains dozens. Designing one touches memory inference, pointer arithmetic, status flags and corner-case testing, which is why it is a favourite interview question.

In this project you will design a synchronous FIFO (one clock for reading and writing), learn the extra-bit trick for telling "full" from "empty", write a self-checking testbench against a queue model, and compute how deep a FIFO needs to be. The Verilog is read-only here (no simulator runs on this site); the C programs are labelled stand-ins that run the same pointer logic and checks.

The interface

Signal Direction Meaning
clk, rst_n in clock and active-low reset
wr_en in write wr_data into the FIFO this cycle (ignored if full)
wr_data in data to write
rd_en in read this cycle (ignored if empty)
rd_data out oldest data, valid the cycle after rd_en (registered read)
full, empty out status flags

Parameters: WIDTH (data bits) and DEPTH_LOG2 (the depth is 2^DEPTH_LOG2 words).

The pointer idea

The storage is a memory array used as a circular buffer. A write pointer says where the next word goes and a read pointer says where the oldest word is. Both advance (and wrap) when used.

flowchart LR
  W["wr_ptr<br/>(next to write)"] --> M["memory[0..DEPTH-1]"]
  M --> R["rd_ptr<br/>(next to read)"]

The FIFO is empty when the pointers are equal; the problem is that they are also equal when it is full.

If wr_ptr == rd_ptr, are there 0 words or DEPTH words? You cannot tell from the address bits alone. The standard solution is to make each pointer one bit wider than needed to address the memory. The lower bits address the memory; the extra MSB records how many times the pointer has wrapped:

  • Empty: all bits of the pointers equal.
  • Full: the lower bits equal but the MSBs differ (the writer is exactly one lap ahead).
TEXT
empty = (wr_ptr == rd_ptr)
full  = (wr_ptr[DEPTH_LOG2] != rd_ptr[DEPTH_LOG2]) &&
        (wr_ptr[DEPTH_LOG2-1:0] == rd_ptr[DEPTH_LOG2-1:0])

An alternative is a separate count register, which is simpler to read but adds an up/down counter with a priority issue when read and write occur together.

The Verilog

VERILOG
module sync_fifo #(
  parameter WIDTH      = 8,
  parameter DEPTH_LOG2 = 4                    // 16 words
) (
  input                  clk, rst_n,
  input                  wr_en,
  input      [WIDTH-1:0] wr_data,
  input                  rd_en,
  output reg [WIDTH-1:0] rd_data,
  output                 full, empty
);
  localparam DEPTH = 1 << DEPTH_LOG2;

  reg [WIDTH-1:0]    mem [0:DEPTH-1];
  reg [DEPTH_LOG2:0] wr_ptr, rd_ptr;          // one extra bit

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

  wire do_write = wr_en && !full;
  wire do_read  = rd_en && !empty;

  always @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      wr_ptr <= 0; rd_ptr <= 0; rd_data <= 0;
    end else begin
      if (do_write) begin
        mem[wr_ptr[DEPTH_LOG2-1:0]] <= wr_data;
        wr_ptr <= wr_ptr + 1'b1;
      end
      if (do_read) begin
        rd_data <= mem[rd_ptr[DEPTH_LOG2-1:0]];
        rd_ptr <= rd_ptr + 1'b1;
      end
    end
  end
endmodule

Notes:

  • Memory writes and reads are in one clocked block with non-blocking assignments, so a simultaneous read and write work independently. FPGA tools infer block RAM from this pattern when the read is registered (as here).
  • Writing when full or reading when empty is simply ignored. An alternative is to flag an overflow or underflow error output, which is useful for debugging.
  • The pointer wraps automatically: the wide pointer is DEPTH_LOG2 + 1 bits and its addition overflows.

Running the pointer logic in C

The first stand-in implements the same circular buffer, with an extra-bit pointer and the same full/empty tests, and drives it with a long random sequence of reads and writes, comparing every result with a simple reference queue. This is exactly the structure of the Verilog testbench below. It uses a fixed seed so the run is reproducible.

C Stand-in: FIFO pointers checked against a reference queue

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

The test deliberately writes more often than it reads so the FIFO hits full many times, and sometimes reads when it is empty: both flags are exercised and checked against the count of the reference queue. A FIFO that was only tested while half full would hide exactly the bugs most likely to exist.

The Verilog testbench

VERILOG
`timescale 1ns/1ps
module sync_fifo_tb;
  reg        clk = 0, rst_n = 0, wr_en = 0, rd_en = 0;
  reg  [7:0] wr_data = 0;
  wire [7:0] rd_data;
  wire       full, empty;

  reg [7:0] model [0:1023];
  integer   head = 0, tail = 0, errors = 0, cycle, count_before;
  reg       rd_pending;
  reg [7:0] expected;
  integer   seed = 7;

  always #5 clk = ~clk;

  sync_fifo #(.WIDTH(8), .DEPTH_LOG2(3)) dut (
    .clk(clk), .rst_n(rst_n), .wr_en(wr_en), .wr_data(wr_data),
    .rd_en(rd_en), .rd_data(rd_data), .full(full), .empty(empty));

  initial begin
    #22 rst_n = 1;
    rd_pending = 0;
    for (cycle = 0; cycle < 5000; cycle = cycle + 1) begin
      @(negedge clk);
      // check read data from previous cycle's read
      if (rd_pending && rd_data !== expected) begin
        errors = errors + 1;
        $display("FAIL at %0t: got %h expected %h", $time, rd_data, expected);
      end
      wr_en = ($urandom(seed) % 100) < 55;
      rd_en = ($urandom(seed) % 100) < 45;
      wr_data = cycle[7:0];
      // reference model: both decisions use the occupancy BEFORE this cycle
      count_before = tail - head;
      rd_pending = rd_en && (count_before > 0);
      if (rd_pending) begin expected = model[head % 1024]; head = head + 1; end
      if (wr_en && (count_before < 8)) begin
        model[tail % 1024] = wr_data; tail = tail + 1;
      end
      // flags are checked after the clock edge
      @(posedge clk); #1;
      if (empty !== ((tail - head) == 0)) begin errors = errors + 1; $display("FAIL empty"); end
      if (full  !== ((tail - head) == 8)) begin errors = errors + 1; $display("FAIL full"); end
    end
    if (errors == 0) $display("PASS"); else $display("FAIL: %0d errors", errors);
    $finish;
  end
endmodule

The checks follow the style from self-checking testbenches: a reference model (the model array with head and tail indexes), !== comparisons, and a PASS or FAIL summary. Inputs change at the falling edge, away from the sampling edge (clocks and races). Note the subtle rule the model copies from the design: when the FIFO is exactly full, a simultaneous read and write does not accept the write, because full is evaluated before the read frees a slot (and likewise a read from an empty FIFO is refused even if a write happens in the same cycle). That is why the model uses count_before for both decisions. Write this rule in your specification; a design that accepts the write in that case is also valid, but then the model must change with it.

How deep must the FIFO be?

If a producer writes in bursts and a consumer drains at a steady rate, the FIFO must hold the backlog at the worst moment. For a burst of B words written at one word per cycle while the consumer reads r words per cycle (0 < r < 1), the maximum occupancy is about B * (1 - r). Add margin for latency in the flow control path (the producer needs time to see full and stop, called the almost-full threshold).

The second stand-in simulates a burst and reports the peak occupancy for different read rates, so you can choose a depth:

C Stand-in: peak occupancy for a write burst

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

When the consumer is as fast as the producer the FIFO barely fills; when it is a quarter as fast, almost the whole burst must be stored. That arithmetic, done before writing any RTL, is how real depth decisions are made.

Extensions

  1. Add almost_full and almost_empty flags with programmable thresholds.
  2. Add count and overflow/underflow error outputs.
  3. Make the read data combinational ("first word fall through") and compare its timing.
  4. Turn it into an asynchronous FIFO with Gray-coded pointers crossing two synchronizers (clock domain crossing).
  5. Write assertions: no write when full changes the pointer, full and empty are never both true (assertions).

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why do FIFO pointers have one extra bit?

    Both full and empty have equal address bits; the extra MSB shows whether the writer is a full lap ahead.
  2. 2. A 16-deep FIFO has 5-bit pointers. wr_ptr = 10110 and rd_ptr = 00110. What is the state?

    The lower four bits are equal and the MSBs differ, so the writer is exactly one lap (16 words) ahead: full.
  3. 3. What should the FIFO do when wr_en is high while full?

    Writing when full must not corrupt stored data; the safe behaviour is to ignore the write and optionally raise an error flag.
  4. 4. Which test scenario is most likely to find FIFO bugs?

    Corner cases are at the boundaries: full, empty and simultaneous operations near them.

Summary

  • A synchronous FIFO is a circular buffer with read and write pointers; one extra pointer bit distinguishes full from empty.
  • Registered reads let tools map the memory to block RAM; ignore writes when full and reads when empty.
  • Verify with a reference queue, random traffic that reaches full and empty, and clear specification of simultaneous operations.
  • Choose the depth from the burst size, the rate difference and the flow-control latency.

Next: Practice: Verilog Exercises