01signal.com

Implementation of single clock FIFOs in Verilog

Scope

This page, which is the third of four in a series about FIFOs, shows an implementation in Verilog of a baseline single clock FIFO. This can be useful for writing portable code, but the main point of this page is to reiterate how a FIFO works. So I'll show an implementation of a "standard FIFO" as well as a FWFT FIFO. But first we need a dual port RAM that both FIFOs will use.

The dual port RAM

This is the Verilog module that implements the RAM by virtue of inference. It's quite likely that any synthesizer will get this right, but it's possible that it will generate the undesired sort of RAM (block RAM vs. distributed RAM), so it may be necessary to add synthesizer directives. Or maybe use an IP that is supplied by the FPGA vendor for a dual port RAM, if that works best.

So here's the module:

module dualport_ram #(parameter depth = 64,
                      log2_depth = 6,
                      width = 8
                     )
   (
    input                    clk,
    input [(log2_depth-1):0] wr_addr,
    input [(log2_depth-1):0] rd_addr,
    output reg [(width-1):0] rd_data,
    input [(width-1):0]      wr_data,
    input                    rd_en,
    input                    wr_en
    );

   reg [(width-1):0] inferred_ram[0:(depth-1)];

   always @(posedge clk)
     begin
        if (wr_en)
          inferred_ram[wr_addr] <= wr_data;

        if (rd_en)
          rd_data <= inferred_ram[rd_addr];
     end
endmodule

The "standard FIFO"

And now we're ready to look at the module that implements a "standard FIFO" (i.e. not a FWFT FIFO):

module fifo
  #(parameter depth = 64, // Must equal 2^log2_depth exactly
    log2_depth = 6,
    width = 8
    )
   (
    input  clk,
    input  rst,

    input  wr_en,
    input [(width-1):0] din,

    input  rd_en,
    output [(width-1):0] dout,

    output reg full,
    output reg empty
    );

   reg [log2_depth:0]         next_words_in_ram; // Combinatorial
   reg [log2_depth:0]         words_in_ram;
   reg [(log2_depth-1):0]     rd_addr;
   reg [(log2_depth-1):0]     wr_addr;
   wire                       fetch_data, commit_data;

   assign fetch_data = rd_en && !empty;
   assign commit_data = wr_en && !full;

   always @(*)
     if (commit_data && !fetch_data)
       next_words_in_ram <= words_in_ram + 1;
     else if (!commit_data && fetch_data)
       next_words_in_ram <= words_in_ram - 1;
     else
       next_words_in_ram <= words_in_ram;

   always @(posedge clk)
     begin
        words_in_ram <= next_words_in_ram;
        full <= (next_words_in_ram == depth);
        empty <= (next_words_in_ram == 0);

        if (fetch_data)
          rd_addr <= rd_addr + 1;

        if (commit_data)
          wr_addr <= wr_addr + 1;

        if (rst)
          begin
             empty <= 1;
             full <= 1;
             words_in_ram <= 0;
             rd_addr <= 0;
             wr_addr <= 0;
          end
     end

   dualport_ram
     #(.depth(depth), .log2_depth(log2_depth), .width(width)) dp_ins
       (.clk(clk), .wr_addr(wr_addr),
        .rd_addr(rd_addr),
        .wr_en(commit_data),
        .rd_en(fetch_data),
        .wr_data(din),
        .rd_data(dout)
        );
endmodule

The only important usage note is made in the comment at the top, regarding the "depth" and "log2_depth" parameters: depth must equal 2log2_depth.

The operation of this module is quite simple: @fetch_data is like @rd_en, but it takes @empty into account. @fetch_data is therefore a safe version of @rd_en, in the sense that it even if @rd_en and @empty are high at the same time (this is illegal), nothing bad happens, because @rd_en is ignored in that case.

@commit_data is the safe version of @wr_en in the same way, by taking @full into account.

The next value of @words_in_ram, @next_words_in_ram, is calculated as a combinatorial function, based upon @fetch_data and @commit_data (note the always @(*) statement). @next_words_in_ram is used to produce the values of several registers with this code snippet:

   always @(posedge clk)
     begin
        words_in_ram <= next_words_in_ram;
        full <= (next_words_in_ram == depth);
        empty <= (next_words_in_ram == 0);
[ ... ]

Note that @full and @empty are defined here.

What makes this FIFO so easy to implement, compared with a dual-clock FIFO, is the ability to define @words_in_ram like this, and use this same register on both sides of the FIFO.

Next on in the code, we have the update of @rd_addr and @wr_addr, and then the clause for @rst. Note that both @empty and @full change to high as a result of the reset, but @full will return to low when the reset is released.

A note about coding style: When @rst is high, the assignments in the if statement's begin-end clause override the assignments that were possibly made earlier, so @rst does indeed reset all registers to their initial values. This isn't the most common coding style, but it has clear advantages when not all registers are reset. This specific case doesn't demonstrate this advantage, but see this page.

Finally, there is an instantiation of the dual port RAM.

The FWFT FIFO

As shown on this page, it's quite easy to convert a "standard FIFO" into a FWFT FIFO. But its direct implementation allows discussing some interesting points, so here it is:

module fwft_fifo
  #(parameter depth = 64, // Must equal 2^log2_depth exactly
    log2_depth = 6,
    width = 8
    )
   (
    input  clk,
    input  rst,

    input  wr_en,
    input [(width-1):0] din,

    input  rd_en,
    output [(width-1):0] dout,

    output reg full,
    output reg empty
    );

   reg [log2_depth:0]         next_words_in_ram; // Combinatorial
   reg [log2_depth:0]         words_in_ram;
   reg [(log2_depth-1):0]     rd_addr;
   reg [(log2_depth-1):0]     wr_addr;
   reg                        has_more_words;
   wire                       fetch_data, commit_data;

   assign fetch_data = (rd_en || empty) && has_more_words;
   assign commit_data = wr_en && !full;

   always @(*)
     if (commit_data && !fetch_data)
       next_words_in_ram <= words_in_ram + 1;
     else if (!commit_data && fetch_data)
       next_words_in_ram <= words_in_ram - 1;
     else
       next_words_in_ram <= words_in_ram;

   always @(posedge clk)
     begin
        words_in_ram <= next_words_in_ram;
        full <= (next_words_in_ram == depth);
        has_more_words <= (next_words_in_ram != 0);

        if (fetch_data)
          rd_addr <= rd_addr + 1;

        if (commit_data)
          wr_addr <= wr_addr + 1;

        if (fetch_data)
          empty <= 0;
        else if (rd_en)
          empty <= 1;

        if (rst)
          begin
             empty <= 1;
             full <= 1;
             words_in_ram <= 0;
             has_more_words <= 0;
             rd_addr <= 0;
             wr_addr <= 0;
          end
     end

   dualport_ram
     #(.depth(depth), .log2_depth(log2_depth), .width(width)) dp_ins
       (.clk(clk), .wr_addr(wr_addr),
        .rd_addr(rd_addr),
        .wr_en(commit_data),
        .rd_en(fetch_data),
        .wr_data(din),
        .rd_data(dout)
        );
endmodule

First note that we have a new register, which is @has_more_words. Compare its definition with the "standard FIFO" above, and convince yourself that @has_more_words is the logical NOT of @empty.

Next, note that the definition for @fetch_data has changed. It's now safeguarded by @has_more_words instead (not surprisingly), so it says

assign fetch_data = (rd_en || empty) && has_more_words;

Recall from before that @empty means "@dout isn't valid" on an FWFT FIFO. So this assignment means that in addition to @rd_en, if the output isn't valid, and there is data in the memory array to read from, go ahead and do that. That's the falling through of the first word.

And finally, the logic for assigning @empty has changed to

   always @(posedge clk)
     if (fetch_data)
       empty <= 0;
     else if (rd_en)
       empty <= 1;

This says simply, that if a word is read from the memory array, @empty changes to low on the next clock cycle, because there's obviously new and valid data now. However if that doesn't happen, and @rd_en is enabled nevertheless, then the application logic has just taken the last word available, so change @empty to high. Note that if @rd_en is high and @fetch_data is low, @has_more_words is surely low (see the assignment for @fetch_data above). This is why this condition is equivalent to reading the last word in the FIFO.

This wraps up the third page in this series about FIFOs. The next page shows how to turn a "standard FIFO" into a FWFT FIFO and vice versa, as well as how to improve timing.

Copyright © 2021-2023. All rights reserved. (ba53f4ca)