RTL Design Patterns · Chapter 7 · FIFO Design
Full & Empty Logic
The hardest part of a FIFO is one question. When the write pointer and the read pointer point at the same address, is the buffer empty or full? An empty FIFO has the pointers equal, and a full FIFO has the write pointer wrapped all the way around to catch the read pointer, so the two cases look identical from the addresses alone. Guess wrong and a write overwrites a word the reader never took, or the reader walks away from a word that was really there, silently losing or duplicating data under near-full traffic. The standard answer adds the missing bit of information: make both pointers one bit wider than the address and read that extra bit as a wrap lap counter. Empty is fully equal pointers, full is wrap bits differing while address bits match. This lesson proves the boundary and its alternatives, in SystemVerilog, Verilog, and VHDL.
Intermediate16 min readRTL Design PatternsFIFOFull Empty FlagsPointer WrapOff-By-OneCircular Buffer
Chapter 7 · Section 7.2 · FIFO Design
1. The Engineering Problem
In 7.1 you built the FIFO's skeleton: a dual-port memory mem, a write pointer wptr that advances every time wr_en pushes a word, a read pointer rptr that advances every time rd_en pops one, and both pointers wrapping the address range so the storage behaves as a circular buffer. The datapath is done. What 7.1 deliberately left open is the one thing that turns that circular buffer into a safe FIFO — the two status flags, full and empty, that tell the producer "stop, there is no room" and the consumer "stop, there is nothing to take." Get those two signals right and the FIFO is correct. Get either one wrong by a single count and the FIFO silently corrupts data.
Here is why it is genuinely hard, and not a matter of "just compare the pointers." Consider the two states that matter most. When the FIFO is empty, nothing has been written since the last read caught up, so wptr and rptr point at the same address — they are equal. Now fill the FIFO completely and it is full: the writer has pushed DEPTH words that the reader has not taken, which means wptr has advanced all the way around the buffer and come back to sit on top of rptr — so wptr and rptr are equal again. Empty and full both present the identical picture: wptr == rptr. If your flag logic looks only at the addresses, it literally cannot tell "there is nothing here" from "there is no room here." They are the same comparison and the opposite meaning.
This is not an academic edge case; it is the operating point of every FIFO under load. A FIFO that is doing its job — absorbing bursts, buffering a fast producer against a slow consumer — spends its time hovering near empty or near full, and it crosses those boundaries constantly. If full de-asserts one slot too late, a sustained burst writes into a location the reader has not yet emptied and overwrites an unread word — the data is gone and no error is raised. If empty asserts one slot too early, the reader stops one word short and never reads the last word — or worse, if it asserts one slot too late, the reader pops a stale, never-written location. Every one of these is an off-by-one on a flag, and every one of them is invisible in a lightly-loaded test and catastrophic in the field.
// From 7.1: a circular buffer. Pointers advance and wrap.
// wr_en pushes -> wptr advances; rd_en pops -> rptr advances.
// EMPTY: reader has caught up to writer -> pointers point at the same slot:
// wptr == rptr
// FULL: writer has wrapped all the way around and caught the reader ->
// wptr == rptr <-- THE SAME COMPARISON.
// So this is AMBIGUOUS and cannot be right for both:
// assign empty = (wptr == rptr);
// assign full = (wptr == rptr); // full and empty can never differ => broken
// The need: add ONE bit of information the equal-address case is missing, so
// "nothing here" and "no room here" become distinguishable. That is this page.2. Mental Model
3. Pattern Anatomy
The structure is the 7.1 circular buffer with pointers made one bit wider and two comparators bolted on. Everything hard is in how those two comparators read the extra bit.
The (AW+1)-bit pointer. For a FIFO of DEPTH = 2**AW entries, both wptr and rptr are AW+1 bits wide, not AW. Split each pointer into two fields: the address field is the low AW bits, wptr[AW-1:0], and it is what actually indexes the DEPTH-entry memory (mem[wptr[AW-1:0]]); the wrap bit is the single MSB, wptr[AW], which toggles every time the pointer rolls over the top of the address range. The wrap bit is never used to address memory — it exists only to distinguish laps. This is why DEPTH must be a power of two: only then does the address field wrap cleanly from its maximum back to zero at exactly the moment the wrap bit toggles, so "address rolled over" and "wrap bit flipped" are the same event. A non-power-of-two depth breaks that alignment and the MSB scheme silently mis-reports (see §6).
The empty condition — pointers fully equal. empty = (wptr == rptr), comparing all AW+1 bits. This is true exactly when the read pointer has caught the write pointer on the same lap: same seat, same lap, nothing between them. At reset both pointers are zero, so the FIFO powers up empty — correct by construction.
The full condition — same address, opposite wrap. full = (wptr[AW] != rptr[AW]) && (wptr[AW-1:0] == rptr[AW-1:0]). The address fields are equal (same seat) but the wrap bits differ (the writer is one lap ahead). That is precisely the state where the writer has advanced DEPTH positions past the reader without the reader moving — the buffer holds DEPTH words. Note the asymmetry that trips people up: empty compares the whole pointer; full compares only the address field and requires the wrap bits to be different. Comparing the full pointer for full (MSB included) would make full never assert; ignoring the wrap bit for empty would make empty and full collide again.
The (AW+1)-bit pointer — address field indexes memory, wrap bit counts laps
data flowThe boundary is worth walking once, because the whole flagship claim is that it has no off-by-one. Take DEPTH = 4, so AW = 2 and the pointers are 3 bits. Start empty: wptr = 000, rptr = 000 — fully equal, empty asserts, full cannot (wrap bits are equal). Push four words: wptr steps 001, 010, 011, 100. On the fourth write wptr = 100, rptr = 000: the address fields 00 == 00 are equal and the wrap bits 1 != 0 differ — full asserts on exactly the fourth (DEPTH-th) write, and not on the third (wptr = 011, address 11 != 00). Now drain: rptr steps 001, 010, 011, 100. On the fourth read rptr = 100 == wptr — fully equal, empty asserts on exactly the fourth read, the one that took the last word, and not on the third. And full and empty are mutually exclusive by construction: empty needs the wrap bits equal, full needs them different, so they can never both be true.
The second visual is the one that makes the ambiguity — and its resolution — tangible: the equal-address state, resolved by the wrap bit into empty on one side and full on the other.
Same address, opposite verdict — how the wrap bit breaks the tie
data flowThe occupancy — a redundant but clarifying view. Because the pointers carry the lap bit, their difference over the AW+1 bits, count = wptr - rptr, is the exact number of stored words, always in 0..DEPTH. You do not need to compute it to produce the flags — the two comparators above are cheaper — but it is the invariant every testbench checks (§5), and it is the seed of the first alternative scheme (§ synthesis trade-off): instead of reading the pointers, maintain count as an explicit up/down counter and set empty = (count == 0), full = (count == DEPTH).
4. Real RTL Implementation
This is the core of the page. We build three things — (a) the full/empty logic via the extra-MSB pointer scheme ((AW+1)-bit wptr/rptr, the exact empty/full conditions, WIDTH and DEPTH generic with power-of-two DEPTH); (b) the occupancy-counter alternative (count-based full/empty) for contrast; and (c) the off-by-one bug beside the fix — and each is shown in SystemVerilog, Verilog, and VHDL with an RTL block and a self-checking clocked testbench. The reasoning is identical in all three; only the syntax differs.
One discipline runs through every RTL block, inherited from 7.1 and the register pattern: pointers update on the clock with non-blocking assignments, reset is explicit (synchronous, active-high rst here), and a write is only committed when wr_en && !full, a read only when rd_en && !empty — the flags gate the pointer motion, which is what makes the whole thing safe.
4a. The extra-MSB pointer scheme — full/empty, three ways
The FIFO stores DEPTH = 2**AW words of WIDTH bits. The pointers are AW+1 bits: [AW-1:0] addresses the memory, [AW] is the wrap bit. empty compares the whole pointer; full compares the address fields and requires the wrap bits to differ.
module fifo_ptr #(
parameter int WIDTH = 8, // datapath width
parameter int DEPTH = 16, // MUST be a power of two
localparam int AW = $clog2(DEPTH) // address width; pointers are AW+1
)(
input logic clk,
input logic rst, // synchronous, active-high
input logic wr_en,
input logic rd_en,
input logic [WIDTH-1:0] wr_data,
output logic [WIDTH-1:0] rd_data,
output logic full,
output logic empty
);
logic [WIDTH-1:0] mem [DEPTH];
logic [AW:0] wptr, rptr; // AW+1 bits: [AW-1:0]=address, [AW]=wrap
// Flags are pure combinational reads of the pointers.
// EMPTY: pointers fully equal (same address AND same wrap bit) -> reader caught writer.
assign empty = (wptr == rptr);
// FULL: wrap bits DIFFER but address bits EQUAL -> writer lapped reader exactly once.
assign full = (wptr[AW] != rptr[AW]) && (wptr[AW-1:0] == rptr[AW-1:0]);
// Commit a write only when there is room; a read only when there is data.
// The flags gate pointer motion -> no overrun, no underrun, by construction.
always_ff @(posedge clk) begin
if (rst) begin
wptr <= '0;
rptr <= '0; // reset -> both zero -> powers up EMPTY
end else begin
if (wr_en && !full) begin
mem[wptr[AW-1:0]] <= wr_data; // address = low AW bits only
wptr <= wptr + 1'b1; // advances into the wrap bit at rollover
end
if (rd_en && !empty)
rptr <= rptr + 1'b1;
end
end
assign rd_data = mem[rptr[AW-1:0]]; // combinational read (FWFT-style)
endmoduleThe clocked testbench does the thing the flagship stands or falls on: it fills to exactly full and checks full asserts on the DEPTH-th write and not before, drains to exactly empty and checks empty asserts on the last read and not before, refuses to overrun or underrun, and asserts full and empty are never both high.
module fifo_ptr_tb;
localparam int WIDTH = 8;
localparam int DEPTH = 4; // small so the boundary is easy to read
logic clk = 1'b0, rst, wr_en, rd_en, full, empty;
logic [WIDTH-1:0] wr_data, rd_data;
int errors = 0;
fifo_ptr #(.WIDTH(WIDTH), .DEPTH(DEPTH)) dut (
.clk(clk), .rst(rst), .wr_en(wr_en), .rd_en(rd_en),
.wr_data(wr_data), .rd_data(rd_data), .full(full), .empty(empty));
always #5 clk = ~clk;
// Invariant that must hold EVERY cycle: full and empty are never both true.
always @(posedge clk)
if (full && empty) begin
$error("INVARIANT: full and empty asserted together"); errors++;
end
initial begin
rst = 1'b1; wr_en = 1'b0; rd_en = 1'b0; wr_data = '0;
@(posedge clk); #1;
assert (empty && !full) else begin $error("reset: expected empty"); errors++; end
rst = 1'b0;
// FILL to EXACTLY full: DEPTH writes. full must be low until the DEPTH-th.
for (int i = 0; i < DEPTH; i++) begin
@(negedge clk); wr_en = 1'b1; wr_data = 8'hA0 + i[7:0];
@(posedge clk); #1;
wr_en = 1'b0;
if (i < DEPTH-1)
assert (!full) else begin $error("full too early after %0d writes", i+1); errors++; end
else
assert (full) else begin $error("full NOT set on the DEPTH-th write"); errors++; end
assert (!empty) else begin $error("empty set while filling"); errors++; end
end
// OVERRUN guard: a write while full must NOT advance / must not corrupt.
@(negedge clk); wr_en = 1'b1; wr_data = 8'hFF;
@(posedge clk); #1; wr_en = 1'b0;
assert (full) else begin $error("full dropped on a blocked write"); errors++; end
// DRAIN to EXACTLY empty: DEPTH reads, checking FIFO order and the boundary.
for (int i = 0; i < DEPTH; i++) begin
assert (rd_data === 8'hA0 + i[7:0])
else begin $error("order: read %h exp %h", rd_data, 8'hA0 + i[7:0]); errors++; end
@(negedge clk); rd_en = 1'b1;
@(posedge clk); #1;
rd_en = 1'b0;
if (i < DEPTH-1)
assert (!empty) else begin $error("empty too early after %0d reads", i+1); errors++; end
else
assert (empty) else begin $error("empty NOT set on the last read"); errors++; end
assert (!full) else begin $error("full set while draining"); errors++; end
end
if (errors == 0) $display("PASS: full on DEPTH-th write, empty on last read, no off-by-one");
else $display("FAIL: %0d errors", errors);
$finish;
end
endmoduleThe Verilog form is the same structure with reg/wire typing; $clog2 is used at elaboration to size the pointers, and AW is passed as a parameter because Verilog cannot derive a localparam from another parameter as cleanly in all tools.
module fifo_ptr #(
parameter WIDTH = 8,
parameter DEPTH = 16, // power of two
parameter AW = 4 // = clog2(DEPTH); set by instantiator
)(
input wire clk,
input wire rst, // synchronous, active-high
input wire wr_en,
input wire rd_en,
input wire [WIDTH-1:0] wr_data,
output wire [WIDTH-1:0] rd_data,
output wire full,
output wire empty
);
reg [WIDTH-1:0] mem [0:DEPTH-1];
reg [AW:0] wptr, rptr; // AW+1 bits
// EMPTY: whole pointers equal. FULL: wrap bits differ, address bits equal.
assign empty = (wptr == rptr);
assign full = (wptr[AW] != rptr[AW]) && (wptr[AW-1:0] == rptr[AW-1:0]);
always @(posedge clk) begin
if (rst) begin
wptr <= {(AW+1){1'b0}};
rptr <= {(AW+1){1'b0}}; // powers up empty
end else begin
if (wr_en && !full) begin
mem[wptr[AW-1:0]] <= wr_data;
wptr <= wptr + 1'b1;
end
if (rd_en && !empty)
rptr <= rptr + 1'b1;
end
end
assign rd_data = mem[rptr[AW-1:0]];
endmodule module fifo_ptr_tb;
parameter WIDTH = 8;
parameter DEPTH = 4;
parameter AW = 2;
reg clk, rst, wr_en, rd_en;
reg [WIDTH-1:0] wr_data;
wire [WIDTH-1:0] rd_data;
wire full, empty;
integer i, errors;
fifo_ptr #(.WIDTH(WIDTH), .DEPTH(DEPTH), .AW(AW)) dut (
.clk(clk), .rst(rst), .wr_en(wr_en), .rd_en(rd_en),
.wr_data(wr_data), .rd_data(rd_data), .full(full), .empty(empty));
always #5 clk = ~clk;
// full and empty must never be asserted together.
always @(posedge clk)
if (full && empty) begin
$display("FAIL: full and empty asserted together"); errors = errors + 1;
end
initial begin
errors = 0; clk = 1'b0; rst = 1'b1; wr_en = 1'b0; rd_en = 1'b0; wr_data = 8'h00;
@(posedge clk); #1;
if (!(empty && !full)) begin $display("FAIL: reset not empty"); errors = errors + 1; end
rst = 1'b0;
// FILL to EXACTLY full.
for (i = 0; i < DEPTH; i = i + 1) begin
@(negedge clk); wr_en = 1'b1; wr_data = 8'hA0 + i;
@(posedge clk); #1; wr_en = 1'b0;
if (i < DEPTH-1 && full) begin
$display("FAIL: full too early after %0d writes", i+1); errors = errors + 1;
end
if (i == DEPTH-1 && !full) begin
$display("FAIL: full NOT set on DEPTH-th write"); errors = errors + 1;
end
end
// OVERRUN guard.
@(negedge clk); wr_en = 1'b1; wr_data = 8'hFF;
@(posedge clk); #1; wr_en = 1'b0;
if (!full) begin $display("FAIL: full dropped on blocked write"); errors = errors + 1; end
// DRAIN to EXACTLY empty.
for (i = 0; i < DEPTH; i = i + 1) begin
if (rd_data !== (8'hA0 + i)) begin
$display("FAIL: order read %h exp %h", rd_data, 8'hA0 + i); errors = errors + 1;
end
@(negedge clk); rd_en = 1'b1;
@(posedge clk); #1; rd_en = 1'b0;
if (i < DEPTH-1 && empty) begin
$display("FAIL: empty too early after %0d reads", i+1); errors = errors + 1;
end
if (i == DEPTH-1 && !empty) begin
$display("FAIL: empty NOT set on last read"); errors = errors + 1;
end
end
if (errors == 0) $display("PASS: full on DEPTH-th write, empty on last read, no off-by-one");
else $display("FAIL: %0d errors", errors);
$finish;
end
endmoduleIn VHDL the pointers are unsigned(AW downto 0) from numeric_std; the flags are concurrent assignments, and slicing the address field is wptr(AW-1 downto 0) while the wrap bit is wptr(AW).
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
entity fifo_ptr is
generic (
WIDTH : positive := 8;
DEPTH : positive := 16; -- power of two
AW : positive := 4 -- = clog2(DEPTH)
);
port (
clk : in std_logic;
rst : in std_logic; -- synchronous, active-high
wr_en : in std_logic;
rd_en : in std_logic;
wr_data : in std_logic_vector(WIDTH-1 downto 0);
rd_data : out std_logic_vector(WIDTH-1 downto 0);
full : out std_logic;
empty : out std_logic
);
end entity;
architecture rtl of fifo_ptr is
type mem_t is array (0 to DEPTH-1) of std_logic_vector(WIDTH-1 downto 0);
signal mem : mem_t;
signal wptr : unsigned(AW downto 0) := (others => '0'); -- AW+1 bits
signal rptr : unsigned(AW downto 0) := (others => '0');
signal full_i, empty_i : std_logic;
begin
-- EMPTY: whole pointers equal. FULL: wrap bits differ, address bits equal.
empty_i <= '1' when wptr = rptr else '0';
full_i <= '1' when (wptr(AW) /= rptr(AW)) and
(wptr(AW-1 downto 0) = rptr(AW-1 downto 0)) else '0';
full <= full_i;
empty <= empty_i;
process (clk)
begin
if rising_edge(clk) then
if rst = '1' then
wptr <= (others => '0');
rptr <= (others => '0'); -- powers up empty
else
if wr_en = '1' and full_i = '0' then
mem(to_integer(wptr(AW-1 downto 0))) <= wr_data;
wptr <= wptr + 1;
end if;
if rd_en = '1' and empty_i = '0' then
rptr <= rptr + 1;
end if;
end if;
end if;
end process;
rd_data <= mem(to_integer(rptr(AW-1 downto 0)));
end architecture; library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
entity fifo_ptr_tb is
end entity;
architecture sim of fifo_ptr_tb is
constant WIDTH : positive := 8;
constant DEPTH : positive := 4;
constant AW : positive := 2;
signal clk : std_logic := '0';
signal rst, wr_en, rd_en, full, empty : std_logic := '0';
signal wr_data, rd_data : std_logic_vector(WIDTH-1 downto 0) := (others => '0');
begin
dut : entity work.fifo_ptr
generic map (WIDTH => WIDTH, DEPTH => DEPTH, AW => AW)
port map (clk => clk, rst => rst, wr_en => wr_en, rd_en => rd_en,
wr_data => wr_data, rd_data => rd_data, full => full, empty => empty);
clkgen : process
begin
clk <= '0'; wait for 5 ns;
clk <= '1'; wait for 5 ns;
end process;
-- full and empty must never be asserted together.
check : process (clk)
begin
if rising_edge(clk) then
assert not (full = '1' and empty = '1')
report "full and empty asserted together" severity error;
end if;
end process;
stim : process
begin
rst <= '1'; wait until rising_edge(clk); wait for 1 ns;
assert empty = '1' and full = '0' report "reset not empty" severity error;
rst <= '0';
-- FILL to EXACTLY full.
for i in 0 to DEPTH-1 loop
wait until falling_edge(clk);
wr_en <= '1'; wr_data <= std_logic_vector(to_unsigned(16#A0# + i, WIDTH));
wait until rising_edge(clk); wait for 1 ns; wr_en <= '0';
if i < DEPTH-1 then
assert full = '0' report "full too early" severity error;
else
assert full = '1' report "full NOT set on DEPTH-th write" severity error;
end if;
end loop;
-- OVERRUN guard.
wait until falling_edge(clk); wr_en <= '1'; wr_data <= x"FF";
wait until rising_edge(clk); wait for 1 ns; wr_en <= '0';
assert full = '1' report "full dropped on blocked write" severity error;
-- DRAIN to EXACTLY empty.
for i in 0 to DEPTH-1 loop
assert rd_data = std_logic_vector(to_unsigned(16#A0# + i, WIDTH))
report "FIFO order mismatch" severity error;
wait until falling_edge(clk); rd_en <= '1';
wait until rising_edge(clk); wait for 1 ns; rd_en <= '0';
if i < DEPTH-1 then
assert empty = '0' report "empty too early" severity error;
else
assert empty = '1' report "empty NOT set on last read" severity error;
end if;
end loop;
report "fifo_ptr self-check complete" severity note;
wait;
end process;
end architecture;4b. The occupancy-counter alternative — count-based full/empty
The alternative maintains an explicit occupancy count (an up/down counter, AW+1 bits so it can hold 0..DEPTH) and derives the flags from it: empty = (count == 0), full = (count == DEPTH). It is simpler to reason about and its flags are trivially unambiguous — but it costs an extra adder/subtractor and, crucially, it does not survive a clock-domain crossing (you cannot gray-code a count that both sides modify), which is why the pointer scheme is preferred for anything that might become async. Shown here in all three HDLs for contrast.
module fifo_count #(
parameter int WIDTH = 8,
parameter int DEPTH = 16,
localparam int AW = $clog2(DEPTH)
)(
input logic clk,
input logic rst,
input logic wr_en,
input logic rd_en,
input logic [WIDTH-1:0] wr_data,
output logic [WIDTH-1:0] rd_data,
output logic full,
output logic empty
);
logic [WIDTH-1:0] mem [DEPTH];
logic [AW-1:0] waddr, raddr; // plain AW-bit addresses (no wrap bit needed)
logic [AW:0] count; // AW+1 bits: holds 0..DEPTH
assign empty = (count == 0);
assign full = (count == DEPTH[AW:0]);
always_ff @(posedge clk) begin
if (rst) begin
waddr <= '0; raddr <= '0; count <= '0;
end else begin
if (wr_en && !full) begin
mem[waddr] <= wr_data;
waddr <= waddr + 1'b1; // wraps naturally at 2^AW
end
if (rd_en && !empty)
raddr <= raddr + 1'b1;
// count tracks the NET change: +1 on a committed write, -1 on a committed read.
case ({(wr_en && !full), (rd_en && !empty)})
2'b10: count <= count + 1'b1; // write only
2'b01: count <= count - 1'b1; // read only
default: count <= count; // both or neither -> net zero
endcase
end
end
assign rd_data = mem[raddr];
endmodule module fifo_count_tb;
localparam int WIDTH = 8, DEPTH = 4;
logic clk = 1'b0, rst, wr_en, rd_en, full, empty;
logic [WIDTH-1:0] wr_data, rd_data;
int errors = 0;
fifo_count #(.WIDTH(WIDTH), .DEPTH(DEPTH)) dut (
.clk(clk), .rst(rst), .wr_en(wr_en), .rd_en(rd_en),
.wr_data(wr_data), .rd_data(rd_data), .full(full), .empty(empty));
always #5 clk = ~clk;
always @(posedge clk) if (full && empty) begin $error("full & empty together"); errors++; end
initial begin
rst = 1'b1; wr_en = 0; rd_en = 0; wr_data = '0;
@(posedge clk); #1; rst = 1'b0;
assert (empty && !full) else begin $error("reset not empty"); errors++; end
for (int i = 0; i < DEPTH; i++) begin
@(negedge clk); wr_en = 1'b1; wr_data = 8'h50 + i[7:0];
@(posedge clk); #1; wr_en = 1'b0;
if (i == DEPTH-1) assert (full) else begin $error("count full late"); errors++; end
else assert (!full) else begin $error("count full early"); errors++; end
end
for (int i = 0; i < DEPTH; i++) begin
assert (rd_data === 8'h50 + i[7:0]) else begin $error("order"); errors++; end
@(negedge clk); rd_en = 1'b1;
@(posedge clk); #1; rd_en = 1'b0;
if (i == DEPTH-1) assert (empty) else begin $error("count empty late"); errors++; end
else assert (!empty) else begin $error("count empty early"); errors++; end
end
if (errors == 0) $display("PASS: counter form matches at the boundary");
else $display("FAIL: %0d errors", errors);
$finish;
end
endmodule module fifo_count #(
parameter WIDTH = 8,
parameter DEPTH = 16,
parameter AW = 4
)(
input wire clk,
input wire rst,
input wire wr_en,
input wire rd_en,
input wire [WIDTH-1:0] wr_data,
output wire [WIDTH-1:0] rd_data,
output wire full,
output wire empty
);
reg [WIDTH-1:0] mem [0:DEPTH-1];
reg [AW-1:0] waddr, raddr;
reg [AW:0] count; // 0..DEPTH
wire do_wr = wr_en && !full;
wire do_rd = rd_en && !empty;
assign empty = (count == 0);
assign full = (count == DEPTH[AW:0]);
always @(posedge clk) begin
if (rst) begin
waddr <= 0; raddr <= 0; count <= 0;
end else begin
if (do_wr) begin mem[waddr] <= wr_data; waddr <= waddr + 1'b1; end
if (do_rd) raddr <= raddr + 1'b1;
case ({do_wr, do_rd})
2'b10: count <= count + 1'b1;
2'b01: count <= count - 1'b1;
default: count <= count;
endcase
end
end
assign rd_data = mem[raddr];
endmodule module fifo_count_tb;
parameter WIDTH = 8, DEPTH = 4, AW = 2;
reg clk, rst, wr_en, rd_en;
reg [WIDTH-1:0] wr_data;
wire [WIDTH-1:0] rd_data;
wire full, empty;
integer i, errors;
fifo_count #(.WIDTH(WIDTH), .DEPTH(DEPTH), .AW(AW)) dut (
.clk(clk), .rst(rst), .wr_en(wr_en), .rd_en(rd_en),
.wr_data(wr_data), .rd_data(rd_data), .full(full), .empty(empty));
always #5 clk = ~clk;
always @(posedge clk) if (full && empty) begin
$display("FAIL: full & empty together"); errors = errors + 1; end
initial begin
errors = 0; clk = 0; rst = 1; wr_en = 0; rd_en = 0; wr_data = 0;
@(posedge clk); #1; rst = 0;
if (!(empty && !full)) begin $display("FAIL: reset not empty"); errors = errors + 1; end
for (i = 0; i < DEPTH; i = i + 1) begin
@(negedge clk); wr_en = 1; wr_data = 8'h50 + i;
@(posedge clk); #1; wr_en = 0;
if (i == DEPTH-1 && !full) begin $display("FAIL: full late"); errors = errors + 1; end
if (i < DEPTH-1 && full) begin $display("FAIL: full early"); errors = errors + 1; end
end
for (i = 0; i < DEPTH; i = i + 1) begin
if (rd_data !== (8'h50 + i)) begin $display("FAIL: order"); errors = errors + 1; end
@(negedge clk); rd_en = 1;
@(posedge clk); #1; rd_en = 0;
if (i == DEPTH-1 && !empty) begin $display("FAIL: empty late"); errors = errors + 1; end
if (i < DEPTH-1 && empty) begin $display("FAIL: empty early"); errors = errors + 1; end
end
if (errors == 0) $display("PASS: counter form matches at the boundary");
else $display("FAIL: %0d errors", errors);
$finish;
end
endmodule library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
entity fifo_count is
generic ( WIDTH : positive := 8; DEPTH : positive := 16; AW : positive := 4 );
port (
clk, rst, wr_en, rd_en : in std_logic;
wr_data : in std_logic_vector(WIDTH-1 downto 0);
rd_data : out std_logic_vector(WIDTH-1 downto 0);
full, empty : out std_logic
);
end entity;
architecture rtl of fifo_count is
type mem_t is array (0 to DEPTH-1) of std_logic_vector(WIDTH-1 downto 0);
signal mem : mem_t;
signal waddr : unsigned(AW-1 downto 0) := (others => '0');
signal raddr : unsigned(AW-1 downto 0) := (others => '0');
signal count : unsigned(AW downto 0) := (others => '0'); -- 0..DEPTH
signal full_i, empty_i : std_logic;
signal do_wr, do_rd : std_logic;
begin
empty_i <= '1' when count = 0 else '0';
full_i <= '1' when count = to_unsigned(DEPTH, AW+1) else '0';
empty <= empty_i;
full <= full_i;
do_wr <= wr_en and not full_i;
do_rd <= rd_en and not empty_i;
process (clk)
begin
if rising_edge(clk) then
if rst = '1' then
waddr <= (others => '0'); raddr <= (others => '0'); count <= (others => '0');
else
if do_wr = '1' then
mem(to_integer(waddr)) <= wr_data;
waddr <= waddr + 1;
end if;
if do_rd = '1' then
raddr <= raddr + 1;
end if;
if do_wr = '1' and do_rd = '0' then
count <= count + 1;
elsif do_wr = '0' and do_rd = '1' then
count <= count - 1;
end if;
end if;
end if;
end process;
rd_data <= mem(to_integer(raddr));
end architecture; library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
entity fifo_count_tb is
end entity;
architecture sim of fifo_count_tb is
constant WIDTH : positive := 8; constant DEPTH : positive := 4; constant AW : positive := 2;
signal clk : std_logic := '0';
signal rst, wr_en, rd_en, full, empty : std_logic := '0';
signal wr_data, rd_data : std_logic_vector(WIDTH-1 downto 0) := (others => '0');
begin
dut : entity work.fifo_count
generic map (WIDTH => WIDTH, DEPTH => DEPTH, AW => AW)
port map (clk => clk, rst => rst, wr_en => wr_en, rd_en => rd_en,
wr_data => wr_data, rd_data => rd_data, full => full, empty => empty);
clkgen : process begin clk <= '0'; wait for 5 ns; clk <= '1'; wait for 5 ns; end process;
check : process (clk) begin
if rising_edge(clk) then
assert not (full = '1' and empty = '1')
report "full & empty together" severity error;
end if;
end process;
stim : process
begin
rst <= '1'; wait until rising_edge(clk); wait for 1 ns; rst <= '0';
assert empty = '1' and full = '0' report "reset not empty" severity error;
for i in 0 to DEPTH-1 loop
wait until falling_edge(clk);
wr_en <= '1'; wr_data <= std_logic_vector(to_unsigned(16#50# + i, WIDTH));
wait until rising_edge(clk); wait for 1 ns; wr_en <= '0';
if i = DEPTH-1 then assert full = '1' report "full late" severity error;
else assert full = '0' report "full early" severity error;
end if;
end loop;
for i in 0 to DEPTH-1 loop
assert rd_data = std_logic_vector(to_unsigned(16#50# + i, WIDTH))
report "order" severity error;
wait until falling_edge(clk); rd_en <= '1';
wait until rising_edge(clk); wait for 1 ns; rd_en <= '0';
if i = DEPTH-1 then assert empty = '1' report "empty late" severity error;
else assert empty = '0' report "empty early" severity error;
end if;
end loop;
report "fifo_count self-check complete" severity note;
wait;
end process;
end architecture;4c. The signature bug — equal-width pointers vs the extra-MSB fix
Pattern (c) is the flagship failure, shown here as buggy vs fixed RTL in each language and dramatized in §7. The buggy design uses equal-width (AW-bit) pointers — no wrap bit — so wptr == rptr is the only comparison available and it means both empty and full. The naive patch ("call it full when the next write pointer would equal the read pointer") is where the off-by-one is born. The fix is the (AW+1)-bit scheme from 4a.
// BUGGY: pointers are only AW bits -> no wrap bit. wptr==rptr is BOTH empty and full,
// so this "patches" full by looking one write ahead. But it forgot the write
// never actually happens when full, so the boundary is off by one under load.
module fifo_bad #(
parameter int WIDTH = 8, parameter int DEPTH = 16, localparam int AW = $clog2(DEPTH)
)(
input logic clk, rst, wr_en, rd_en, input logic [WIDTH-1:0] wr_data,
output logic [WIDTH-1:0] rd_data, output logic full, empty
);
logic [WIDTH-1:0] mem [DEPTH];
logic [AW-1:0] wptr, rptr; // AW bits only -> NO wrap information
assign empty = (wptr == rptr);
// WRONG: "full when the slot before rptr is reached" but with no lap bit this
// aliases with empty and mis-times the boundary; under a sustained burst it
// reports NOT full one slot too long and overwrites an unread word.
assign full = ((wptr + 1'b1) == rptr) && (wptr != rptr);
always_ff @(posedge clk) begin
if (rst) begin wptr <= '0; rptr <= '0; end
else begin
if (wr_en) begin mem[wptr] <= wr_data; wptr <= wptr + 1'b1; end // NOT gated by full!
if (rd_en && !empty) rptr <= rptr + 1'b1;
end
end
assign rd_data = mem[rptr];
endmodule
// FIXED: (AW+1)-bit pointers. empty = whole pointers equal; full = wrap bits differ,
// address bits equal. Writes gated by full, reads by empty. No off-by-one.
module fifo_good #(
parameter int WIDTH = 8, parameter int DEPTH = 16, localparam int AW = $clog2(DEPTH)
)(
input logic clk, rst, wr_en, rd_en, input logic [WIDTH-1:0] wr_data,
output logic [WIDTH-1:0] rd_data, output logic full, empty
);
logic [WIDTH-1:0] mem [DEPTH];
logic [AW:0] wptr, rptr; // AW+1 bits -> the wrap bit is back
assign empty = (wptr == rptr);
assign full = (wptr[AW] != rptr[AW]) && (wptr[AW-1:0] == rptr[AW-1:0]);
always_ff @(posedge clk) begin
if (rst) begin wptr <= '0; rptr <= '0; end
else begin
if (wr_en && !full) begin mem[wptr[AW-1:0]] <= wr_data; wptr <= wptr + 1'b1; end
if (rd_en && !empty) rptr <= rptr + 1'b1;
end
end
assign rd_data = mem[rptr[AW-1:0]];
endmodule module fifo_bug_tb;
localparam int WIDTH = 8, DEPTH = 4;
logic clk = 1'b0, rst, wr_en, rd_en, full, empty;
logic [WIDTH-1:0] wr_data, rd_data;
int errors = 0;
// Bind to fifo_good to PASS. fifo_bad overruns an unread word under a full burst.
fifo_good #(.WIDTH(WIDTH), .DEPTH(DEPTH)) dut (
.clk(clk), .rst(rst), .wr_en(wr_en), .rd_en(rd_en),
.wr_data(wr_data), .rd_data(rd_data), .full(full), .empty(empty));
always #5 clk = ~clk;
initial begin
rst = 1'b1; wr_en = 0; rd_en = 0; wr_data = '0;
@(posedge clk); #1; rst = 1'b0;
// Push DEPTH+2 words back-to-back. A correct FIFO stores exactly DEPTH and
// asserts full; a buggy one keeps writing and destroys the earliest words.
for (int i = 0; i < DEPTH + 2; i++) begin
@(negedge clk); wr_en = 1'b1; wr_data = 8'h10 + i[7:0];
@(posedge clk); #1;
end
wr_en = 1'b0;
assert (full) else begin $error("not full after over-filling"); errors++; end
// The first DEPTH words (0x10..0x13) must survive intact and read out in order.
for (int i = 0; i < DEPTH; i++) begin
assert (rd_data === 8'h10 + i[7:0])
else begin $error("overrun: read %h exp %h", rd_data, 8'h10 + i[7:0]); errors++; end
@(negedge clk); rd_en = 1'b1;
@(posedge clk); #1; rd_en = 1'b0;
end
assert (empty) else begin $error("not empty after draining"); errors++; end
if (errors == 0) $display("PASS: full gated writes; earliest words survived; empty at end");
else $display("FAIL: %0d errors (an unread word was overwritten)", errors);
$finish;
end
endmoduleThe Verilog buggy/fixed pair tells the same story with reg/wire typing; the difference is entirely in the pointer width and whether the write is gated by full.
// BUGGY: AW-bit pointers, no wrap bit, write not gated by full -> off-by-one overrun.
module fifo_bad #(parameter WIDTH = 8, DEPTH = 16, AW = 4) (
input wire clk, rst, wr_en, rd_en, input wire [WIDTH-1:0] wr_data,
output wire [WIDTH-1:0] rd_data, output wire full, empty
);
reg [WIDTH-1:0] mem [0:DEPTH-1];
reg [AW-1:0] wptr, rptr; // no wrap bit
assign empty = (wptr == rptr);
assign full = ((wptr + 1'b1) == rptr) && (wptr != rptr); // WRONG boundary
always @(posedge clk) begin
if (rst) begin wptr <= 0; rptr <= 0; end
else begin
if (wr_en) begin mem[wptr] <= wr_data; wptr <= wptr + 1'b1; end // ungated!
if (rd_en && !empty) rptr <= rptr + 1'b1;
end
end
assign rd_data = mem[rptr];
endmodule
// FIXED: (AW+1)-bit pointers, correct conditions, writes gated by full.
module fifo_good #(parameter WIDTH = 8, DEPTH = 16, AW = 4) (
input wire clk, rst, wr_en, rd_en, input wire [WIDTH-1:0] wr_data,
output wire [WIDTH-1:0] rd_data, output wire full, empty
);
reg [WIDTH-1:0] mem [0:DEPTH-1];
reg [AW:0] wptr, rptr; // extra MSB
assign empty = (wptr == rptr);
assign full = (wptr[AW] != rptr[AW]) && (wptr[AW-1:0] == rptr[AW-1:0]);
always @(posedge clk) begin
if (rst) begin wptr <= 0; rptr <= 0; end
else begin
if (wr_en && !full) begin mem[wptr[AW-1:0]] <= wr_data; wptr <= wptr + 1'b1; end
if (rd_en && !empty) rptr <= rptr + 1'b1;
end
end
assign rd_data = mem[rptr[AW-1:0]];
endmodule module fifo_bug_tb;
parameter WIDTH = 8, DEPTH = 4, AW = 2;
reg clk, rst, wr_en, rd_en;
reg [WIDTH-1:0] wr_data;
wire [WIDTH-1:0] rd_data;
wire full, empty;
integer i, errors;
// Bind to fifo_good to PASS; fifo_bad overwrites an unread word.
fifo_good #(.WIDTH(WIDTH), .DEPTH(DEPTH), .AW(AW)) dut (
.clk(clk), .rst(rst), .wr_en(wr_en), .rd_en(rd_en),
.wr_data(wr_data), .rd_data(rd_data), .full(full), .empty(empty));
always #5 clk = ~clk;
initial begin
errors = 0; clk = 0; rst = 1; wr_en = 0; rd_en = 0; wr_data = 0;
@(posedge clk); #1; rst = 0;
for (i = 0; i < DEPTH + 2; i = i + 1) begin
@(negedge clk); wr_en = 1; wr_data = 8'h10 + i;
@(posedge clk); #1;
end
wr_en = 0;
if (!full) begin $display("FAIL: not full after over-filling"); errors = errors + 1; end
for (i = 0; i < DEPTH; i = i + 1) begin
if (rd_data !== (8'h10 + i)) begin
$display("FAIL: overrun read %h exp %h", rd_data, 8'h10 + i); errors = errors + 1;
end
@(negedge clk); rd_en = 1;
@(posedge clk); #1; rd_en = 0;
end
if (!empty) begin $display("FAIL: not empty after draining"); errors = errors + 1; end
if (errors == 0) $display("PASS: full gated writes; earliest words survived");
else $display("FAIL: %0d errors (an unread word was overwritten)", errors);
$finish;
end
endmoduleIn VHDL the same bug appears when the pointers are unsigned(AW-1 downto 0) — no wrap bit — and the fix widens them to unsigned(AW downto 0) and gates the write with full.
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
-- BUGGY: AW-bit pointers (no wrap), write ungated by full -> off-by-one overrun.
entity fifo_bad is
generic ( WIDTH : positive := 8; DEPTH : positive := 16; AW : positive := 4 );
port ( clk, rst, wr_en, rd_en : in std_logic;
wr_data : in std_logic_vector(WIDTH-1 downto 0);
rd_data : out std_logic_vector(WIDTH-1 downto 0);
full, empty : out std_logic );
end entity;
architecture rtl of fifo_bad is
type mem_t is array (0 to DEPTH-1) of std_logic_vector(WIDTH-1 downto 0);
signal mem : mem_t;
signal wptr : unsigned(AW-1 downto 0) := (others => '0'); -- no wrap bit
signal rptr : unsigned(AW-1 downto 0) := (others => '0');
signal empty_i : std_logic;
begin
empty_i <= '1' when wptr = rptr else '0';
empty <= empty_i;
full <= '1' when ((wptr + 1) = rptr) and (wptr /= rptr) else '0'; -- WRONG boundary
process (clk) begin
if rising_edge(clk) then
if rst = '1' then wptr <= (others => '0'); rptr <= (others => '0');
else
if wr_en = '1' then -- ungated!
mem(to_integer(wptr)) <= wr_data; wptr <= wptr + 1;
end if;
if rd_en = '1' and empty_i = '0' then rptr <= rptr + 1; end if;
end if;
end if;
end process;
rd_data <= mem(to_integer(rptr));
end architecture;
-- FIXED: (AW+1)-bit pointers, correct conditions, write gated by full.
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
entity fifo_good is
generic ( WIDTH : positive := 8; DEPTH : positive := 16; AW : positive := 4 );
port ( clk, rst, wr_en, rd_en : in std_logic;
wr_data : in std_logic_vector(WIDTH-1 downto 0);
rd_data : out std_logic_vector(WIDTH-1 downto 0);
full, empty : out std_logic );
end entity;
architecture rtl of fifo_good is
type mem_t is array (0 to DEPTH-1) of std_logic_vector(WIDTH-1 downto 0);
signal mem : mem_t;
signal wptr : unsigned(AW downto 0) := (others => '0'); -- extra MSB
signal rptr : unsigned(AW downto 0) := (others => '0');
signal full_i, empty_i : std_logic;
begin
empty_i <= '1' when wptr = rptr else '0';
full_i <= '1' when (wptr(AW) /= rptr(AW)) and
(wptr(AW-1 downto 0) = rptr(AW-1 downto 0)) else '0';
empty <= empty_i; full <= full_i;
process (clk) begin
if rising_edge(clk) then
if rst = '1' then wptr <= (others => '0'); rptr <= (others => '0');
else
if wr_en = '1' and full_i = '0' then
mem(to_integer(wptr(AW-1 downto 0))) <= wr_data; wptr <= wptr + 1;
end if;
if rd_en = '1' and empty_i = '0' then rptr <= rptr + 1; end if;
end if;
end if;
end process;
rd_data <= mem(to_integer(rptr(AW-1 downto 0)));
end architecture; library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
entity fifo_bug_tb is
end entity;
architecture sim of fifo_bug_tb is
constant WIDTH : positive := 8; constant DEPTH : positive := 4; constant AW : positive := 2;
signal clk : std_logic := '0';
signal rst, wr_en, rd_en, full, empty : std_logic := '0';
signal wr_data, rd_data : std_logic_vector(WIDTH-1 downto 0) := (others => '0');
begin
-- Bind to fifo_good to PASS; fifo_bad overwrites an unread word.
dut : entity work.fifo_good
generic map (WIDTH => WIDTH, DEPTH => DEPTH, AW => AW)
port map (clk => clk, rst => rst, wr_en => wr_en, rd_en => rd_en,
wr_data => wr_data, rd_data => rd_data, full => full, empty => empty);
clkgen : process begin clk <= '0'; wait for 5 ns; clk <= '1'; wait for 5 ns; end process;
stim : process
begin
rst <= '1'; wait until rising_edge(clk); wait for 1 ns; rst <= '0';
for i in 0 to DEPTH+1 loop
wait until falling_edge(clk);
wr_en <= '1'; wr_data <= std_logic_vector(to_unsigned(16#10# + i, WIDTH));
wait until rising_edge(clk); wait for 1 ns;
end loop;
wr_en <= '0';
assert full = '1' report "not full after over-filling" severity error;
for i in 0 to DEPTH-1 loop
assert rd_data = std_logic_vector(to_unsigned(16#10# + i, WIDTH))
report "overrun: an unread word was overwritten" severity error;
wait until falling_edge(clk); rd_en <= '1';
wait until rising_edge(clk); wait for 1 ns; rd_en <= '0';
end loop;
assert empty = '1' report "not empty after draining" severity error;
report "fifo_bug self-check complete" severity note;
wait;
end process;
end architecture;Across all three languages the lesson is one sentence: give each pointer an extra wrap MSB so equal addresses on the same lap mean empty and equal addresses on opposite laps mean full — then gate every write with full and every read with empty, and there is no off-by-one.
5. Verification Strategy
A FIFO's flags are a boundary property, so verification lives at the boundary: fill to exactly full, drain to exactly empty, and check the flags flip on the precise transaction and not one before or after.
fullasserts on exactly the DEPTH-th write and never before;emptyasserts on exactly the read that takes the last word and never before; occupancy stays in0..DEPTH; andfullandemptyare never both true.
Everything below makes that invariant checkable and maps onto the testbenches in §4.
- Fill-to-exactly-full, self-checking. Reset, then issue
DEPTHwrites back-to-back and assertfullis low after each of the firstDEPTH-1writes and high after theDEPTH-th — this is the off-by-one detector forfull. The §4 testbenches do exactly this: SVassert (full)/assert (!full), Verilogif (i==DEPTH-1 && !full) $display("FAIL…"), VHDLassert full = '1' … severity error. Then over-fill by two more writes and confirm the earliest words survive on read-out (the §4c overrun test) — afullthat de-asserts one slot late overwrites an unread word and fails this check. - Drain-to-exactly-empty, self-checking. From full, issue
DEPTHreads and assertemptyis low after each of the firstDEPTH-1and high after the last — the off-by-one detector forempty— while checking the words read out in FIFO order. Anemptythat asserts one slot early leaves the last word unread; one slot late lets the reader pop a stale location. - Invariants, stated conceptually. Three properties must hold every cycle: (i)
fullandemptyare never simultaneously true (the §4 testbenches check this on everyposedge— structurally guaranteed here because empty needs equal wrap bits and full needs differing wrap bits); (ii) occupancywptr - rptris always in0..DEPTH(never negative, never over-full); (iii) a write is committed iffwr_en && !full, a read iffrd_en && !empty— the flags gate motion, so overrun and underrun are impossible. - Corner cases to exercise. Simultaneous read and write while full (occupancy holds at
DEPTH, one word in one word out); simultaneous read and write while empty (nothing happens — the read is gated); a full/drain/refill burst that crosses the wrap boundary several times (this is what exercises the wrap MSB — a scheme that works for the first lap but mis-handles the second is caught here); single-entry behaviour and, for aDEPTH=1FIFO, that full and empty still separate; and reset asserted mid-operation (pointers return to zero, FIFO reports empty). - Parameter-generic verification. Re-run the fill/drain/burst suite for
DEPTH = 2, 4, 8, 16andWIDTH = 1, 8, 32. A flag scheme that passes atDEPTH=4can still be wrong atDEPTH=8if a pointer width was hardcoded. Include a non-power-of-twoDEPTH(e.g. 6) as a negative test — the MSB scheme is expected to mis-report there, which is why §3 and §6 insist on power-of-two depth; verifying that it breaks confirms you understand the constraint rather than having stumbled into it. - Expected waveform. On a correct run, as writes stream in, occupancy climbs
0 → DEPTHandfullrises coincident with the clock edge of the DEPTH-th write, staying low through the previousDEPTH-1. As reads stream out, occupancy fallsDEPTH → 0andemptyrises coincident with the edge of the last read. At no point arefullandemptyboth high. The visual signature of the bug isfullstaying low for one extra write (then a later read reveals a corrupted, overwritten word) oremptyrising one read early (the last word never appears onrd_data).
6. Common Mistakes
The off-by-one — full one slot early or late. The signature failure. If full asserts one write too early you waste an entry (the FIFO reports full at DEPTH-1); if it asserts one write too late — the dangerous direction — a DEPTH-th write lands in a slot the reader has not emptied and overwrites an unread word under sustained load. The extra-MSB conditions assert full on exactly the DEPTH-th write; anything hand-derived from equal-width pointers is prone to landing a slot off. (Post-mortem in §7.)
Using bare wptr == rptr for both empty and full. The root ambiguity. With equal-width pointers, wptr == rptr is the only comparison, and it is true both when the FIFO is empty (reader caught writer) and when it is full (writer lapped reader). Assigning it to both flags makes them identical, so the FIFO can never actually report full — writes overrun on the first lap. There is no correct full/empty logic on equal-width pointers without extra state; you must add the wrap MSB (or a separate counter).
Wasting a slot unintentionally. The "declare full when the next write pointer equals the read pointer" scheme ((wptr+1) == rptr) is a legitimate design — the waste-one-slot scheme — but only if you chose it knowingly: it makes a DEPTH-entry memory hold only DEPTH-1 words so the two "equal" states never collide. Reaching for it by accident, or applying it to (AW+1)-bit pointers where the wrap bit already resolves the ambiguity, throws away an entry for nothing. Decide deliberately: extra-MSB scheme (uses all DEPTH slots) or waste-one-slot (gives up one to avoid the extra bit) — not a muddle of both.
Non-power-of-two DEPTH breaking the MSB scheme. The wrap MSB works only because a power-of-two address field rolls over from its maximum to zero at the exact instant the MSB toggles. If DEPTH is not a power of two, the address must wrap "early" (before the natural binary rollover), so the MSB toggle and the address rollover no longer coincide, and full/empty mis-report. Either keep DEPTH a power of two (the standard) or switch to the occupancy-counter scheme, which handles any DEPTH because it counts explicitly.
Comparing the full pointer where only the address bits should match. In the full condition, comparing all AW+1 bits (wptr == rptr including the MSB) makes full collapse into empty — it would only be true when the wrap bits are equal, which is never the full state. full must compare the address fields for equality and the wrap bits for inequality. Conversely, comparing only the address bits for empty (dropping the MSB) re-introduces the ambiguity. The asymmetry — whole pointer for empty, address-only-plus-wrap-differ for full — is exact and must be respected.
Combinationally coupling the flags into the pointer update in a way that creates a loop. full depends on the pointers and the pointers' update depends on full (wr_en && !full). That is fine because full is a registered function of the pointers (it reads the current pointer values, which changed on the previous edge), not a same-cycle combinational function of the next pointer. Deriving full from the next pointer value and feeding it back into the same-cycle enable creates a combinational loop; keep the flags a function of the current registered pointers.
7. DebugLab
The FIFO that ate a word — a full/empty off-by-one under a sustained burst
The engineering lesson: when the write and read pointers are equal the FIFO is at a boundary, but which boundary — empty or full — is undecidable from the addresses alone; you must carry the missing bit of information in the pointers themselves, not bolt it on as a side flag. The tell is a bug that only bites under sustained near-full traffic and tracks the fill level rather than any single input — a FIFO that is correct when lightly loaded and eats or duplicates a word when driven to the boundary is a full/empty off-by-one, not a data-path bug. Two habits make it impossible, and they are identical across SystemVerilog, Verilog, and VHDL: make each pointer one bit wider than the address so empty is fully-equal pointers and full is same-address / opposite-wrap-bit, and gate every write with full and every read with empty, then verify by filling to exactly full and draining to exactly empty with no off-by-one. The extra-MSB scheme is the one to internalize because it is the exact pointer that gets gray-coded to cross clock domains in the asynchronous FIFO (11.6).
8. Interview Q&A
9. Exercises
Design and reasoning exercises — no syntax drills. Each rehearses the equal-pointers / wrap-bit reasoning and the boundary discipline behind it.
Exercise 1 — Derive and prove the boundary
For a DEPTH = 8 FIFO, state the pointer width, the empty condition, and the full condition in terms of wptr, rptr, and AW. Then hand-trace the pointers (in binary) from reset through eight writes and eight reads, and mark the exact write on which full asserts and the exact read on which empty asserts. Confirm in one line each that full does not assert on the seventh write and empty does not assert on the seventh read.
Exercise 2 — Choose the disambiguation scheme
For each requirement, pick extra-MSB pointers, an occupancy counter, or waste-one-slot, and justify in one line: (a) a single-clock FIFO that must use every one of its DEPTH slots; (b) a FIFO whose depth is required to be exactly 6; (c) a dual-clock FIFO that crosses from a write clock to a read clock; (d) a tiny FIFO where the designer wants to avoid both an extra pointer bit and an adder and can spare one entry. Then state which single scheme you would standardize on across a design and why.
Exercise 3 — Find the off-by-one on paper
An engineer writes full = ((wptr + 1'b1) == rptr) on (AW+1)-bit pointers (the extra-MSB pointers) and leaves empty = (wptr == rptr). Describe precisely what goes wrong: is full early, late, or does it waste a slot? Walk the DEPTH=4 boundary to show it. Then give the correct full condition for the extra-MSB pointers and explain why mixing the waste-one-slot rule with the wrap-bit scheme throws away an entry.
Exercise 4 — Verify without shipping the bug
Write the test plan (not the RTL) that would have caught the §7 overrun before tape-out. Specify: the exact fill sequence and what you assert after each write; the over-fill step and the post-drain check that proves no unread word was overwritten; the standing every-cycle invariants; and the one negative test (a non-power-of-two depth) that confirms you understand the power-of-two constraint. State which single check in your plan is the direct off-by-one detector for full.
10. Related Tutorials
Continue in RTL Design Patterns (sibling and forward links unlock as they ship):
- Synchronous FIFO Architecture — Chapter 7.1; the circular-buffer body this page completes — the dual-port memory and the wrapping write/read pointers whose equal-pointer boundary is resolved here.
- FIFO Programmable Flags — Chapter 7.3; almost-full / almost-empty thresholds built on the same occupancy the full/empty flags read — early warning before the hard boundary.
- FIFO Depth Calculation — Chapter 7.4; how deep the FIFO must be for a given producer/consumer rate — the sizing that decides the
DEPTHthis page's flags guard. - First-Word Fall-Through FIFO — Chapter 7.5; the read-timing variant where
rd_datais valid beforerd_en, changing howemptygates the first read. - FIFO Verification — Chapter 7.6; the full self-checking + assertion strategy this page's boundary tests are the core of.
- Asynchronous FIFO — Chapter 11.6; the dual-clock FIFO where these exact pointers get gray-coded and synchronized across clock domains — the reason the extra-MSB scheme is the one to learn.
- Gray-Coded Pointer Synchronization — Chapter 11.5; how a pointer is gray-coded so it can cross a clock boundary one-bit-at-a-time, the CDC-safe form of this page's pointers.
Backward / in-track dependencies:
- Up/Down Counters — Chapter 3.3; the occupancy counter alternative is exactly an up/down counter, and the pointers are up-counters with an extra wrap bit.
- Comparators — Chapter 1.5; the equality comparators that produce
fullandemptyfrom the pointer fields. - Dual-Port RAM — Chapter 6.2; the two-port memory the FIFO reads and writes as a circular buffer.
- Encoding & Conversions — Chapter 1.4; binary-to-gray and back — the encoding the async-FIFO pointers use, previewed here.
- Gray Counters — Chapter 3.5; the gray-coded counter the async FIFO's pointers become, so only one bit changes per step across a clock boundary.
- The Register Pattern (D-FF) — Chapter 2.1; the flops the pointers and flag registers are built from, and the reset-first clocked-update discipline.
- The RTL Design Mindset — Chapter 0.2; the State and Verification lenses this page applies — the pointers are the FIFO's state, and the flags are how you prove it safe.
- What Is an RTL Design Pattern? — Chapter 0.1; why full/empty logic earns the name "pattern" — a recurring problem, a reusable form, a synthesis reality, and a signature failure.
Verilog v1 prerequisites (the grammar this pattern transcribes into):
- Relational Operators — the equality comparisons (
==,!=) that build thefullandemptyconditions. - Bitwise Operators — the field slicing and bit tests (
wptr[AW],wptr[AW-1:0]) the flag logic reads. - Blocking and Non-Blocking Assignments — why the pointers and flag registers update with non-blocking (
<=) in their clocked process. - Physical Data Types — the vector widths (
AW,AW+1) whose deliberate sizing is the entire point of the wrap-bit scheme.
11. Summary
- Equal pointers are ambiguous — empty and full look identical. A FIFO is empty when the reader catches the writer (
wptr == rptr) and full when the writer laps the reader (wptr == rptragain). From the addresses alone you cannot tell "nothing here" from "no room here," and guessing wrong overwrites or drops a word under load. You must add the one bit of information the equal-address case is missing. - The extra-MSB pointer scheme adds that bit. Make each pointer one bit wider than the address: an N-deep FIFO (
DEPTH = 2**AW) uses(AW+1)-bit pointers, lowAWbits the memory address, the extra MSB a wrap (lap) bit. Thenempty = (wptr == rptr)(fully equal — same seat, same lap) andfull = (wptr[AW] != rptr[AW]) && (wptr[AW-1:0] == rptr[AW-1:0])(same seat, opposite lap).fullasserts on exactly theDEPTH-th write,emptyon exactly the last read — no off-by-one — and because empty needs equal wrap bits and full needs differing ones, they are mutually exclusive by construction.DEPTHmust be a power of two. - Two alternatives, each with a cost. A separate occupancy counter (
empty = count==0,full = count==DEPTH) is unambiguous and handles any depth but costs an up/down counter and cannot cross clock domains. The waste-one-slot scheme (fullwhen the next write pointer would equal the read pointer) avoids the extra bit but gives up one entry. The extra-MSB scheme is standard because it uses every slot, keeps the flags mutually exclusive, and — the decisive reason — its pointers gray-code cleanly, so it extends straight to the asynchronous FIFO (11.6). - The signature bug is the off-by-one. Equal-width pointers make
fullandemptythe same comparison; a hand-patched boundary lands a slot off, and an ungated write then overwrites an unread word under a sustained near-full burst — intermittent, load-dependent, invisible when lightly loaded. The tell is corruption that tracks the fill level, not any single input. - Verify at the boundary. Fill to exactly full (assert
fullon theDEPTH-th write and not before), drain to exactly empty (assertemptyon the last read and not before), over-fill and confirm the earliest words survive, and hold the invariants thatfullandemptyare never both true and occupancy stays in0..DEPTH. Built and self-check-verified here in SystemVerilog, Verilog, and VHDL.