“Design a synchronous FIFO with full and empty flags. Parameterize depth and width.”
The question tests flag discipline, not memory. The trap is the pointer-equality ambiguity: with plain binary pointers, equal pointers mean both full and empty.
State the interface first: push, pop, data in, data out, full, empty, clock, and active-low reset. Occupancy equals accepted pushes minus accepted pops since reset. Guards reject requests at the boundaries; the counter must never rely on clamping an invalid update. Across reset epochs, accepted pushes = delivered pops + reset-cancelled words + outstanding words.
A counter holds occupancy. Full asserts at depth, empty at zero. A push is accepted only when not full, and a pop only when not empty.
Signal | Meaning | Guard |
|---|---|---|
| Write request / read request | Accepted only when |
| Occupancy equals depth | Further pushes are ignored |
| Occupancy equals zero | Further pops are ignored, |
| Word removed by the last accepted pop | Registered; meaningful only after a pop |
Simultaneous push and pop keep occupancy unchanged when both are accepted. When full, a simultaneous pop is accepted and the push is refused, so occupancy falls by one.
DEPTH must be at least 1 (DEPTH = 1 is a single-entry FIFO): the pointer width is guarded as localparam int AW = (DEPTH > 1) ? $clog2(DEPTH) : 1; because $clog2(1) is 0.
Each slot shows values just after a rising edge. Inputs change right after an edge, so a push or pop drawn in a slot is accepted at the next edge, and the registered flags change one slot later. full rises after the fourth accepted push and falls after the first accepted pop.
Slot 0: reset is held, so empty is 1 and full is 0.
Slot 1: reset releases and push rises. Nothing is accepted yet, so empty is still 1.
Slot 2: the first push was accepted at the edge, so empty falls.
Slot 3: the second push was accepted.
Slot 4: the third push was accepted.
Slot 5: the fourth push filled the last entry, so full rises. Push stops and pop starts.
Slot 6: the first pop was accepted, so full falls.
Slot 7: the second pop leaves two entries stored.
“Push and pop arrive together while full. What happens?” The pop is accepted and the push is refused. Occupancy drops by one.
“Depth is not a power of two. What changes?” Binary pointers no longer wrap for free. Keep the counter and compare against depth, since pointer wrap needs explicit modulo logic.
“Should dout be combinational?” Choose the latency contract and target resource first. Combinational read may map to flops/muxes or asynchronous/distributed RAM; many FPGA block RAMs require clocked reads. Registered read alone does not guarantee SRAM inference. The asynchronous reset on dout here may prevent absorption into a RAM output register; use mapping reports and the target template, or reset a separate output-valid flag if the interface permits. ASIC macros have their own interfaces and collision rules.
A weaker answer draws the memory first and derives flags from pointer equality. That answer cannot distinguish full from empty without an extra bit, and it usually forgets the push-when-full and pop-when-empty guards.
Resetting pointers/count logically invalidates queued words here; consumers cannot read old entries before new pushes. Storage initialization, physical storage reset and multi-cycle scrubbing serve different requirements such as defined boot contents or erasure. They may be necessary, but bulk array reset can prevent RAM mapping and cost routing/area. Select the requirement and target-supported mechanism explicitly; this FIFO does not promise erasure.
15. The pop is accepted because the FIFO is not empty, while the push is refused because it is full.
dout hold before the first accepted pop?The reset value. No word has been removed yet, so dout is not meaningful whatever empty reads.
The full FIFO plus independent depth-1, depth-3 and depth-16 regression instances. Directed traffic visits every occupancy, wraps pointers and checks boundary rejection and simultaneous requests. Random traffic uses the upper Xorshift bits. Occupancy visits, accepted-operation transitions and random-phase occupancy visits are reported separately. A singleton depth cannot accept push and pop together under this contract.
`timescale 1ns/1ps
module sync_fifo #(
parameter int DW = 8,
parameter int DEPTH = 16 // must be at least 1
) (
input logic clk,
input logic rst_n,
input logic push,
input logic pop,
input logic [DW-1:0] din,
output logic [DW-1:0] dout,
output logic full,
output logic empty
);
// DEPTH = 1 guard ($clog2(1) is 0, so [$clog2(DEPTH)-1:0] would be [-1:0]).
localparam int AW = (DEPTH > 1) ? $clog2(DEPTH) : 1;
localparam int CW = $clog2(DEPTH + 1);
logic [DW-1:0] mem [DEPTH];
logic [AW-1:0] wr_ptr, rd_ptr;
logic [CW-1:0] count;
logic take_push, take_pop;
assign take_push = push && !full;
assign take_pop = pop && !empty;
assign full = (count == DEPTH);
assign empty = (count == '0);
always_ff @(posedge clk or negedge rst_n) begin
if (!rst_n) begin
wr_ptr <= '0;
rd_ptr <= '0;
count <= '0;
dout <= '0;
end else begin
if (take_push) begin
mem[wr_ptr] <= din;
wr_ptr <= (wr_ptr == AW'(DEPTH - 1)) ? '0 : wr_ptr + 1'b1; // explicit wrap: DEPTH need not be a power of two
end
if (take_pop) begin
dout <= mem[rd_ptr];
rd_ptr <= (rd_ptr == AW'(DEPTH - 1)) ? '0 : rd_ptr + 1'b1;
end
if (take_push && !take_pop) count <= count + 1'b1;
else if (take_pop && !take_push) count <= count - 1'b1;
end
end
endmodule
module fifo_case #(parameter int DEPTH = 16) (output logic done);
localparam int DW = 8;
logic clk = 0, rst_n = 0, push = 0, pop = 0;
logic [DW-1:0] din = 0, dout;
logic full, empty;
sync_fifo #(.DW(DW), .DEPTH(DEPTH)) dut (.*);
always #5 clk = ~clk;
int errors = 0;
logic [DW-1:0] ref_q [DEPTH];
int ref_head = 0, ref_tail = 0, ref_occ = 0;
logic [31:0] rnd = 32'h12345678;
int occupancy_hits [DEPTH+1];
int random_hits [DEPTH+1];
int transition_hits [4]; // accepted {push,pop}: 00, 01, 10, 11
bit random_phase = 0;
int cycles = 0;
task automatic cycle(input logic do_push, input logic do_pop, input logic [DW-1:0] data);
logic acc_push, acc_pop;
logic [DW-1:0] exp_data;
@(negedge clk);
push = do_push; pop = do_pop; din = data;
acc_push = do_push && !full;
acc_pop = do_pop && !empty;
exp_data = dout; // no accepted pop: output must hold
if (acc_push) begin
ref_q[ref_tail] = data;
ref_tail = (ref_tail + 1) % DEPTH;
end
if (acc_pop) exp_data = ref_q[ref_head];
@(posedge clk); #1;
if (dout !== exp_data) errors++;
if (acc_pop) begin
ref_head = (ref_head + 1) % DEPTH;
end
if (acc_push) ref_occ++;
if (acc_pop) ref_occ--;
if (dut.count !== ref_occ) errors++;
if (empty !== (ref_occ == 0)) errors++;
if (full !== (ref_occ == DEPTH)) errors++;
occupancy_hits[ref_occ]++;
transition_hits[{acc_push, acc_pop}]++;
if (random_phase) random_hits[ref_occ]++;
cycles++;
if (errors != 0)
$fatal(1, "FAIL: FIFO depth=%0d cycle=%0d push/pop=%b%b occupancy=%0d count=%0d dout=%h expected=%h",
DEPTH, cycles, do_push, do_pop, ref_occ, dut.count, dout, exp_data);
endtask
initial begin
done = 0;
for (int i = 0; i <= DEPTH; i++) begin
occupancy_hits[i] = 0; random_hits[i] = 0;
end
for (int i = 0; i < 4; i++) transition_hits[i] = 0;
repeat (3) @(posedge clk);
@(negedge clk) rst_n = 1;
@(posedge clk); #1;
if (!empty || full) errors++;
if (dut.count != 0) errors++;
cycle(0, 1, 8'h00); // pop while empty: ignored
if (!empty) errors++;
for (int i = 0; i < DEPTH; i++) // fill this configured depth
cycle(1, 0, i[7:0]);
if (!full) errors++;
cycle(1, 0, 8'hFF); // push while full: ignored
if (!full) errors++;
cycle(1, 1, 8'hEE); // full with push and pop: pop accepted, push refused
if (full) errors++;
repeat (4) cycle(1, 1, 8'hC0); // depth 1 alternates; deeper FIFOs hold partial occupancy
for (int i = 0; i < DEPTH; i++) cycle(0, 1, 8'h00);
if (!empty) errors++;
cycle(0, 0, 0); // accepted transition 00
cycle(1, 1, 8'hA5); // empty: push only
if (DEPTH > 1) cycle(1, 1, 8'h5A); // partial: both accepted
for (int i = 0; i < DEPTH; i++) cycle(0, 1, 0);
random_phase = 1;
for (int t = 0; t < 5000; t++) begin // deterministic pseudo-random regression
rnd = rnd ^ (rnd << 13);
rnd = rnd ^ (rnd >> 17);
rnd = rnd ^ (rnd << 5);
cycle(rnd[31], rnd[23], rnd[15:8]);
end
random_phase = 0;
for (int i = 0; i < DEPTH; i++) cycle(0, 1, 8'h00); // bounded drain
if (!empty) errors++;
for (int i = 0; i <= DEPTH; i++) begin
$display("COVER depth=%0d occupancy=%0d total=%0d random=%0d", DEPTH, i, occupancy_hits[i], random_hits[i]);
if (occupancy_hits[i] == 0) errors++;
if (random_hits[i] == 0) begin
errors++;
$display("ERROR: random coverage hole depth=%0d occupancy=%0d", DEPTH, i);
end
end
for (int i = 0; i < 4; i++) begin
$display("COVER depth=%0d accepted-transition=%0d hits=%0d", DEPTH, i, transition_hits[i]);
if ((i != 3 || DEPTH > 1) && transition_hits[i] == 0) errors++;
end
if (DEPTH == 1 && transition_hits[3] != 0) errors++;
if (errors != 0) $fatal(1, "FAIL: FIFO depth=%0d errors=%0d", DEPTH, errors);
done = 1;
end
endmodule
module tb_sync_fifo;
wire done1, done3, done16;
fifo_case #(.DEPTH(1)) c1 (.done(done1));
fifo_case #(.DEPTH(3)) c3 (.done(done3));
fifo_case #(.DEPTH(16)) c16 (.done(done16));
initial begin
wait (done1 && done3 && done16);
$display("PASS: finite FIFO regression at depths 1, 3, 16; see coverage counts");
$finish;
end
initial begin
#100000;
$fatal(1, "FAIL: FIFO regression watchdog");
end
endmoduleRegression Run with Icarus Verilog 13.0 (2026-10-16): prints PASS. It runs depth-1, depth-3 and depth-16 instances with directed and random traffic. It is not proof for all depths or sequences.