G1.9.1 Hamming(7,4) Corrector

MediumImplementIcarus · browser samples / server checksReview the topic

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

SignalWidthRole
script70input of each check
Full specification
The module (keep the name and the ports)
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 bitCovers 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

Report a problem with this page

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

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
Expected 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.

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

Icarus · browser samples / server checks