G2.7.1 A 9-bit Parity Tree in Four Levels

MediumOptimizeIcarus · browser samples / server checksReview the topic

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

SignalWidthRole
word9input of each check
Full specification
cells.sv: the unit-delay cell library (read-only)
// 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
The module you write (keep the name and the ports)
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
RuleDetail
Functionerr = 1 when d holds an even number of 1s, including zero. err = 0 when the count is odd.
DelayEvery cell takes 1 ns. After one bit of d changes, err must stop changing within 4 ns.
CellsUse cells of cells.sv only: between 8 and 10 of them. An XOR of nine bits needs at least eight two-input cells.
Cells onlyThe 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

Report a problem with this page

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

One Bit Set in an Empty Word

Input
d = 000000000, then d[0] flips
Expected 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.

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

Icarus · browser samples / server checks