Implement the FIFO and its boundaries

Offers and accepted operations

The RTL starts from the two decisions of lesson 7.1. take_w is write_en && used < DEPTH and take_r is read_en && used > 0, where used is the number of stored items. Both are continuous assignments of the values before the edge.

Everything that changes state is gated by them: the memory write, both pointers and used. An offer that is refused, such as a write while full, must change nothing at all, or a later accepted operation lands in the wrong place.

Named wires also help when debugging. In a waveform, take_w and take_r show at a glance which offers the FIFO accepted, so you rarely have to work it out from used.

The flags come from the same used: full is used == DEPTH and empty is used == 0. Because acceptance and flags read one number, a testbench never sees the FIFO accept a write while full says it cannot.

One decision for the occupancy

At an edge that takes both a write and a read, used must stay the same. Writing that as two separate nonblocking assignments looks right but is wrong.

if (take_w) used <= used + 1;
if (take_r) used <= used - 1;

case ({take_w, take_r})
  2'b10:   used <= used + 1;
  2'b01:   used <= used - 1;
  default: used <= used;
endcase

Both nonblocking assignments in the left version are scheduled at the same edge, and the last one scheduled sets the final value (Module 6). The bug appears only when both operations happen together, which is why the test plan includes that case at every fill level.

A useful habit is to write the next value of every register as one expression or one case. Each combination of conditions then has exactly one result, and you can read it off the page.

A registered response

read_valid is assigned at every edge that is not a reset: read_valid <= take_r;. Writing it only inside if (take_r) would leave it stuck at 1 after the first read, because nothing would ever clear it.

read_data changes only when a read is accepted, and it takes the item at the read pointer. Between reads it keeps its last value, which the rules allow. Reset clears used, both pointers, read_valid and read_data in one step.

Suppose the FIFO answered within the same edge, through a path straight from the memory to read_data. The output could then change whenever the inputs changed, and every reader would have to allow for that. Registering it trades one cycle of delay for an output that holds still.

The memory itself has no reset. After a reset, the old items are still in it, but used is 0 and both pointers are back at slot 0, so nothing can read them before they are overwritten.

Wrap at the depth

The pointers walk around a ring of DEPTH slots. Each one moves only on its own accepted operation and wraps with an explicit test: wp <= (wp == DEPTH - 1) ? 0 : wp + 1;.

A counter that simply overflows wraps at the next power of two. That happens to be correct when DEPTH is 4 and the counter is 2 bits wide, and wrong for every other depth. So test the FIFO at a depth such as 3, for at least two laps of the ring.

Here the pointers are int unsigned, far wider than they need to be, so they cannot overflow by accident. The explicit test against DEPTH - 1 is what keeps them in range, at every depth.

A first test at the pins

The example drives the pins directly from a task: it sets the requests on a falling edge, lets the FIFO act at the rising edge, and prints what it sees. It peeks at dut.used to show the occupancy, which a real testbench would not do. Lesson 7.3 replaces this task with a driver.

The task changes the inputs on the falling edge, half a cycle away from the rising edge where the FIFO reads them, so the test never races the design. Module 6's clocking blocks do the same job more neatly, which is why the driver in lesson 7.3 uses one.

Try it

Each line shows the requests of one edge and the outputs just after it. The write of 44 is refused at full. At full with both requests, 11 comes out and 55 is refused. With two stored, 22 comes out and 66 goes in, and 66 is the last item read, after the pointers have wrapped.

Reads at empty are refused and read_valid stays 0 while read_data keeps 66. Reset clears everything. Now change wp to wrap as (wp + 1) % 4 and predict which line changes first.

Check yourself

// The FIFO from lesson 7.2. Same ports and rules as hardware_fifo in the problem bank.
module fifo #(parameter int DEPTH = 4, parameter int WIDTH = 8) (
  input  bit             clk, reset, write_en, read_en,
  input  bit [WIDTH-1:0] write_data,
  output bit             full, empty, read_valid,
  output bit [WIDTH-1:0] read_data
);
  bit [WIDTH-1:0] mem [DEPTH];
  int unsigned    wp, rp, used;
  // Both decisions use the occupancy from before the edge.
  wire take_w = write_en && used < DEPTH;
  wire take_r = read_en  && used > 0;
  assign full  = (used == DEPTH);
  assign empty = (used == 0);
  always @(posedge clk) begin
    if (reset) begin
      used <= 0; wp <= 0; rp <= 0;
      read_valid <= 0; read_data <= '0;
    end else begin
      read_valid <= take_r;
      if (take_r) begin
        read_data <= mem[rp];
        rp <= (rp == DEPTH - 1) ? 0 : rp + 1;
      end
      if (take_w) begin
        mem[wp] <= write_data;
        wp <= (wp == DEPTH - 1) ? 0 : wp + 1;
      end
      case ({take_w, take_r})
        2'b10:   used <= used + 1;
        2'b01:   used <= used - 1;
        default: used <= used;
      endcase
    end
  end
endmodule

module tb;
  bit clk, reset, write_en, read_en;
  bit [7:0] write_data;
  bit full, empty, read_valid;
  bit [7:0] read_data;
  string seen = "";
  fifo #(.DEPTH(2)) dut (.*);
  always #5 clk = ~clk;
  task automatic cycle(bit w, bit r, bit [7:0] d = 0, bit rst = 0);
    @(negedge clk);
    write_en = w; read_en = r; write_data = d; reset = rst;
    @(posedge clk); #1;
    if (read_valid) seen = {seen, $sformatf("%h ", read_data)};
  endtask
  initial begin
    cycle(0, 0, 0, 1);
    cycle(1, 0, 8'h11);
    cycle(1, 0, 8'h22);
    cycle(1, 1, 8'h33);
    cycle(0, 1);
    cycle(0, 1);
    $display("%svalid=%0d", seen, read_valid);
    $finish;
  end
endmodule

wp <= (wp == DEPTH - 1) ? 0 : wp + 1;

wp <= 2'((wp + 1) % DEPTH);

if (wp == DEPTH - 1) wp <= 0;
else wp <= wp + 1;

wp <= wp + 1;

Practice

• The read that was valid on an empty FIFO Fix · Easy
• Arbitrary-depth FIFO with a fill level Implement · Medium