Hamming Error Correction

Hamming Error Correction

Mathematical Definition

All additions below are XOR, or addition modulo two in GF(2). Number the codeword from left to right, starting at 1. Insert the input digits d₁, d₂, d₃, d₄ at positions 3, 5, 6, 7. Parity bits at 1, 2, 4 make each corresponding group contain an even number of ones.

The parity-check matrix H has columns equal to the binary indices 1 through 7, with the least significant bit in its first row. For a received column vector r, the three-bit syndrome is Hr modulo two:

Here S uses ordinary integer addition to interpret the bits; its binary display is s₄s₂s₁. Every valid codeword satisfies Hc=0. Thus r=c+e gives Hr=He: a single error at position j produces exactly column j and therefore S=j. Different bit-order conventions give different displayed codewords, so the position convention matters.

Key Concepts

A worked transmission

For input 1011, the three parity digits are 0, 1, 0. The seven-bit word is 0110011 and its XOR is 0, so the extended word is 01100110. Flip position 5 to receive 01101110. Checks 1 and 4 fail, check 2 passes: the displayed syndrome is 101, or decimal 5. Overall parity is odd. Flipping position 5 restores the original word and extracting positions 3, 5, 6, 7 recovers 1011.

Parity bits are protected too. A flip at position 2 produces S=2. A flip of the extended overall bit produces S=0 but odd overall parity, identifying position 8 under the one-error assumption.

Why the extra bit detects two errors

Let P be the XOR of all eight received bits. With at most two errors, the receiver uses the following table. A pair of distinct errors among the first seven positions has S=i XOR j≠0. If one error is at position 8, S is the other position. Both cases have even P, so no correction is attempted. The receiver does not know the injected error count shown by the experiment. MIT SECDED decision table.

Code distance and rate

Hamming distance counts the positions where two equal-length words differ. The minimum distance between distinct Hamming(7,4) codewords is 3; extending with even overall parity raises it to 4. Radius-one error neighborhoods therefore do not overlap. A distance-4 code can detect up to three errors when used only for detection, but a decoder that also corrects single errors can confuse three errors with one. SECDED promises simultaneous single-error correction and double-error detection. It does not correct two errors. MIT: Hamming distance.

The code rate is payload length divided by transmitted length: 4/7 for the basic code and 4/8=1/2 for the extended code. Extra redundancy buys protection rather than compression. These are small teaching codes; the same parity-check idea supports larger payloads.

Counterexamples beyond the guarantee

In the plain seven-bit example, flipping positions 1 and 2 changes 0110011 into 1010011. The syndrome is 1 XOR 2=3. A single-error decoder flips position 3 and emits 1000011, whose data is 0011. Both errors were initially in parity bits, yet the attempted repair corrupts a data bit.

In the extended example, flips at 1, 2, 3 give 10000110: S=1 XOR 2 XOR 3=0 and P=1. The SECDED decoder assumes only bit 8 is wrong and emits 10000111, again decoding 0011. Flips at 1, 2, 3, 8 directly produce that different valid codeword with S=P=0. Passing every check therefore establishes code membership, not identity with the originally sent word.

The experiment intentionally allows arbitrary combinations. Its sender comparison labels such failures after the fact; the receiver algorithm cannot consult that comparison. Clearing flips resets only the channel. Changing data or code variant clears the channel as one state transition.

Historical Context

Richard W. Hamming published the construction in the Bell System Technical Journal in 1950, connecting parity constraints to detection, correction, and minimum separation between codewords. His original paper also explains adding an overall check for single-error correction with double-error detection. Hamming’s original paper.

Real-world Applications

• Memory reliability: ECC designs use redundant checks to recover isolated bit errors and flag selected multi-bit faults. A specific implementation’s guarantees depend on its code and fault model.
• Digital communication: An encoder trades bandwidth for protection against noise; a receiver needs an explicit policy for uncorrectable blocks.
• System design: Detection is useful only when the surrounding system handles the error. A decoder should not label a guessed or uncorrectable payload as verified data.

Related Concepts

• Null Space & Column Space — valid codewords form the null space of H over GF(2), rather than over the real numbers.
• Huffman Coding — reduces message length through compression; Hamming coding instead adds protective redundancy.
• Entropy & Information Theory — studies information, communication rates, and the limits of reliable transmission.