17 / 24 · Concept
FIFO empty, full, and simultaneous transfers
Separate occupancy from pointers and specify boundary push/pop behavior.
Lessons are free to read. Enroll to save your learning progress.
A queue preserves acceptance order
A FIFO delivers the oldest accepted item first. Its read pointer identifies the oldest entry and its write pointer the next storage location. Equal pointers alone cannot distinguish empty from full, so this design keeps an occupancy count. For depth four, pointers need two bits but count needs three to represent zero through four. Store tags together with data.
Our registered FIFO has no empty-queue fall-through. Output-valid is count>0 and pop is output-valid AND output-ready. Input-ready is count<depth OR pop, allowing replacement when a full queue simultaneously delivers its head. Push is input-valid AND input-ready. Next count is count+push-pop. Two separate assignments that increment and decrement count can mishandle simultaneous transfers; use one combined update or explicit cases.
| Old count | Conditions | push | pop | New count |
|---|---|---|---|---|
| 0 | Input and ready sink | 1 | 0 | 1 |
| 1 | Input and ready sink | 1 | 1 | 1 |
| 4 | Input and stalled sink | 0 | 0 | 4 |
| 4 | Input and ready sink | 1 | 1 | 4 |
An empty queue cannot pop merely because the sink is ready. Its new input first transfers at the next edge. A full queue [A,B,C,D] simultaneously consuming A and accepting E becomes [B,C,D,E], still full. Verify underlying memory behavior when reading and writing the same physical position.
Four-entry FIFO. Initially empty; read and write pointers are 0. Accept pop when nonempty. Accept push when space is available or a pop is accepted on the same edge.
Power-of-two depths wrap naturally in pointer bits. Depth three needs an explicit transition from position two to zero. Test wrap, last-item removal, and full replacement separately.
A depth-four empty queue absorbs only four items during a five-cycle sink stall. The fifth input must wait. A source that cannot stall needs more capacity or a defined loss policy. No finite FIFO fixes permanently slower consumption. Check 0≤count≤depth, accepted-delivered=count, and tag ordering; counts alone cannot expose reordering.
Try it yourself
For depth two and queue [tag3,tag4], input tag5 is offered with out-ready=1. Find push, pop, next count, and next queue. Would tag5 pop immediately if the queue were empty?
Read the explanation
Pop=1 makes input-ready high despite full occupancy, so push=1. Next count remains two and the queue is [tag4,tag5]. An empty queue has out-valid=0, so tag5 is stored and cannot pop until a later edge.