Project: How Does a Synchronous FIFO Know When It Is Full?
By giving each pointer one more bit than it needs to address the memory. The read and write pointers both count from 0, and the FIFO is empty when they are equal. When the write pointer has gone all the way round and caught up with the read pointer, the address bits are equal again, but the extra top bit differs, because the writer has wrapped once more than the reader. That one bit is what tells full from empty.
What you'll learn
- Why equal addresses alone can't tell full from empty
- The extra-bit pointer scheme and the count it gives for free
- A complete synchronous FIFO in Verilog
- A self-checking testbench with a queue model and random traffic
Conventions and assumptions
One clock for both reading and writing (a synchronous FIFO; crossing clock domains needs an asynchronous FIFO with Gray-coded pointers). DEPTH is a power of 2. Read data appears on the clock after rd_en. Simulated in Icarus Verilog 12 and linted with Verilator 5.036 with -Wall, with no warnings.
Step 1: the full and empty problem
A 16-entry FIFO needs 4 address bits. Start with both pointers at 0: empty. Write 16 times and the write pointer wraps back to 0, equal to the read pointer again, but now the FIFO is full. With only 4 bits the two states look identical. Use 5-bit pointers and the write pointer reaches 16 (binary 10000) while the read pointer is 0 (00000): the low 4 bits match and the top bit differs, so full. The count is simply wr_ptr − rd_ptr in 5 bits.
| wr_ptr | rd_ptr | Low 4 bits equal? | Top bits | State |
|---|---|---|---|---|
| 00000 | 00000 | yes | same | empty |
| 10000 | 00000 | yes | differ | full, 16 entries |
| 00011 | 11110 | no | 5 entries (3 − 30 mod 32) | |
| 10100 | 00100 | yes | differ | full |
Step 2: the Verilog
// Synchronous FIFO: one clock for both sides. DEPTH must be a power of 2.
// The pointers carry one extra bit: equal pointers mean empty, and pointers
// that differ only in that top bit mean full.
module sync_fifo #(parameter WIDTH = 8, parameter DEPTH = 16, parameter AW = $clog2(DEPTH)) (
input wire clk,
input wire rst,
input wire wr_en,
input wire [WIDTH-1:0] wr_data,
input wire rd_en,
output reg [WIDTH-1:0] rd_data,
output wire full,
output wire empty,
output wire [AW:0] count
);
reg [WIDTH-1:0] mem [0:DEPTH-1];
reg [AW:0] wr_ptr, rd_ptr;
wire do_write = wr_en && !full; // writes when full are dropped
wire do_read = rd_en && !empty; // reads when empty are ignored
assign empty = (wr_ptr == rd_ptr);
assign full = (wr_ptr[AW] != rd_ptr[AW]) && (wr_ptr[AW-1:0] == rd_ptr[AW-1:0]);
assign count = wr_ptr - rd_ptr;
always @(posedge clk) begin
if (rst) begin
wr_ptr <= 0;
rd_ptr <= 0;
rd_data <= 0;
end else begin
if (do_write) begin
mem[wr_ptr[AW-1:0]] <= wr_data;
wr_ptr <= wr_ptr + 1'b1;
end
if (do_read) begin
rd_data <= mem[rd_ptr[AW-1:0]]; // data appears the clock after rd_en
rd_ptr <= rd_ptr + 1'b1;
end
end
end
endmodule
Writes when full and reads when empty are simply dropped, so the pointers never pass each other. A write is also dropped when the FIFO is full even if a read happens on the same clock; allowing that write is a small extension, at the cost of a longer path into the full logic.
Step 3: a testbench with a model
The testbench keeps its own circular queue. Before each clock it decides, exactly as the FIFO should, whether the write and read happen, updates the model, and remembers what the read should return. After the clock it checks the data, and before each clock it checks full, empty and count against the model's size. Directed tests fill past full and drain past empty; then 5,000 clocks of random pushes and pops exercise everything in between.
task drive(input w, input r, input [W-1:0] d);
reg do_w, do_r;
begin
@(negedge clk);
if (full !== (n == D) || empty !== (n == 0) || count !== n) begin errors = errors + 1; $display("flags: n %0d full %b empty %b count %0d", n, full, empty, count); end
wr_en = w; rd_en = r; wr_data = d;
do_w = w && (n < D); do_r = r && (n > 0);
if (w && !do_w) dropped = dropped + 1;
if (r && !do_r) ignored = ignored + 1;
if (do_r) begin expect_data = model[head]; expect_valid = 1; head = (head + 1) % D; reads = reads + 1; end
if (do_w) begin model[tail] = d; tail = (tail + 1) % D; writes = writes + 1; end
n = n + do_w - do_r;
step;
end
endtask
What the simulation shows
after filling: full 1, count 16, dropped 4
after draining: empty 1, count 0, ignored 2
2426 writes, 2419 reads, 55 dropped when full, 123 ignored when empty, 0 errors
PASS
Common mistakes
- Using address-width pointers, so full and empty can't be told apart.
- Letting a write through when full, which overwrites the oldest data.
- Forgetting that read data arrives a clock after rd_en, and checking it too early.
- Using this design between two clock domains. The pointers would be sampled mid-change; use an asynchronous FIFO with Gray-coded pointers.
Check your understanding
- Q1. How many pointer bits does a 64-entry FIFO need? Answer: 7: six for the address and one wrap bit.
- Q2. wr_ptr = 01000 and rd_ptr = 11000 in a 16-deep FIFO. Full or empty? Answer: full. The low bits match and the top bits differ.
- Q3. Why can't the count be computed from the address bits alone? Answer: when they are equal it can be 0 or 16; the extra bit resolves it.
Related
Sources
Last verified
Simulated in Icarus Verilog 12 and linted with Verilator 5.036 on 14 November 2026; the output above is copied from that run, and the pointer arithmetic is checked in the site's tests (lib/projectNumbers.test.js). The full files are in the site's repository under scripts/projects/fifo.