A First FIFO

Explain first-in first-out storage, and build a small FIFO from two pointers and a word counter.

You Will Be Able To

  • Explain how a write pointer and a read pointer move around the storage.
  • Derive the full and empty flags from a word counter.
  • Predict the count after a sequence of pushes and pops.
  • Find and fix a full flag that is wrong by one word.
Lesson
G8.2
Time
25 min
Runs on
Your browser
Check
4 questions

A receiver stored its bytes in a four-word FIFO. In a burst of four bytes, the fourth one never came out. The full flag rose after three words, and the FIFO refused the fourth. One wrong constant cost one word in every burst.

Four Pushes into a FIFO Whose Full Flag Is EarlyEach cycle ends at a rising clock edge. count and full show what the edge before left.
01234clkpushwdataa1b2c3d4e5count0123fullfull at 3 words: d4 is refused
Scroll horizontally ↔
  1. Cycle 0

    The FIFO is empty. The writer pushes a1.

  2. Cycle 2

    Two words are held, and the third push, of c3, is taken.

  3. Cycle 3

    count is 3 and full is already 1. The writer pushes d4, and the FIFO refuses it. One slot is still free.

  4. Cycle 4

    The count stays at 3. The word d4 is lost.

Measured on Icarus Verilog: the example of this lesson as it ships, edges 1 to 5.

First in, First Out

A FIFO is a small memory that returns words in the order they arrived. FIFO stands for first in, first out. A push adds a word at the back. A pop removes the oldest word from the front.

The writer and the reader do not share an address. Each side has two signals. The writer has push and looks at full. The reader has pop and looks at empty.

Five Words Go Through a Four-Word FIFOEach cycle ends at a rising edge. push, pop and wdata are the offers of the cycle. count, full, empty and rdata show the state before that edge.
  • I/O
  • Storage
pushwdatafullrdataemptypopWriterpushes wordsfifo4four slotsReaderpops words
push→ fifo4wdata→ fifo4full→ Writerrdata→ Readerempty→ Readerpop→ fifo4Writerpushes wordsfifo4four slotsReaderpops words

A token on wdata is a push that the FIFO takes. A token on rdata is a pop that it takes.

01234567891011clkpushwdataa1b2c3d4e5f6fullpopemptyrdataxa1b2c3d4f6xcount012343210
Scroll horizontally ↔
  1. Cycle 0

    The FIFO is empty. The writer pushes a1, and the edge at the end of this cycle stores it.

  2. Cycle 3

    Three words are held. The fourth push, of d4, fills the last slot.

  3. Cycle 4

    full is 1. The writer pushes e5 anyway. The FIFO refuses the push, and e5 is never stored.

  4. Cycle 5

    The reader pops. rdata shows a1, the oldest word, and the edge removes it.

  5. Cycle 6

    A push and a pop in one cycle. The word b2 leaves and f6 enters. count stays at 3.

  6. Cycle 7

    The reader keeps popping: c3 leaves now, then d4, then f6. The order is the order of arrival.

  7. Cycle 10

    empty is 1. The reader pops once more. The FIFO refuses the pop and nothing changes.

Measured on Icarus Verilog: the example with its full flag fixed, edges 1 to 11.

A push while the FIFO is full is an overflow. A pop while it is empty is an underflow. This FIFO refuses both, so its content stays correct. The refused word is still lost, and the writer must look at full before it pushes.

Two Pointers Around a Ring

Words in a FIFO do not move. The storage is a small memory, and two pointers move over it. The write pointer wptr is the slot of the next push. The read pointer rptr is the slot of the next pop.

Four Slots in a RingArrows show where a pointer goes when it adds 1. After slot 3 it returns to slot 0.
  • Storage
  • Control
CallValueReturnWaiting
Four slots in a ringArrows show where a pointer goes when it adds 1. After slot 3 it returns to slot 0. storage Slot 0 mem[0] storage Slot 1 mem[1] storage Slot 2 mem[2] storage Slot 3 mem[3] +1+1+1wrap
  1. storage Slot 0mem[0]
    • +1 → Slot 1
  2. storage Slot 1mem[1]
    • +1 → Slot 2
  3. storage Slot 2mem[2]
    • +1 → Slot 3
  4. storage Slot 3mem[3]
    • wrap → Slot 0
  1. After reset

    Both pointers are at slot 0 and the FIFO is empty.

  2. Three pushes

    Each push writes the slot under wptr and moves wptr one slot on. After three pushes it is at slot 3.

    Follow the calls, values and waits
    1. data wptr: Slot 0 → Slot 1
    2. data wptr: Slot 1 → Slot 2
    3. data wptr: Slot 2 → Slot 3
  3. The fourth push wraps

    The push writes slot 3. Then wptr returns to slot 0. Both pointers are at slot 0 again, and now the FIFO is full.

    Follow the calls, values and waits
    1. data wptr: Slot 3 → Slot 0
  4. Two pops

    Each pop reads the slot under rptr and moves rptr one slot on. Slots 0 and 1 are free again, and wptr can use them.

    Follow the calls, values and waits
    1. data rptr: Slot 0 → Slot 1
    2. data rptr: Slot 1 → Slot 2
Read the diagram as text
  • Slot 0: mem[0]
  • Slot 1: mem[1]
  • Slot 2: mem[2]
  • Slot 3: mem[3]
  • Slot 0 → Slot 1: +1
  • Slot 1 → Slot 2: +1
  • Slot 2 → Slot 3: +1
  • Slot 3 → Slot 0: wrap

The read pointer follows the write pointer around the ring. Old slots are used again.

Going from the last slot back to slot 0 is the wrap. With four slots a 2-bit pointer wraps with no extra code: 3 plus 1 is 0 in two bits.

A push writes and moves wptr. A pop only moves rptr: the oldest word is always mem[rptr].
if (do_push) begin
  mem[wptr] <= wdata;
  wptr      <= wptr + 2'd1;   // 2 bits: slot 3 wraps to slot 0
end
if (do_pop) rptr <= rptr + 2'd1;

Full and Empty Need a Count

After reset both pointers are at slot 0, and the FIFO is empty. After four pushes both pointers are at slot 0 again, and the FIFO is full. Equal pointers mean two different things.

A word counter removes the doubt. count is the number of words held. The two flags come from it.

Flags from the pointers

assign empty = (wptr == rptr);
assign full  = (count == 3'd4);

Icarus: after four pushes the line shows full=1 empty=1. No pop is ever taken: 0 of 5 words came back.

Flags from the count

assign empty = (count == 3'd0);
assign full  = (count == 3'd4);

Icarus: after four pushes the line shows full=1 empty=0. All 5 words came back, in order.

Each offer is decided on the flags before the edge. A push is taken when full is 0. A pop is taken when empty is 0.

Push takenPop takenCount after the edge
nonothe same
yesnoone more
noyesone less
yesyesthe same: one word in, one word out

The count moves only when one of the two happens alone.

Where FIFOs Are Used

A FIFO sits between a block that produces words and a block that uses them. The two blocks do not have to work at the same moments.

UseWhat the FIFO does
Rate matchingThe source sends a short burst. The FIFO holds the words until the slower reader takes them.
Pipeline stallA later stage is busy for some cycles. The FIFO keeps the words that are already on their way.
Clock crossingThe writer and the reader use different clocks. This needs an asynchronous FIFO, a harder design.

This lesson builds a synchronous FIFO: both sides use one clock.

A FIFO only moves the problem in time. If the writer is faster than the reader for long enough, any depth fills up. The depth must cover the longest burst.

The RTL Design track goes further in lesson R5.2: flags from the pointers alone, with one extra pointer bit.

Asked in interviews
  1. How do you tell a full FIFO from an empty one?

    The pointers are equal in both cases, so they are not enough. One way is a word counter: empty is count 0 and full is count equal to the depth. The other way is one extra bit on each pointer, which records the wrap.

  2. What happens when a push and a pop arrive in the same cycle?

    Each one is decided on the flags before the edge. In the middle both are taken, and the count stays the same. In this design a full FIFO takes only the pop, and an empty FIFO takes only the push.

  3. How deep must a FIFO be?

    Deep enough for the longest burst. Work out how many words the writer sends in the burst and how many the reader removes in the same time. The difference must fit in the FIFO.

Try It

Each line shows the offers of one edge and the state after it. At edge 3 the line shows count=3 full=1. The FIFO has four slots, but the flag rises at three words.

Edge 4 pushes d4 and the FIFO refuses it. The last lines show the result: words out: a1 b2 c3 f6 and 4 of 5 words came back.

Fix the line that assigns full: compare count with 3'd4. Run again. Edge 4 now shows count=4 full=1, edge 5 refuses e5 as it should, and the last line is 5 of 5 words came back.

Press Synthesize: Yosys builds 97 cells with 41 flip-flops. The storage needs 32 of them. The pointers and the count use the others.

RTLIcarus Verilog · in your browser · Lint: Verilator service · Synthesize: Yosys service
Edit the design, then Run, Lint or Synthesize
Expected: e0 rst=1 push=0 pop=0 wdata=00 count=0 full=0 empty=1 rdata=-- e1 rst=0 push=1 pop=0 wdata=a1 count=1 full=0 empty=0 rdata=a1 e2 rst=0 push=1 pop=0 wdata=b2 count=2 full=0 empty=0 rdata=a1 e3 rst=0 push=1 pop=0 wdata=c3 count=3 full=1 empty=0 rdata=a1 e4 rst=0 push=1 pop=0 wdata=d4 count=3 full=1 empty=0 rdata=a1 e5 rst=0 push=1 pop=0 wdata=e5 count=3 full=1 empty=0 rdata=a1 e6 rst=0 push=0 pop=1 wdata=e5 count=2 full=0 empty=0 rdata=b2 e7 rst=0 push=1 pop=1 wdata=f6 count=2 full=0 empty=0 rdata=c3 e8 rst=0 push=0 pop=1 wdata=f6 count=1 full=0 empty=0 rdata=f6 e9 rst=0 push=0 pop=1 wdata=f6 count=0 full=0 empty=1 rdata=-- e10 rst=0 push=0 pop=1 wdata=f6 count=0 full=0 empty=1 rdata=-- e11 rst=0 push=0 pop=1 wdata=f6 count=0 full=0 empty=1 rdata=-- words out: a1 b2 c3 f6 4 of 5 words came back

Original design · 97 cells · 41 flip-flops · 0 latches · 7 logic levels. Synthesis uses Yosys; counts depend on the toolchain.

Read included file: tb.sv
// tb.sv: the bench (read-only). It sends the words a1, b2, c3, d4 and f6 through the FIFO and prints one line per edge.
`timescale 1ns/1ps
module tb;
  logic       clk = 0;
  logic       rst = 0, push = 0, pop = 0;
  logic [7:0] wdata = 8'h00;
  logic [7:0] rdata;
  logic       full, empty;
  logic [2:0] count;
  int         edge_n = -1;
  int         got = 0;                         // words that came out
  string      out = "";

  always #5 clk = ~clk;                       // a 10 ns clock
  always @(posedge clk) edge_n = edge_n + 1;   // counts the rising edges from 0

  fifo4 dut (.clk(clk), .rst(rst), .push(push), .wdata(wdata), .pop(pop),
             .rdata(rdata), .full(full), .empty(empty), .count(count));

  // A word that leaves: the oldest word, at an edge where the pop is taken.
  always @(posedge clk)
    if (!rst && pop && !empty) begin
      got = got + 1;
      out = {out, $sformatf(" %h", rdata)};
    end

  // Drive one cycle, wait for the edge, let the FIFO update, then print one line.
  task automatic tick(input logic do_rst, input logic do_push, input logic do_pop, input logic [7:0] word);
    rst = do_rst; push = do_push; pop = do_pop; wdata = word;
    @(posedge clk); #1;
    if (empty) $display("e%0d rst=%b push=%b pop=%b wdata=%h count=%0d full=%b empty=%b rdata=--", edge_n, rst, push, pop, wdata, count, full, empty);
    else       $display("e%0d rst=%b push=%b pop=%b wdata=%h count=%0d full=%b empty=%b rdata=%h", edge_n, rst, push, pop, wdata, count, full, empty, rdata);
  endtask

  initial begin
    tick(1, 0, 0, 8'h00);     // edge 0: reset
    tick(0, 1, 0, 8'ha1);     // edges 1 to 4: four pushes fill the four slots
    tick(0, 1, 0, 8'hb2);
    tick(0, 1, 0, 8'hc3);
    tick(0, 1, 0, 8'hd4);
    tick(0, 1, 0, 8'he5);     // edge 5: a push while full: the FIFO must refuse e5
    tick(0, 0, 1, 8'he5);     // edge 6: one pop
    tick(0, 1, 1, 8'hf6);     // edge 7: a push and a pop together
    tick(0, 0, 1, 8'hf6);     // edges 8 to 10: three pops
    tick(0, 0, 1, 8'hf6);
    tick(0, 0, 1, 8'hf6);
    tick(0, 0, 1, 8'hf6);     // edge 11: a pop while empty: nothing comes out
    $display("words out:%s", out);
    $display("%0d of 5 words came back", got);
    $finish(0);
  end
endmodule

Check Yourself

Predict the outputThis program holds only the counter of a four-word FIFO. Predict the exact line it prints.
module tb;
  logic       clk = 0, push = 0, pop = 0;
  logic [2:0] count = 3'd0;
  wire        full    = (count == 3'd4);
  wire        empty   = (count == 3'd0);
  wire        do_push = push && !full;
  wire        do_pop  = pop  && !empty;
  always_ff @(posedge clk) begin
    if (do_push && !do_pop) count <= count + 3'd1;
    if (do_pop && !do_push) count <= count - 3'd1;
  end
  task automatic step(input logic p, input logic q);
    push = p; pop = q;
    #1 clk = 1; #1 clk = 0;
  endtask
  initial begin
    step(0, 1);                    // a pop
    repeat (5) step(1, 0);         // five pushes
    step(1, 1);                    // a push and a pop together
    step(1, 1);                    // and once more
    $display("count=%0d", count);
  end
endmodule
Spot the bugEach option updates the word counter from do_push and do_pop, the push and the pop that are taken. The bench applies both in one cycle and expects the count to stay. Which option fails?
ConceptThe FIFO of this lesson holds four words, so full is 1. In one cycle push and pop are both 1. What does it do at the edge?
ConceptA four-slot FIFO comes out of reset. It takes four pushes and then one pop. Where are the two pointers?

Common Mistakes

Wrong Take empty from the pointers: empty when wptr == rptr.

Equal pointers mean 0 words or 4 words: on Icarus this FIFO shows full=1 empty=1 and returns no word.

Fix Keep a count of the words held. Empty is count 0 and full is count equal to the depth.

Before
assign empty = (wptr == rptr);
After
assign empty = (count == 3'd0);

Wrong Store the word on every push, with no look at full.

The fifth word lands on the oldest one: on Icarus the bench then reads e5 where a1 was stored.

Fix Write the storage and move the pointer only when the push is taken: push && !full.

Before
wire do_push = push;
After
wire do_push = push && !full;

Wrong Use a 3-bit pointer for six slots and let it count freely.

The pointer goes on to 6 and 7, which are not slots: after seven pushes Icarus shows wptr=7.

Fix Return the pointer to 0 after the last slot, or choose a depth that is a power of two.

Before
wptr <= wptr + 3'd1;
After
wptr <= (wptr == 3'd5) ? 3'd0 : wptr + 3'd1;

Wrong Make the count register just wide enough for the pointer: 2 bits for 4 slots.

A 2-bit count holds 0 to 3: after four pushes Icarus shows count=0, and the full FIFO looks empty.

Fix Give the count one more value than the depth: 3 bits for 0 to 4.

Remember

  • A FIFO returns words in the order they arrived: push at the back, pop at the front.
  • Two pointers move around the storage and wrap from the last slot to slot 0.
  • Equal pointers mean empty or full. A word counter tells the two apart.
  • Decide each push and pop on the flags before the edge: push && !full, pop && !empty.
  • A FIFO matches rates for a burst. Its depth must cover the longest burst.

Practice

Report a problem with this page