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.
count and full show what the edge before left.- Cycle 0
The FIFO is empty. The writer pushes a1.
- Cycle 2
Two words are held, and the third push, of c3, is taken.
- Cycle 3
countis 3 andfullis already 1. The writer pushes d4, and the FIFO refuses it. One slot is still free. - 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.
push, pop and wdata are the offers of the cycle. count, full, empty and rdata show the state before that edge.- I/O
- Storage
A token on wdata is a push that the FIFO takes. A token on rdata is a pop that it takes.
- Cycle 0
The FIFO is empty. The writer pushes a1, and the edge at the end of this cycle stores it.
- Cycle 3
Three words are held. The fourth push, of d4, fills the last slot.
- Cycle 4
fullis 1. The writer pushes e5 anyway. The FIFO refuses the push, and e5 is never stored. - Cycle 5
The reader pops.
rdatashows a1, the oldest word, and the edge removes it. - Cycle 6
A push and a pop in one cycle. The word b2 leaves and f6 enters.
countstays at 3. - Cycle 7
The reader keeps popping: c3 leaves now, then d4, then f6. The order is the order of arrival.
- Cycle 10
emptyis 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.
- Storage
- Control
- After reset
Both pointers are at slot 0 and the FIFO is empty.
- Three pushes
Each push writes the slot under
wptrand moveswptrone slot on. After three pushes it is at slot 3.Follow the calls, values and waits
- data wptr: Slot 0 → Slot 1
- data wptr: Slot 1 → Slot 2
- data wptr: Slot 2 → Slot 3
- The fourth push wraps
The push writes slot 3. Then
wptrreturns to slot 0. Both pointers are at slot 0 again, and now the FIFO is full.Follow the calls, values and waits
- data wptr: Slot 3 → Slot 0
- Two pops
Each pop reads the slot under
rptrand movesrptrone slot on. Slots 0 and 1 are free again, andwptrcan use them.Follow the calls, values and waits
- data rptr: Slot 0 → Slot 1
- 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.
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 taken | Pop taken | Count after the edge |
|---|---|---|
| no | no | the same |
| yes | no | one more |
| no | yes | one less |
| yes | yes | the 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.
| Use | What the FIFO does |
|---|---|
| Rate matching | The source sends a short burst. The FIFO holds the words until the slower reader takes them. |
| Pipeline stall | A later stage is busy for some cycles. The FIFO keeps the words that are already on their way. |
| Clock crossing | The 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
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.
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.
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.
Synthesize the design to measure its cells and inspect the mapped gates.
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 backOriginal 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
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.
assign empty = (wptr == rptr);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.
wire do_push = push;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.
wptr <= wptr + 3'd1;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.