G1.9.2 Which Errors Slip Past Parity

MediumBreak ItIcarus · browser samples / server checks3 hidden designsReview the topic

Find error patterns that slip past single parity, two-dimensional parity and a Hamming corrector, with at most three patterns.

Hardware context: The receiver of a noisy sensor link and three candidate error checks for a new link. Find error patterns that beat single parity, two-dimensional parity and a Hamming single-error corrector.

A link designer must choose between three error checks. Before choosing, she wants to see each one fail. Your job is to find the error patterns that beat them.

This is a Break it problem. In the task stimulus, call try_error once for each error pattern. A pattern is a 16-bit word with a 1 for every flipped bit. You may try at most three patterns, and each must flip at least one bit.

Every pattern goes to three receivers. A receiver is beaten when the pattern leaves wrong data and no alarm. Beat all three.

Signals in the Timeline

SignalWidthRole
hidden_bug8input of each check
Full specification
ReceiverHow it checks the 16 bitsIt is safe when
AOne even-parity bit over all 16 bits.it raises an alarm
BA 4 x 4 block: bit 4i + j is row i, column j. One parity bit per row and per column.some row or column fails
CBits 6 to 0 are one Hamming(7,4) word, bit k at position k + 1. It flips the bit the syndrome names. It ignores bits 15 to 7.the corrected data bits (positions 3, 5, 6, 7) are right
What you write
task automatic stimulus();
  try_error(16'h0001);   // one call per error pattern
endtask

Receivers A and B keep their check bits outside the 16 bits, so only data bits flip. Receiver C's whole codeword is bits 6 to 0: its parity bits (positions 1, 2 and 4) can flip too.

Examples

Run samples checks your input rules and any explicitly public sample faults. Submit runs every hidden faulty copy on the server. The worked bug examples below describe Submit results.

Example 1

Your Patterns Follow the Rules
Input
stimulus() makes 1 call with a nonzero pattern
Output
inputs_legal = yes

One pattern is within the limit of three, and it flips at least one bit.

Example 2

Receiver A Is Beaten
Input
Your patterns, run on receiver A
Output
caught = yes

Receiver A counts as beaten when one of your patterns leaves it with wrong data and no alarm. The expected result is caught = 1.

Example 3

Receiver B Is Beaten
Input
Your patterns, run on receiver B
Output
caught = yes

The same test for the row and column parity of receiver B. Every receiver needs its own caught = 1.

Constraints and Contract

  • Call try_error at most 3 times inside stimulus.
  • Every pattern flips at least one bit: 16'h0000 is not an error.

Hints

Hint 1

A single flipped bit beats none of them. Count how many flips each receiver can always handle.

Hint 2

Receiver A misses any even number of flips. Receiver B misses flips that pair up in every row and every column. Receiver C misses a pattern on bits 6 to 0 whose syndrome is 0 or names the wrong bit.

Hint 3

Receiver B misses flips that pair up in every row and column, such as a rectangle. Receiver C keeps its data at positions 3, 5, 6 and 7.

What the grader checks: Your patterns are run through the perfect receiver and the three real ones. A receiver counts as beaten when one of your patterns leaves it with wrong data and no alarm.

4 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 2 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

Your Patterns Follow the Rules

Input
stimulus() makes 1 call with a nonzero pattern
Expected output
inputs_legal = yes

One pattern is within the limit of three, and it flips at least one bit.

Run samples executes all 1 public checks. Check all tests runs 4 checks on the server.

Icarus · browser samples / server checks