Hamming codes

The formula

Hamming distance between two equal-length bit strings:

d(x, y) = number of positions where x and y differ

Reading: 1011001 and 1001101 differ in positions 3 and 5, so their Hamming distance is 2 — it counts the minimum number of bit flips to turn one word into the other.

What minimum distance buys you:

detect up to  d_min − 1  errors
correct up to ⌊(d_min − 1)/2⌋  errors

Reading: a code whose codewords all sit at least d_min flips apart can absorb that many hits before a corrupted word looks closer to the wrong codeword than the right one. Hamming codes have d_min = 3: correct one error, or detect two — not both at once.

The family, one code for each integer r ≥ 2:

block length  n = 2^r − 1        data bits  k = 2^r − 1 − r

Reading: r parity bits protect a block of 2^r − 1 total bits. r = 3 gives the classic Hamming(7,4); r = 5 gives (31,26); r = 6 gives (63,57). The overhead fraction r/n shrinks as blocks grow.

Hamming(7,4) explicitly, with parity bits p₁p₂p₄ at positions 1, 2, 4 and data bits d₁–d₄ at positions 3, 5, 6, 7:

p₁ = d₁ ⊕ d₂ ⊕ d₄        p₂ = d₁ ⊕ d₃ ⊕ d₄        p₄ = d₂ ⊕ d₃ ⊕ d₄

Reading: each parity bit covers the positions whose binary index contains that parity bit's position. On receive, recompute all three checks; the pattern of failures, read as a binary number, is the syndrome:

s = (c₄ c₂ c₁)₂   →   s = 0 means clean, otherwise s is the position of the flipped bit

Reading: the code is its own error address decoder. Syndrome 6 means position 6 is wrong — XOR it with 1 and move on.

The sphere-packing identity that makes Hamming codes "perfect":

2^k · (n + 1) = 2^n        for (7,4):  16 · 8 = 128 = 2⁷

Reading: every possible received word is either a codeword or exactly one flip away from exactly one codeword. Zero wasted patterns — no single-error-correcting code of that length can carry more data.

Where you meet it

The ECC server in your data acquisition rack. Standard ECC DIMMs store 72 bits per 64-bit word — the extra 8 check bits implement a SECDED code, single-error-correcting and double-error-detecting ^[7]. When the BMC log on a test-stand server shows "correctable memory errors," that is a Hamming-class code silently fixing bit flips mid-acquisition instead of corrupting your run.
Spacecraft memory at a design review. Cassini's solid-state recorders held 2.5 gigabits of commercial DRAM behind error-correcting hardware, and during the first 2.5 years of flight the telemetry showed a nearly constant rate of about 280 corrected single-bit errors per day from the galactic cosmic ray background ^[7]^[8]. The review-board question is never whether bits will flip up there — it's whether your scrub rate keeps up.
FPGA and flash controller datasheets. Block RAM in radiation-adjacent FPGA designs and the spare bytes in NAND flash pages routinely carry Hamming or extended-Hamming protection; the datasheet line "SECDED" is telling you exactly which code and exactly what it can and cannot fix.
Anywhere "Hamming distance" shows up as a spec. Command words in a safety-critical protocol are often assigned a minimum mutual Hamming distance of 4 or more, so no single (or double) bit hit on the bus turns ARM into FIRE.

How it works

The trick is putting parity bits at the power-of-two positions 1, 2, 4, 8, … and having parity bit p cover every position whose binary index includes p. A flip at position 6 (binary 110) fails exactly the checks at positions 4 and 2, so the syndrome reads 110 — the error announces its own address. That is the whole mechanism; everything else is bookkeeping.

The behavior engineers trip over: a plain Hamming code fed two errors does not throw up its hands. It computes a nonzero syndrome, confidently "corrects" a third, innocent bit, and hands you a codeword that is now three flips from the truth. Single-error correction actively makes double errors worse. That is why real hardware uses the extended code — one more overall parity bit raises d_min from 3 to 4 and gives SECDED: syndrome nonzero with overall parity failed means one error, fix it; syndrome nonzero with overall parity clean means two errors, flag the word and do not touch it. The (72,64) code in ECC RAM is exactly this scheme (usually a Hsiao variant, an equivalent code rearranged for cheaper, faster check logic ^[7]).

SECDED per word only holds if errors don't accumulate. A bit that flipped in January and a second flip in the same word in June looks like a double error — or worse, a miscorrection — even though each event was single. That is why spacecraft and servers run memory scrubbing: background reads that sweep every word, correct singles while they are still single, and write the cleaned word back. Scrub interval is a design number, set by the expected upset rate.

Limits of validity: the Hamming construction assumes errors land independently, one bit here, one bit there. A burst — connector chatter, a scratch across a flash block, an SEU that clips two adjacent cells — puts multiple errors in one word and blows straight past d_min = 3. The standard fixes are interleaving (spread each codeword's bits across physical locations so a burst hits many words once instead of one word many times) or a stronger code entirely; Reed–Solomon and BCH exist precisely because Hamming stops at one. And for pure error detection on serial links, a CRC beats a Hamming code at the same overhead — Hamming's premium buys correction, and if you can just ask for a retransmit, you don't need it.

One vocabulary trap: "Hamming distance" is a general-purpose metric — people apply it to strings, feature vectors, and fuzzy-hash comparisons — and it long ago escaped coding theory. When a colleague says two configurations are "Hamming distance 3 apart," they owe you the alphabet and the encoding before the number means anything.

History

In 1947 Richard Hamming was sharing time on Bell Labs' relay computers, which ran his problems unattended over the weekend. The machines could detect an error — and, with nobody there to intervene, would drop the job. He came in one Monday to find a run had died early with nothing to show for it, and asked the obvious engineer's question: if the machine can detect an error, why can't it locate and correct it? ^[2]^[3] He worked out the answer — the parity-bits-at-powers-of-two construction — and wrote it up internally, but Bell Labs sat on publication while the patent was filed ^[4]^[6]. The code leaked into the literature anyway, in the best possible way: Claude Shannon's 1948 A Mathematical Theory of Communication closes its noisy-channel discussion with a seven-symbol, rate-4/7 example of perfect error correction, credited to "a method due to R. Hamming" — two years before Hamming's own paper existed ^[5]^[1]. Hamming finally published "Error Detecting and Error Correcting Codes" in the April 1950 Bell System Technical Journal, and the field of coding theory dates itself from that paper ^[2]^[4]. He stayed at Bell Labs until 1976, then taught at the Naval Postgraduate School in Monterey until his death in 1998; the 1968 Turing Award — he was its third recipient — cited the error-correcting codes by name ^[2]^[3]^[6].

Related tools

/tools/adc-resolution — bits, quantization, and word sizes on the acquisition side of the systems Hamming codes protect
/tools/snr-enob — the analog error budget that decides how clean your bits are before the code ever sees them
/tools/link-budget — coding gain from error correction is a line item in every space-link margin calculation

Sources

Written by HE in our own words from the cited sources — engineering judgment included, your stamp still required. All entries →