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
| Signal | Width | Role |
|---|---|---|
hidden_bug | 8 | input of each check |
Full specification
| Receiver | How it checks the 16 bits | It is safe when |
|---|---|---|
| A | One even-parity bit over all 16 bits. | it raises an alarm |
| B | A 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 |
| C | Bits 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 |
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