See it move
The idea
A FIFO is a queue: data comes out in the order it went in. It lets the producer and consumer run at different rates for a while. A synchronous FIFO uses one clock for both sides.
Pointers
A circular buffer needs two pointers. The write pointer marks the next slot to fill, and the read pointer marks the next slot to read. Both wrap around at the end.
Full or empty?
If the pointers are equal, the FIFO is either full or empty, and you can't tell which from the indices alone. The usual trick is one extra pointer bit:
- All bits equal: empty.
- Index bits equal, top bit different: full. The writer has lapped the reader.
module sync_fifo #(parameter W = 8, parameter DEPTH = 8) (
input clk, rst, wr, rd,
input [W-1:0] din,
output [W-1:0] dout,
output full, empty
);
localparam AW = $clog2(DEPTH);
reg [W-1:0] mem [0:DEPTH-1];
reg [AW:0] wp, rp;
assign empty = (wp == rp);
assign full = (wp[AW-1:0] == rp[AW-1:0]) && (wp[AW] != rp[AW]);
assign dout = mem[rp[AW-1:0]];
always_ff @(posedge clk)
if (rst) begin
wp <= '0;
rp <= '0;
end else begin
if (wr && !full) begin
mem[wp[AW-1:0]] <= din;
wp <= wp + 1'b1;
end
if (rd && !empty) rp <= rp + 1'b1;
end
endmoduleEdge cases to define and test
- Writing when full must not overwrite data.
- Reading when empty must not advance the pointer.
- A simultaneous read and write at full or empty should be defined by your specification.
- Decide whether the output is combinational, as above, or registered, which adds a cycle.
Common mistake
Using a depth that isn't a power of two with this pointer scheme. The pointers wrap naturally only at powers of two. Other depths need explicit wrap logic. Another common bug is checking full on the wrong clock cycle in the writer. Press Write until the animation refuses and look at the pointer bits.
One more to try
Key ideas
- Read and write pointers wrap around.
- An extra pointer bit separates full from empty.
- Writing when full and reading when empty must be defined.
Lab: FIFO depth lab
Your exercise
Find the bug
This code has one deliberate bug. Read the symptom, then click the line you think is wrong.
The fix
assign full = (wp[2:0] == rp[2:0]) && (wp[3] != rp[3]);
Why it failed
Equal pointers mean empty, which is the state after reset. Full needs the extra pointer bit: index bits equal, but top bits different, so the writer has lapped the reader. With this bug, both flags are high together.
Interview questions
coreHow does the extra pointer bit help?
Pointers equal: empty. Index bits equal but MSB differs: full.
basicA synchronous FIFO is 32 entries deep and uses the extra-bit pointer scheme. How wide is each pointer?
Six bits. Five bits address the 32 entries, since 2^5 = 32, and one extra top bit counts laps. When all six bits are equal, the FIFO is empty. When the low five match but the top bits differ, the writer has lapped the reader, and the FIFO is full.
basicInstead of an extra pointer bit, you could keep a count register. What are the trade-offs?
A count register, increased on a write and decreased on a read, gives full and empty and the exact occupancy directly. It needs an up/down counter, and it must handle a simultaneous read and write correctly. The extra-bit scheme needs no counter, just comparisons of the two pointers, and occupancy can still be computed as wp - rp. Both work for synchronous FIFOs, but only pointer-based schemes carry over to async FIFOs, where the pointers are passed between clock domains.
coreRight after reset, this FIFO refuses every write. Why?
assign empty = (wp == rp); assign full = (wp[AW-1:0] == rp[AW-1:0]);
The full flag compares only the index bits. After reset both pointers are zero, so full and empty are both 1, and the writer is blocked forever. In simulation, three writes after reset stored nothing. Full needs the lap bit as well: the index bits must be equal and the top bits must differ.
coreIn a depth-8 FIFO with 4-bit pointers, wp = 0010 and rp = 1110. How many words are inside, and what are the flags?
Occupancy is wp - rp in 4 bits: 2 - 14 = -12, which wraps to 4 (mod 16). So the FIFO holds 4 words, and it is neither full nor empty. The index bits are 010 and 110, which differ, so it can't be either. The writer has wrapped past the end of memory, and the subtraction handles that automatically.
coreWith the lesson's FIFO, the FIFO is full and the user asserts read and write in the same cycle. What happens? What if it is empty instead?
When full, the write is refused because full is high before the edge, but the read proceeds, so the count drops from 8 to 7. When empty, the read is refused, but the write proceeds, so the count goes from 0 to 1. Both outcomes were confirmed in simulation. Some FIFOs allow the write when full if a read happens in the same cycle. That is legal too, as long as the specification states it and the tests cover it.
coreSomeone sets DEPTH = 6 but keeps 3 index bits and the same pointer logic. What happens?
The pointers still wrap at 8, not 6, so full is not raised until 8 words have been written. Writes 7 and 8 go to memory indexes 6 and 7, which don't exist, so those words are lost. In simulation, full stayed low after 6 writes, the first 6 words read back correctly, and the next reads returned x. Non-power-of-two depths need explicit wrap logic, or a count-based design.
advancedWhat changes if you register the FIFO's output instead of reading memory combinationally?
The output gains a cycle of latency: data appears one cycle after the read request instead of in the same cycle. The reader logic must then use a valid signal that is delayed to match. The flags also need care, because a word can be in the output register while the memory itself is empty. A common variant, often called first-word fall-through, preloads the head word into the output register so it is visible without a read, which needs extra control logic.
advancedA writer sees the FIFO's flag through two pipeline flops, so it may keep writing for two cycles after the flag rises. For a depth-16 FIFO, at what occupancy should almost_full rise?
At 14, which is the depth minus the 2 cycles of delay. When the count reaches 14, the flag rises, and the writer still issues the writes in that cycle and the next, since it hasn't seen the flag yet. Those 2 writes fill the last 2 slots, and then the writer stops. In simulation with continuous writes and random reads, a threshold of 14 never attempted a write while full, and a threshold of 15 did.