Parity adds one bit and detects one error. Add three more bits to four data bits and you can correct one error. Add one more and you can correct one and detect two. Why do those particular numbers of extra bits buy those particular abilities? It is not a coincidence of clever design. It follows from one quantity: how far apart the valid code words are.
What decides how many errors a code can detect or correct?
The obvious answer is "more check bits, more protection". It points the right way but gives no way to predict what a given code can do, or to compare two codes with the same number of check bits. The answer is a property of the set of valid words, not of the number of bits: their minimum distance.
The Hamming distance between two words is the number of positions where they differ: 1011 and 1001 differ in one position, distance 1. A code is a set of valid words; its minimum distance d is the smallest distance between any two of them. If errors flip at most e bits, a received word lies within distance e of the word that was sent.
Detect: with fewer than d flips, a valid word cannot become another valid word, so the receiver sees an invalid word and knows something is wrong.
Correct: with at most ⌊(d−1)/2⌋ flips, the received word is still closer to the sent word than to any other valid word, so choosing the nearest valid word recovers it.
The model computes the minimum distance of five small codes by comparing every pair of code words, and prints what each can detect and correct.
"""Minimum Hamming distance of small codes, and what each can detect and correct.
The Hamming distance between two code words is the number of bit positions where
they differ. A code's minimum distance d is the smallest distance between any two
of its code words. It can detect any d - 1 errors and correct any (d - 1) // 2.
"""
from itertools import combinations, product
def dist(a, b):
return sum(x != y for x, y in zip(a, b))
def hamming74(d):
d1, d2, d3, d4 = d
p1, p2, p3 = d1 ^ d2 ^ d4, d1 ^ d3 ^ d4, d2 ^ d3 ^ d4
return (p1, p2, d1, p3, d2, d3, d4)
codes = {
"4 data bits, no check": [tuple(d) for d in product((0, 1), repeat=4)],
"4 data bits + parity": [tuple(d) + (sum(d) % 2,) for d in product((0, 1), repeat=4)],
"triple repetition of 1 bit": [(0, 0, 0), (1, 1, 1)],
"Hamming (7,4)": [hamming74(d) for d in product((0, 1), repeat=4)],
"Hamming (7,4) + overall parity (8,4)": [hamming74(d) + (sum(hamming74(d)) % 2,) for d in product((0, 1), repeat=4)],
}
for name, words in codes.items():
d = min(dist(a, b) for a, b in combinations(words, 2))
print(f"{name:38s} distance {d}: detects {d - 1}, corrects {(d - 1) // 2}")
assert min(dist(a, b) for a, b in combinations(codes["Hamming (7,4) + overall parity (8,4)"], 2)) == 4
print("PASS: adding check bits spreads code words apart; distance 4 gives correct-1, detect-2")It prints:
4 data bits, no check distance 1: detects 0, corrects 0
4 data bits + parity distance 2: detects 1, corrects 0
triple repetition of 1 bit distance 3: detects 2, corrects 1
Hamming (7,4) distance 3: detects 2, corrects 1
Hamming (7,4) + overall parity (8,4) distance 4: detects 3, corrects 1
PASS: adding check bits spreads code words apart; distance 4 gives correct-1, detect-2Raw data has distance 1: any flip makes another valid word, so nothing is detected. One parity bit gives distance 2. Hamming (7,4), with three check bits, reaches distance 3 and can correct one error, as can triple repetition, with far more overhead. Adding an overall parity bit gives distance 4. Used purely for detection, distance 4 detects any 3 errors; used to correct single errors, it can still detect every double error: that is SECDED (lesson 10.5).
Minimum distance | Use as | Example |
|---|---|---|
2 | Detect 1 | Parity |
3 | Correct 1, or detect 2 | Hamming codes |
4 | Correct 1 and detect 2 (SECDED), or detect 3 | Extended Hamming, memory ECC |
Larger | Correct several errors | Multi-bit ECC, Reed-Solomon (per symbol, lesson 10.6) |
Every step of distance costs check bits, and correction costs a decoder in the data path. Detection-only codes are cheaper and faster, which is why links that can ask for a resend use CRCs, and memories that cannot ask use ECC.
A designer (illustrative) used a distance-3 Hamming code to correct single errors in a memory and assumed it would also flag double errors. It cannot do both at once: with distance 3, a double error lands one flip away from a different valid word, and the decoder confidently "corrects" it to the wrong value. Silent corruption, from a code that was working exactly as designed. Adding the overall parity bit (distance 4) turned those into detected errors.
They differ in bits 6, 4 and 0 (counting from the right, bit 0 first): distance 3.
⌊(d − 1)/2⌋ ≥ 2, so d ≥ 5.
Hamming distance counts differing bits; a code's minimum distance d sets its power.
A code detects d − 1 errors or corrects ⌊(d − 1)/2⌋; distance 4 corrects 1 and detects 2.
A code pushed beyond its distance miscorrects silently; match distance to the error model.