The synchronous FIFO: pointers, full, empty, the extra bit

A memory with two pointers

A FIFO (first in, first out) is a memory (R5.1) with two pointers. A write goes to mem[wptr] and moves wptr on; a read comes from mem[rptr] and moves rptr on. The words held are the difference, wptr - rptr.

With 2-bit pointers on a 4-deep FIFO, the difference can only be 0 to 3. Four words wrap it back to 0. That is the hook: four slots need five states, empty plus one to four words.

The extra bit, and the count register

The classic cure adds one bit to each pointer. The low bits still address the memory, and the top bit flips each time a pointer wraps. Empty is equal pointers. Full is the same address with a different top bit: the writer is exactly one lap ahead.

logic [AW:0] used;
assign used  = wptr_q - rptr_q;
assign empty = (used == 0);
assign full  = (used == (AW+1)'(DEPTH));

assign empty = (wptr_q == rptr_q);
assign full  = (wptr_q[AW] != rptr_q[AW]) &&
               (wptr_q[AW-1:0] == rptr_q[AW-1:0]);

The other cure is a count register: pointers as wide as the address, plus a register of AW + 1 bits. It adds one per accepted write and subtracts one per accepted read. It holds the occupancy outright and allows any DEPTH, but it is one more register to keep right. Measured at 16 x 8: 451 cells, 150 flops, 13 levels of logic.

The rules the brief states

1. A push when full is refused

   The write pointer does not move and no word is written. The producer must hold its word or lose it.

2. A pop when empty is refused

   The read pointer does not move and read_valid stays 0 after the edge.

3. A push and a pop together are both honoured

   Both pointers move, so the count stays. At full only the pop is accepted, and at empty only the push, because both decisions use the flags from before the edge.

4. Reset clears the pointers, not the memory

   Equal pointers make the FIFO empty, and a word is never read before it is written. Clearing 128 data flops would add a reset to each for no change in behaviour.

This FIFO answers an accepted read one edge later, with read_valid beside the word. Another style shows the head word on read_data while the FIFO is not empty, before any read: first-word fall-through. It saves a cycle and puts the memory's read mux on the output path.

The lab: add the extra bit

Run the lab. Each line shows the offers (w, r), both pointers in binary and the flags after the edge. The shipped design says empty at edge 5 and loses four words. Press Lint: it reports that used gives 4 bits where the comparison expects 5.

Fix it by giving both pointers and used one more bit: [AW:0] for [AW-1:0]. Run again; the reads return all four words in order. Synthesize both: the shipped design is 431 cells, 145 flops and 8 levels of logic; the fix is 453 cells, 147 flops and 12 levels. The two new flops are the wrap bits.

Then replace the flags with the wrap-bit version of the compare and synthesize: 413 cells and 7 levels, still 147 flops. Of these, 128 hold data, 10 are pointers, 1 is read_valid and 8 are read_data.

Try it

After four pushes both pointers are 00 and empty is 1, so the fifth push is taken and overwrites slot 00. One read returns 0xa4; the next three are refused as empty. The last lines push 0xb0, push 0xb1 while popping 0xb0, then pop 0xb1.

With the extra bit, full is 1 at edges 5 and 6, and the fifth push is refused. The reads at edges 7 to 10 return 0xa0, 0xa1, 0xa2 and 0xa3. The pointers end at 110: the write pointer has passed the wrap once.

`timescale 1ns/1ps
module tb;
  logic clk = 0;
  always #5 clk = ~clk;                   // rising edges at 5, 15, 25, ...
  logic rst_n = 1;                        // falls at 1 ns: a real edge, so an asynchronous reset acts before any clock
  int edge_n = -1;
  always @(posedge clk) edge_n = edge_n + 1;
  logic       write_en = 0, read_en = 0;
  logic [7:0] write_data = 0, read_data;
  logic       read_valid, full, empty;
  bit show = 0;
  // One cycle of offers: w writes d, r reads. The line after the edge shows what the FIFO did.
  task automatic cycle(input bit w, input bit r, input logic [7:0] d = 0);
    write_en = w; read_en = r; write_data = d; tick(); write_en = 0; read_en = 0;
  endtask
  sync_fifo #(.DEPTH(4)) dut (.clk(clk), .rst_n(rst_n), .write_en(write_en), .write_data(write_data),
                .read_en(read_en), .read_data(read_data), .read_valid(read_valid), .full(full), .empty(empty));
  // Advance to the next rising edge, wait for the design to settle, then print one line.
  task automatic tick();
    @(posedge clk); #1;
    if (show) begin
      $write("e%0d %s%s wptr=%b rptr=%b full=%b empty=%b", edge_n, write_en ? "w" : "-", read_en ? "r" : "-",
             dut.wptr_q, dut.rptr_q, full, empty);
      if (read_valid) $write(" read 0x%h", read_data);
      $display("");
    end
  endtask
  initial begin
    #1 rst_n = 0; tick(); tick(); rst_n = 1;   // asserted at 1 ns, edges 0 and 1 in reset, released 1 ns after edge 1
    show = 1;
    cycle(1, 0, 8'ha0); cycle(1, 0, 8'ha1); cycle(1, 0, 8'ha2); cycle(1, 0, 8'ha3);   // fill: four words
    cycle(1, 0, 8'ha4);                                                               // a fifth push
    repeat (4) cycle(0, 1);                                                           // drain
    cycle(1, 0, 8'hb0);
    cycle(1, 1, 8'hb1);                                                               // push and pop together
    cycle(0, 1);
    cycle(0, 0);
    $finish(0);                             // quiet: no "$finish called" line
  end
endmodule

Check yourself

// sync_fifo: a synchronous FIFO of DEPTH words (a power of two) of WIDTH bits.
// A write is accepted at an edge where write_en is 1 and the FIFO is not full; a read where
// read_en is 1 and it is not empty. Both decisions use the flags from before the edge. An
// accepted read returns its word in read_data after that edge, with read_valid 1 for one cycle.
module sync_fifo #(parameter int DEPTH = 16, parameter int WIDTH = 8) (
  input  logic             clk,
  input  logic             rst_n,         // asynchronous, active-low
  input  logic             write_en,
  input  logic [WIDTH-1:0] write_data,
  input  logic             read_en,
  output logic [WIDTH-1:0] read_data,
  output logic             read_valid,
  output logic             full,
  output logic             empty
);
  localparam int AW = $clog2(DEPTH);      // address bits: 4 for 16 words

  logic [WIDTH-1:0] mem [DEPTH];          // the storage (R5.1): no reset
  logic [AW:0]      wptr_q, rptr_q;       // the next slot to write, the next slot to read
  logic [AW:0]      used;                 // words held: the pointer difference

  assign used  = wptr_q - rptr_q;
  assign empty = (used == 0);
  assign full  = (used == (AW+1)'(DEPTH));   // DEPTH words: AW+1 bits

  wire take_w = write_en && !full;
  wire take_r = read_en && !empty;

  always_ff @(posedge clk)
    if (take_w) mem[wptr_q[AW-1:0]] <= write_data;

  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n) begin
      wptr_q <= '0; rptr_q <= '0; read_valid <= 1'b0; read_data <= '0;
    end else begin
      if (take_w) wptr_q <= wptr_q + 1'b1;
      if (take_r) begin
        rptr_q    <= rptr_q + 1'b1;
        read_data <= mem[rptr_q[AW-1:0]];
      end
      read_valid <= take_r;
    end
endmodule

module tb;
  logic clk = 0, rst_n = 1, write_en = 0, read_en = 0;
  logic [7:0] write_data = 0, read_data;
  logic read_valid, full, empty;
  sync_fifo #(.DEPTH(8)) dut (.*);
  task automatic cycle(input bit w, input bit r);
    write_en = w; read_en = r; write_data = write_data + 8'd1;
    #1 clk = 1; #1 clk = 0;
  endtask
  initial begin
    #1 rst_n = 0; #1 rst_n = 1;
    repeat (5) cycle(1, 0);
    repeat (2) cycle(0, 1);
    cycle(1, 1);
    $display("used=%0d", dut.used);
    $finish(0);
  end
endmodule

(wptr_q ^ rptr_q) == {1'b1, {AW{1'b0}}}

(AW+1)'(wptr_q - rptr_q) == (AW+1)'(DEPTH)

(wptr_q[AW] != rptr_q[AW]) && (wptr_q[AW-1:0] == rptr_q[AW-1:0])

(wptr_q == rptr_q)