The simplest algebraic error correction code — used in ECC memory, satellite telemetry, and the Voyager program. One parity bit per 4 data bits.
Hamming codes detect and correct single-bit errors in blocks of transmitted data. The (7,4) variant takes 4 data bits and adds 3 parity bits, creating a 7-bit codeword that can survive one flipped bit.
This is the simplest and most elegant error correction code. It was invented by Richard Hamming in 1950 at Bell Labs, after he grew frustrated with punched card readers that would abort on single-bit errors. His insight: add parity bits at positions that are powers of 2, each covering a specific subset of bit positions. The syndrome — the pattern of which parities disagree — directly points to the error's location.
Message HELLO — each character is 8 bits. Split into 4-bit nibbles:
H = 0100 1000 → nibble 1 = 0100, nibble 2 = 1000
Encode each nibble with the generator matrix G:
G = [I₄ | P]
1 0 0 0 | 1 1 0
0 1 0 0 | 1 0 1
0 0 1 0 | 0 1 1
0 0 0 1 | 1 1 1
codeword = data_bits · G
Parity-check matrix H:
1 1 0 1 | 1 0 0
1 0 1 1 | 0 1 0
0 1 1 1 | 0 0 1
To decode: compute syndrome s = H · rT where r is the received 7-bit block. If s = (0,0,0), no error. If s matches a column of H, that column index tells you which bit flipped.
def hamming_decode(block_7bit, H):
s = [0, 0, 0] # syndrome
for row in range(3):
for col in range(7):
s[row] ^= block_7bit[col] & H[row][col]
if s != [0, 0, 0]:
# Find which column of H matches s
for col in range(7):
if [H[r][col] for r in range(3)] == s:
block_7bit[col] ^= 1 # flip error
break
# Extract data bits (positions 0-3)
return block_7bit[:4]
| Level | What Happens | Time Estimate |
|---|---|---|
| 1 | Clean signal, no errors | <10s |
| 2-3 | 0-1 errors per block (correctable) | 20-60s |
| 4-5 | 1 guaranteed error per block, sometimes 2 | 30-90s |
| 6-7 | 1-2 errors per block, uncorrectable blocks need retransmission detection | 1-3m |