Hamming code and error correction: How data repairs itself

In short: A Hamming code inserts check bits so that a single flipped bit error is not only detected but also located and corrected exactly.

In more detail: A parity bit only says “something is wrong”. Richard Hamming (1950) developed codes that additionally show which bit is wrong: then you can simply flip it back. This error correction (FEC) is in ECC RAM, hard drives, radio links and satellites.

In Depth

Idea of the Hamming code (7,4)

Of 7 bits 4 are data bits (d1–d4) and 3 check bits (p1–p3). The check bits sit at positions 1, 2 and 4 (powers of two); each checks the parity of a subset of positions:

Position:  1  2  3  4  5  6  7
Bit:      p1 p2 d1 p3 d2 d3 d4
p1 checks positions 1,3,5,7
p2 checks positions 2,3,6,7
p3 checks positions 4,5,6,7

On receipt the three parities are recomputed. Their result (the syndrome, read as a binary number) is the position of the faulty bit (000 = no error). That bit is inverted.

Worked example

Data 1011 (d1=1, d2=0, d3=1, d4=1). Check bits (even parity):

• 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 (p1 p2 d1 p3 d2 d3 d4) = 0 1 1 0 0 1 1. If bit 6 is flipped → 0110011 becomes 0110001. Recomputed: p1 check (1,3,5,7) = 0⊕1⊕0⊕1 = 0 ✓; p2 check (2,3,6,7) = 1⊕1⊕0⊕1 = 1 ✗; p3 check (4,5,6,7) = 0⊕0⊕0⊕1 = 1 ✗. Syndrome (p3 p2 p1) = 110 = 6 → bit 6 is wrong.

Properties

• Hamming distance 3: detects 2 bit errors, corrects 1 bit error. With an additional overall parity bit (SECDED: single error correction, double error detection) 2 errors are detected (not corrected).
• Overhead: 3 check bits for 4 data bits (75 %), much lower for longer words: 8 check bits for 64 data bits (ECC RAM: 72 bits per word).
• Limit: many errors in a row (bursts) need other codes.

Where error correction is used

• ECC memory (servers, workstations) against cosmic radiation and bit flips.
• Reed-Solomon: CDs, DVDs, QR codes, satellites, RAID 6.
• LDPC and turbo codes: Wi-Fi, 5G, SSDs, DVB.
• RAID parity (5/6) reconstructs failed drives.
• Error correction (FEC) in streaming and radio saves retransmissions. When correction is impossible, protocols (TCP) demand retransmission.

See also: Checksums, parity and CRC, RAID, QR code