Compute the syndrome of a received Hamming(7,4) word, flip the bit it names, and return the corrected data.
Hardware context: The receiver of a noisy sensor link and three candidate error checks for a new link. Correct a single flipped bit in a Hamming(7,4) word and return the data.
A sensor sends four data bits at a time over a noisy wire, coded as Hamming(7,4). The receiver must repair any single flipped bit before the data reaches the controller.
This is an Implement problem. Write ham74_fix. The input r is a received word with positions 1 to 7, as in the lesson. Parity sits at 1, 2 and 4, and data at 3, 5, 6 and 7. At most one bit of r is flipped.
syn is the syndrome. fixed is 1 when a bit was flipped back, whether it was a data bit or a parity bit. data holds the corrected bits of positions 3, 5, 6 and 7, with position 3 as the most significant bit.
The check applies ten words, one per nanosecond, and records the three outputs after each. Between them the cases try every codeword with no error and with each single error.
Signals in the Timeline
| Signal | Width | Role |
|---|---|---|
script | 70 | input of each check |
Full specification
module ham74_fix (
input logic [7:1] r, // the received word: r[p] is position p
output logic [2:0] syn, // the syndrome: 0, or the position of the flipped bit
output logic fixed, // 1 when a bit was flipped back
output logic [3:0] data // the corrected data: positions 3, 5, 6, 7, most significant first
);
// your design
endmodule
| Check bit | Covers positions |
|---|---|
| syn[0] | 1, 3, 5, 7 |
| syn[1] | 2, 3, 6, 7 |
| syn[2] | 4, 5, 6, 7 |
The result fields are syn_step0, fixed_step0 and data_step0 for the first word, up to the same names with step9.
Examples
Example 1
The Data 0000 and 0001- Input
r 0000000; r 0000001; r 0000010; r 0000100; r 0001000; r 0010000; r 0100000; r 1000000; r 1001011; r 1001010
- Output
syn_step0 = 0, fixed_step0 = no, data_step0 = 'b0000, syn_step1 = 1, fixed_step1 = yes, data_step1 = 'b0000, syn_step2 = 2, fixed_step2 = yes, data_step2 = 'b0000, syn_step3 = 3, fixed_step3 = yes, data_step3 = 'b0000, syn_step4 = 4, fixed_step4 = yes, data_step4 = 'b0000, syn_step5 = 5, fixed_step5 = yes, data_step5 = 'b0000, syn_step6 = 6, fixed_step6 = yes, data_step6 = 'b0000, syn_step7 = 7, fixed_step7 = yes, data_step7 = 'b0000, syn_step8 = 0, fixed_step8 = no, data_step8 = 'b0001, syn_step9 = 1, fixed_step9 = yes, data_step9 = 'b0001
The first eight words are the codeword of 0000 with no error and then with each of the seven single errors. The syndrome counts 0 to 7 and the data is always 0000.
Example 2
The Data 0001 and 0010- Input
r 1001001; r 1001111; r 1000011; r 1011011; r 1101011; r 0001011; r 0101010; r 0101011; r 0101000; r 0101110
- Output
syn_step0 = 2, fixed_step0 = yes, data_step0 = 'b0001, syn_step1 = 3, fixed_step1 = yes, data_step1 = 'b0001, syn_step2 = 4, fixed_step2 = yes, data_step2 = 'b0001, syn_step3 = 5, fixed_step3 = yes, data_step3 = 'b0001, syn_step4 = 6, fixed_step4 = yes, data_step4 = 'b0001, syn_step5 = 7, fixed_step5 = yes, data_step5 = 'b0001, syn_step6 = 0, fixed_step6 = no, data_step6 = 'b0010, syn_step7 = 1, fixed_step7 = yes, data_step7 = 'b0010, syn_step8 = 2, fixed_step8 = yes, data_step8 = 'b0010, syn_step9 = 3, fixed_step9 = yes, data_step9 = 'b0010
The same pattern for the next data words. A flipped data bit changes the received data, so data must come from the corrected word.
Example 3
The Data 0010 and 0011- Input
r 0100010; r 0111010; r 0001010; r 1101010; r 1100001; r 1100000; r 1100011; r 1100101; r 1101001; r 1110001
- Output
syn_step0 = 4, fixed_step0 = yes, data_step0 = 'b0010, syn_step1 = 5, fixed_step1 = yes, data_step1 = 'b0010, syn_step2 = 6, fixed_step2 = yes, data_step2 = 'b0010, syn_step3 = 7, fixed_step3 = yes, data_step3 = 'b0010, syn_step4 = 0, fixed_step4 = no, data_step4 = 'b0011, syn_step5 = 1, fixed_step5 = yes, data_step5 = 'b0011, syn_step6 = 2, fixed_step6 = yes, data_step6 = 'b0011, syn_step7 = 3, fixed_step7 = yes, data_step7 = 'b0011, syn_step8 = 4, fixed_step8 = yes, data_step8 = 'b0011, syn_step9 = 5, fixed_step9 = yes, data_step9 = 'b0011
Each word with an error gives fixed = 1. That includes errors in positions 1, 2 and 4, which hold parity bits.
Constraints and Contract
- Inputs are known 0/1 values with at most one flipped bit. Each word is held for one nanosecond and the outputs are sampled at its end.
- Keep the module name and the ports. The design is combinational.
Hints
Hint 1
Each syndrome bit is the XOR of the four received bits its check covers. The table lists them.
Hint 2
The syndrome is a position from 1 to 7, or 0 for no error. Make a copy of r and invert the bit at that position.
Hint 3
Read the data from the corrected copy, not from r. A flipped parity bit leaves the data as it was, but it still counts as fixed.
What the grader checks: Thirteen cases of ten words cover all 16 codewords, with no error and with each of the 7 single errors. All three outputs are compared after every word with a model that finds the nearest codeword. Two or more flipped bits are outside this problem.
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 2 steps and the final capstone