G8.2.1 A Counter-Based FIFO

MediumImplementIcarus · browser samples / server checksReview the topic

Build an eight-word FIFO from two pointers and a word counter, with full and empty flags that are never wrong.

Hardware context: An eight-word FIFO between a bursty sensor and a slower processor. Build the FIFO from two pointers and a counter, correct at full, at empty and when both offers arrive together.

A sensor sends bytes in short bursts. The processor reads them when it has time. A FIFO between the two keeps the bytes in order: the first byte in is the first byte out.

This is an Implement problem. Write fifo8: eight words of 8 bits, a write pointer, a read pointer and a counter of the words held.

A push stores wdata when the FIFO is not full. A pop removes the oldest word when the FIFO is not empty. The port rdata shows the oldest word with no clock.

Each offer is decided on the flags before the edge. A full FIFO that sees a push and a pop together takes only the pop. An empty FIFO takes only the push.

Signals in the Timeline

SignalWidthRole
controls72input of each check
values192input of each check
Full specification
The module you write (keep the name and the ports)
module fifo8 (
  input  logic       clk,
  input  logic       rst,      // synchronous, active high: empties the FIFO
  input  logic       push,     // 1: store wdata at the next edge, if the FIFO is not full
  input  logic [7:0] wdata,
  input  logic       pop,      // 1: remove the oldest word at the next edge, if the FIFO is not empty
  output logic [7:0] rdata,    // the oldest word (valid while empty is 0)
  output logic       full,
  output logic       empty,
  output logic [3:0] count     // words held: 0 to 8
);
  // your design
endmodule
RuleDefinition
Push takenAt a rising edge with push = 1 and full = 0 before the edge. The word goes in behind the newest word.
Pop takenAt a rising edge with pop = 1 and empty = 0 before the edge. The oldest word leaves.
Both in one cycleEach one is decided on its own flag. When both are taken, count stays the same.
countThe number of words held, from 0 to 8, with no delay.
full and emptyfull is 1 when count is 8. empty is 1 when count is 0.
rdataThe oldest word, whenever empty is 0. The value does not matter while empty is 1.
ResetAt a rising edge with rst = 1 the FIFO becomes empty. Reset wins over push and pop.

Each test starts with one reset edge and then runs 24 cycles of offers. One nanosecond after every edge it compares count, full and empty with the expected values. When the FIFO should hold a word, it also compares rdata.

The result names the cycles with a difference in error_cycles. It also counts the pushes and pops the FIFO took and reports the last value of count.

Examples

Example 1

Three Words in, Three Words Out
Input
push 11, push 22, push 33, pop, pop, pop, then idle
Output
error_cycles = {}, pushes_taken = 3, pops_taken = 3, count_at_end = 0, depth = 8

The words 11, 22 and 33 go in. While they wait, rdata shows 11, the oldest. Three pops return 11, 22 and 33 in that order, and the FIFO is empty again.

Example 2

Fill to Full, One Push Too Many
Input
push 30, push 31, push 32, push 33, push 34, push 35, push 36, push 37, push ee, pop, pop, pop, pop, pop, pop, pop, pop, pop, then idle
Output
error_cycles = {}, pushes_taken = 8, pops_taken = 8, count_at_end = 0, depth = 8

Eight pushes fill the FIFO and full becomes 1. The ninth push, of ee, is refused: eight pushes are taken, not nine. The drain returns 30 to 37. The last pop finds an empty FIFO and is refused too.

Example 3

Push and Pop in the Same Cycle
Input
push 41, push 42, push 43 + pop, push 44 + pop, push 45 + pop, pop, pop, then idle
Output
error_cycles = {}, pushes_taken = 5, pops_taken = 5, count_at_end = 0, depth = 8

With two words held, three cycles push and pop together. Each cycle one word leaves and one arrives, so count stays at 2. Two more pops empty the FIFO: five pushes and five pops are taken in all.

Constraints and Contract

  • Offers change after an edge and are known 0/1 values. wdata may hold any byte.
  • Keep the module name and the ports.

Hints

Hint 1

Three registers hold the state: the write pointer, the read pointer and the count. Write down what each one does on a push, on a pop and on both.

Hint 2

The pointers are equal when the FIFO is empty and also when it is full. Take full and empty from the count.

Hint 3

Make two wires first. One is a push that is taken: push and not full. The other is a pop that is taken: pop and not empty. The count goes up on a taken push alone and down on a taken pop alone. The storage write and each pointer move use the same two wires.

What the grader checks: Eight directed and ten seeded scripts of 24 cycles run on the FIFO. They cover full, empty, both offers together, pointer wrap and reset. After every edge count, full, empty and the oldest word are compared with a queue model written in JavaScript. Other depths and widths, and rdata while the FIFO is empty, are outside this problem.

18 checks on Icarus · browser samples / server checks. Run the examples first, then check the full regression. Full checks use the server judge. Downloads contain public samples only. A passing result establishes the tested cases, not a proof for all possible inputs.

See all 1 steps and the final capstone

Report a problem with this page

Your code SystemVerilogSaved locally
Ln 1, Col 1Tab indents · Ctrl/⌘ + Enter runs samples
Not run yet

Three Words in, Three Words Out

Input
push 11, push 22, push 33, pop, pop, pop, then idle
Expected output
error_cycles = {}, pushes_taken = 3, pops_taken = 3, count_at_end = 0, depth = 8

The words 11, 22 and 33 go in. While they wait, rdata shows 11, the oldest. Three pops return 11, 22 and 33 in that order, and the FIFO is empty again.

Run samples executes all 3 public checks. Check all tests runs 18 checks on the server.

Icarus · browser samples / server checks