Hamming Code

Hamming Code: The First Practical Error-Correcting Code

Richard Hamming invented his famous code in 1950 while working at Bell Labs, frustrated that the relay computers of his era would stop and wait for human intervention whenever a single bit error occurred. He asked a simple but profound question: "If the machine can detect an error, why can't it locate and correct the error?" His answer — the Hamming code — became the foundation of all error-correcting codes and remains in widespread use today in computer memory systems.

The Key Insight: Error Position Through Parity

Think of it this way: imagine you have 8 people standing in a line, and one of them is lying about their number. You could ask "Is the liar in the first half or second half?" to narrow down the position. Then "Is the liar in positions 1-2 or 3-4 of that half?" With just 3 yes/no questions, you can identify which of 8 people is the liar.

Hamming codes work identically: r parity check bits can identify which of up to 2^r - 1 positions contains an error. Each parity bit checks a specific subset of positions, and the pattern of parity failures (the syndrome) uniquely identifies the error location.

Constructing the (7,4) Hamming Code

The most basic Hamming code encodes 4 data bits into 7 total bits (3 parity bits). The parity bits are placed at positions that are powers of 2 (positions 1, 2, 4):

Position mapping:

Each parity bit checks positions whose binary representation has a 1 in the corresponding bit:

• P1 (position 1 = ...1): Checks positions 1, 3, 5, 7 (all odd positions)
• P2 (position 2 = ..1.): Checks positions 2, 3, 6, 7
• P3 (position 4 = .1..): Checks positions 4, 5, 6, 7

Encoding example — Data = 1011 (D1=1, D2=0, D3=1, D4=1):

• P1 = D1 ⊕ D2 ⊕ D4 = 1 ⊕ 0 ⊕ 1 = 0
• P2 = D1 ⊕ D3 ⊕ D4 = 1 ⊕ 1 ⊕ 1 = 1
• P3 = D2 ⊕ D3 ⊕ D4 = 0 ⊕ 1 ⊕ 1 = 0

Codeword: 0 1 1 0 0 1 1 (positions 1-7)

Syndrome Decoding: Finding the Error

When the receiver gets a 7-bit word, it computes the syndrome — a binary number indicating the error position:

Syndrome computation:

• S1 = P1 ⊕ D1 ⊕ D2 ⊕ D4 (should be 0 if no error in positions 1,3,5,7)
• S2 = P2 ⊕ D1 ⊕ D3 ⊕ D4 (should be 0 if no error in positions 2,3,6,7)
• S3 = P3 ⊕ D2 ⊕ D3 ⊕ D4 (should be 0 if no error in positions 4,5,6,7)

Syndrome = (S3, S2, S1):

• 000 → No error
• 001 → Error in position 1
• 010 → Error in position 2
• 011 → Error in position 3
• 100 → Error in position 4
• 101 → Error in position 5
• 110 → Error in position 6
• 111 → Error in position 7

Correction: Simply flip the bit at the position indicated by the syndrome!

Example: Received word 0 1 1 0 1 1 1 (position 5 corrupted: should be 0):

• S1 = 0⊕1⊕1⊕1 = 1
• S2 = 1⊕1⊕1⊕1 = 0
• S3 = 0⊕1⊕1⊕1 = 1
• Syndrome = 101 (binary) = 5 → Error at position 5!
• Correction: Flip bit 5: 0 1 1 0 0 1 1 ← Correct!

Matrix Formulation

The encoding and decoding can be expressed as matrix operations over GF(2):

Parity check matrix H:

Syndrome: s = H × r^T (where r is the received vector)

If s = 0, no error. If s ≠ 0, s points to the error position.

Generator matrix G: Maps 4 data bits to 7-bit codeword.

General Hamming Codes (2^r - 1, 2^r - 1 - r)

The (7,4) code is just one member of the Hamming family:

As r increases, the code rate approaches 1 (very efficient), but correction capability remains limited to single errors. The minimum distance is always dmin = 3.

SEC-DED: Single Error Correction, Double Error Detection

Adding one more parity bit (overall parity of all bits) extends Hamming code to detect double errors:

• Single error: Syndrome ≠ 0 AND overall parity wrong → Correct the error
• Double error: Syndrome ≠ 0 AND overall parity correct → Two errors detected (cannot correct)
• No error: Syndrome = 0 AND overall parity correct → Data is clean

The (8,4) extended Hamming code has dmin = 4, enabling correction of 1 error and detection of 2 errors simultaneously.

Application: ECC Memory

The most widespread application of Hamming codes today is in ECC (Error-Correcting Code) memory used in servers and workstations:

• Each 64-bit data word is stored with 8 additional ECC bits (72 bits total)
• Uses SEC-DED Hamming code
• Single-bit errors (from cosmic rays, alpha particles, or aging cells) are silently corrected
• Double-bit errors are detected and flagged (system alert)
• Essential for server reliability — a typical server experiences several single-bit errors per day

Without ECC memory, these errors would corrupt data silently, potentially causing crashes, data loss, or security vulnerabilities.

Limitations and Beyond

Hamming code limitations:

• Corrects only 1 error per codeword
• Cannot handle burst errors (multiple adjacent corrupted bits)
• Minimum distance fixed at 3 (or 4 for extended) — no flexibility

For stronger correction, use:

• BCH codes (correct multiple errors, tunable)
• Reed-Solomon codes (correct burst errors via symbol-level operation)
• LDPC codes (near-Shannon-limit performance)

Key Takeaways

1. Hamming codes use r parity bits to identify and correct single-bit errors among 2^r - 1 total bit positions.
2. The syndrome (pattern of parity check results) directly indicates the error position in binary.
3. Extended Hamming (SEC-DED) adds one overall parity bit to also detect double-bit errors.
4. Hamming codes are used universally in ECC computer memory, silently correcting cosmic-ray-induced bit flips.
5. Code rate improves with larger block size (approaching 1.0) while maintaining single-error correction.
6. For stronger error correction capabilities, more powerful codes (BCH, Reed-Solomon, LDPC) build upon Hamming's foundational principles.