10Memories and FIFOs

1. A memory is an array of registers

A register holds one value. A memory holds many values of the same width, picked by an address. In Verilog it is declared as an array of reg vectors: the range before the name is the width of one word, the range after it is the number of words.

Form

reg [word_msb:0] name [0:words-1];

reg [7:0] mem [0:3];        // four words of 8 bits
mem[2] <= 8'h5a;            // write word 2 at a clock edge
assign rdata = mem[raddr];  // read the word at raddr

The examples access this memory one word at a time, and a word that has never been written reads as x. Here a word is written with <= inside always @(posedge clock), so a write happens only at a rising edge.

2. Write at the edge, read in two ways

RegFile.v is a register file of four 8-bit words with one write port and one read address. The same address is read two ways:

// A 4 x 8 register file: one write port, one address read two ways.
module regfile (
  input            clock,
  input            we,
  input      [1:0] waddr,
  input      [7:0] wdata,
  input      [1:0] raddr,
  output     [7:0] rdata_async,
  output reg [7:0] rdata_sync
);
  reg [7:0] mem [0:3];

  // Writes happen only at a rising edge.
  always @(posedge clock) begin
    if (we) mem[waddr] <= wdata;
    // A registered read: the word at raddr is captured at the edge.
    rdata_sync <= mem[raddr];
  end

  // An asynchronous read: rdata_async follows raddr and mem at once.
  assign rdata_async = mem[raddr];
endmodule

The testbench changes inputs on falling edges and prints each cycle before the rising edge that ends it. So an RF line shows the inputs driven during that cycle and what the outputs show during it. The four cycles are:

Predict before you run. A write lands at the edge that ends its cycle. The asynchronous read shows the word at raddr now; the registered read shows what was at raddr one edge ago.

Check the result. The four RF lines are the first lines of the run below:

A registered read costs a cycle but gives a clean register output. Many FPGA block memories only offer a registered read; an asynchronous read is built from flip-flops or small distributed memory. Whichever you choose, the rest of the design has to expect the data in the right cycle.

3. A FIFO keeps words in arrival order

A FIFO (first in, first out) is a memory used as a queue: words leave in the order they arrived. Fifo.v stores up to DEPTH words of WIDTH bits. The rule for every rising edge:

full is count == DEPTH and empty is count == 0, both read from the count register, so they change only at rising edges. dout is an asynchronous read at rd_ptr: while the FIFO is not empty, it shows the oldest word, and a pop moves the pointer. While empty, dout is not valid.

// A synchronous FIFO of DEPTH words, each WIDTH bits wide.
module sync_fifo #(
  parameter WIDTH = 8,
  parameter DEPTH = 4
) (
  input              clock,
  input              reset,
  input              push,
  input  [WIDTH-1:0] din,
  input              pop,
  output [WIDTH-1:0] dout,
  output             full,
  output             empty,
  output reg   [4:0] count
);
  reg [WIDTH-1:0] mem [0:DEPTH-1];
  // The pointers wrap explicitly, so DEPTH need not be a power of two (up to 16).
  reg [3:0] wr_ptr, rd_ptr;

  // A push when full and a pop when empty are ignored.
  wire do_push = push && !full;
  wire do_pop  = pop  && !empty;

  always @(posedge clock) begin
    if (reset) begin
      wr_ptr <= 4'd0;
      rd_ptr <= 4'd0;
      count  <= 5'd0;
    end else begin
      if (do_push) begin
        mem[wr_ptr] <= din;
        wr_ptr <= (wr_ptr == DEPTH - 1) ? 4'd0 : wr_ptr + 4'd1;
      end
      if (do_pop)
        rd_ptr <= (rd_ptr == DEPTH - 1) ? 4'd0 : rd_ptr + 4'd1;
      // Both accepted at once: one word in, one word out, count unchanged.
      count <= count + do_push - do_pop;
    end
  end

  // While nonempty, the oldest word is visible at dout through an asynchronous read.
  assign dout  = mem[rd_ptr];
  assign full  = (count == DEPTH);
  assign empty = (count == 5'd0);
endmodule

Three details of the code:

• do_push and do_pop are the pushes and pops that are allowed. Everything that changes state uses them, so an ignored push cannot write and an ignored pop cannot move the pointer.
• count <= count + do_push - do_pop; covers all four combinations in one line.
• The pointers wrap with a comparison against DEPTH - 1, not by overflowing, so DEPTH may be any value up to 16, not only a power of two. WIDTH and DEPTH are parameters, set per instance as in Instances, hierarchy and parameters.

4. Predict and run the FIFO trace

Tb.v drives the register file first, then releases the FIFO's reset and counts its cycles from 0. The FIFO lines follow the same convention as the RF lines: inputs during the cycle, outputs before the edge that ends it.

module tb;
  reg        clock = 0;
  reg        we = 0, reset = 1, push = 0, pop = 0;
  reg  [1:0] waddr = 0, raddr = 0;
  reg  [7:0] wdata = 0, din = 0;
  wire [7:0] rdata_async, rdata_sync, dout;
  wire       full, empty;
  wire [4:0] count;
  integer    c = 0;

  regfile rf (.clock(clock), .we(we), .waddr(waddr), .wdata(wdata), .raddr(raddr),
              .rdata_async(rdata_async), .rdata_sync(rdata_sync));
  sync_fifo #(.WIDTH(8), .DEPTH(4)) fifo (.clock(clock), .reset(reset), .push(push),
              .din(din), .pop(pop), .dout(dout), .full(full), .empty(empty), .count(count));

  always #5 clock = ~clock;

  // Drive one cycle on the falling edge, then print what is visible during that cycle,
  // before the rising edge that ends it.
  task rf_cycle(input w, input [1:0] wa, input [7:0] wd, input [1:0] ra);
    begin
      @(negedge clock);
      we = w; waddr = wa; wdata = wd; raddr = ra;
      #1 $display("RF   c=%0d we=%b waddr=%0d wdata=%h raddr=%0d | async=%h sync=%h",
                  c, we, waddr, wdata, raddr, rdata_async, rdata_sync);
      c = c + 1;
    end
  endtask

  task fifo_cycle(input p, input [7:0] d, input q);
    begin
      @(negedge clock);
      push = p; din = d; pop = q;
      #1 $display("FIFO c=%0d push=%b din=%h pop=%b | count=%0d full=%b empty=%b dout=%h",
                  c, push, din, pop, count, full, empty, dout);
      c = c + 1;
    end
  endtask

  initial begin
    $dumpfile("dump.vcd");
    $dumpvars(0, tb);
    rf_cycle(1, 0, 8'h11, 0);
    rf_cycle(1, 1, 8'h22, 0);
    rf_cycle(0, 0, 8'h00, 1);
    rf_cycle(0, 0, 8'h00, 1);
    // The FIFO was held in reset so far: release it and count cycles from 0 again.
    @(negedge clock) reset = 0;
    c = 0;
    fifo_cycle(1, 8'ha1, 0);
    fifo_cycle(1, 8'ha2, 0);
    fifo_cycle(1, 8'ha3, 0);
    fifo_cycle(1, 8'ha4, 0);
    fifo_cycle(1, 8'ha5, 0);
    fifo_cycle(1, 8'ha6, 1);
    fifo_cycle(1, 8'hb1, 1);
    fifo_cycle(0, 8'h00, 1);
    fifo_cycle(0, 8'h00, 1);
    fifo_cycle(0, 8'h00, 1);
    fifo_cycle(0, 8'h00, 1);
    fifo_cycle(0, 8'h00, 0);
    $finish;
  end
endmodule

Predict before you run. Write count, full and empty for every cycle, then answer:

Check the result.

Open the waveform and compare fifo.count, fifo.full and fifo.empty: all three change only at rising edges, at the same edges.

5. Change one thing: a shallower FIFO

In Tb.v, change .DEPTH(4) to .DEPTH(2) and run again. Nothing else changes.

The trace now shows full=1 from c=2 to c=5, and dout shows a1, a2, b1 while popping. Because the flags compare with the parameter, no other line of Fifo.v had to change. Put DEPTH back to 4.

6. Practice: make a FIFO track how full it is

The checkpoint is the Practice problem fifo-flags. Its FIFO has the storage, the pointers and do_push/do_pop, but count never changes and full and empty are tied to 0, so its public trace shows pops from an empty FIFO and pushes that overwrite stored words. Predict the correct trace first, then write the count update and the two flags. The grader also runs other WIDTH and DEPTH values, so nothing may assume 4.

7. Summary

8. Check your understanding

1. A design reads a memory through a register and uses the data in the cycle it sets the address. What does it see?

   Show answer

   The word from the address of the previous cycle. A registered read captures the word at the edge that ends the address cycle, so the data is valid one cycle later; the design has to wait a cycle or use an asynchronous read.

2. Why can the FIFO not use full = (wr_ptr == rd_ptr)?

   Show answer

   The pointers are equal both when the FIFO is empty and when it is full: after DEPTH pushes the write pointer has wrapped around to the read pointer. Something else has to tell the two apart, here the count register; another common way is one extra bit on each pointer.