Build the odd-parity checker of a 9-bit memory word from unit-delay XOR cells, with at most four gate delays from any input.
Hardware context: The read path of a small memory that stores each byte with one odd-parity bit. Rebuild a chain of eight parity cells as a four-level tree with the right polarity.
A small memory stores each byte with one parity bit. It uses odd parity: every stored 9-bit word holds an odd number of 1s. On every read, a checker raises err when the word holds an even number of 1s.
This is an Optimize problem. The starter is a chain of eight cells. It is correct, but a change of d[0] takes eight gate delays to reach err. The read path allows four.
Rebuild the checker from the cells of cells.sv so that err settles within four gate delays after any single bit changes.
Signals in the Timeline
| Signal | Width | Role |
|---|---|---|
word | 9 | input of each check |
Full specification
// cells.sv: the unit-delay cell library (read-only).
// Every cell takes 1 time unit, whatever its fan-in. Ports are (y, inputs...): output first.
// Each cell adds 1 to the bench's cell counter. While the bench sets poison to 1, every cell output is x.
module INV (output wire y, input wire a); wire g; not #1 (g, a); assign y = tb.poison ? 1'bx : g; initial tb.cells++; always @(tb.recount) tb.cells++; endmodule
module AND2 (output wire y, input wire a, b); wire g; and #1 (g, a, b); assign y = tb.poison ? 1'bx : g; initial tb.cells++; always @(tb.recount) tb.cells++; endmodule
module AND3 (output wire y, input wire a, b, c); wire g; and #1 (g, a, b, c); assign y = tb.poison ? 1'bx : g; initial tb.cells++; always @(tb.recount) tb.cells++; endmodule
module AND4 (output wire y, input wire a, b, c, d); wire g; and #1 (g, a, b, c, d); assign y = tb.poison ? 1'bx : g; initial tb.cells++; always @(tb.recount) tb.cells++; endmodule
module AND5 (output wire y, input wire a, b, c, d, e); wire g; and #1 (g, a, b, c, d, e); assign y = tb.poison ? 1'bx : g; initial tb.cells++; always @(tb.recount) tb.cells++; endmodule
module OR2 (output wire y, input wire a, b); wire g; or #1 (g, a, b); assign y = tb.poison ? 1'bx : g; initial tb.cells++; always @(tb.recount) tb.cells++; endmodule
module OR3 (output wire y, input wire a, b, c); wire g; or #1 (g, a, b, c); assign y = tb.poison ? 1'bx : g; initial tb.cells++; always @(tb.recount) tb.cells++; endmodule
module OR4 (output wire y, input wire a, b, c, d); wire g; or #1 (g, a, b, c, d); assign y = tb.poison ? 1'bx : g; initial tb.cells++; always @(tb.recount) tb.cells++; endmodule
module OR5 (output wire y, input wire a, b, c, d, e); wire g; or #1 (g, a, b, c, d, e); assign y = tb.poison ? 1'bx : g; initial tb.cells++; always @(tb.recount) tb.cells++; endmodule
module NAND2 (output wire y, input wire a, b); wire g; nand #1 (g, a, b); assign y = tb.poison ? 1'bx : g; initial tb.cells++; always @(tb.recount) tb.cells++; endmodule
module NOR2 (output wire y, input wire a, b); wire g; nor #1 (g, a, b); assign y = tb.poison ? 1'bx : g; initial tb.cells++; always @(tb.recount) tb.cells++; endmodule
module XOR2 (output wire y, input wire a, b); wire g; xor #1 (g, a, b); assign y = tb.poison ? 1'bx : g; initial tb.cells++; always @(tb.recount) tb.cells++; endmodule
module XNOR2 (output wire y, input wire a, b); wire g; xnor #1 (g, a, b); assign y = tb.poison ? 1'bx : g; initial tb.cells++; always @(tb.recount) tb.cells++; endmodule
module parity9 (
input logic [8:0] d, // eight data bits and one parity bit, as stored
output wire err // 1 when d holds an even number of 1s
);
// your cells
endmodule
| Rule | Detail |
|---|---|
| Function | err = 1 when d holds an even number of 1s, including zero. err = 0 when the count is odd. |
| Delay | Every cell takes 1 ns. After one bit of d changes, err must stop changing within 4 ns. |
| Cells | Use cells of cells.sv only: between 8 and 10 of them. An XOR of nine bits needs at least eight two-input cells. |
| Cells only | The check refuses assign, always, initial, gate primitives, operators and hierarchical names before it runs. It also forces every cell output to x, and err must follow. |
Each check sets a word, waits and flips one bit. It reports err, the gate delays over the budget, and the two rules above.
Examples
Example 1
One Bit Set in an Empty Word- Input
d = 000000000, then d[0] flips
- Output
err = 0, gate_delays_over_budget = 0, err_moved_with_no_delay = no, cell_count_outside_8_to_10 = no
From 000000000, d[0] flips. The word holds one 1, an odd count, so err is 0. The check also times how long err took.
Example 2
The Parity Bit Itself Flips- Input
d = 000000001, then d[8] flips
- Output
err = 1, gate_delays_over_budget = 0, err_moved_with_no_delay = no, cell_count_outside_8_to_10 = no
From 000000001, d[8] flips. Now two bits are 1, an even count, so err must be 1.
Example 3
A Bit Flips in a Word with Two 1s- Input
d = 100000000, then d[3] flips
- Output
err = 1, gate_delays_over_budget = 0, err_moved_with_no_delay = no, cell_count_outside_8_to_10 = no
The word 100000000 holds one 1. After d[3] flips it holds two, an even count, so err is 1.
Constraints and Contract
- Keep the module name parity9 and its two ports.
- Use cell instances only: no operators, assign, always blocks or gate primitives.
Hints
Hint 1
XOR is associative, so you may group the nine bits in any order. Pair them up instead of adding one bit per cell.
Hint 2
Eight bits paired, then paired again, then once more, take three levels. The ninth bit joins at the fourth level.
Hint 3
The last cell decides the polarity. The XOR of all nine bits is 1 for an odd count, so the checker needs its complement.
What the grader checks: The check flips each of the nine bits at least once, from twelve different words, and times err after each flip. It counts cells through the library, and forces every cell output to x to confirm that err comes from a cell.
13 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