Put the legal words far apart

Suppose only 000 and 111 are valid transmissions. The sender wants to communicate one bit, but repeats it three times. If 111 arrives as 101, one position differs from 111 and two differ from 000. The closest legal word is unambiguous, so the receiver repairs 101 to 111.

The number of positions at which two equal-length words differ is their Hamming distance. For binary words it is the number of one-bits in their exclusive-or.

Distance behaves exactly like physical separation. If every pair of legal codewords is at least $d$ apart, then fewer than $d$ changes cannot turn one legal word into another. Therefore the code detects up to $d-1$ errors.

Correction needs more room. A receiver repairs every word within radius $t$ of a codeword. Those balls must not overlap, which requires

$$2t < d.$$

Equivalently, minimum distance $d$ corrects $\lfloor(d-1)/2\rfloor$ errors.

Parity detects but cannot point

Append one bit so the total number of one-bits is even. Any single flipped bit changes parity, so the receiver detects it. But all bit positions produce the same complaint: “parity is odd.” The check provides one bit of evidence and cannot identify one of many locations.

To locate a single bad position among seven, the receiver needs at least three yes/no check outcomes, since three bits name $2^3=8$ cases: no error plus seven possible positions. This is the pigeonhole principle returning as a design bound.

Three checks form an address

Number seven positions by the nonzero three-bit labels 001 through 111. Create three parity checks. The first covers positions whose first label bit is 1, the second those whose second bit is 1, and the third those whose third bit is 1.

If one transmitted bit flips, exactly the checks named by that position's label fail. Read the failed checks as a three-bit number—the syndrome—and it is the address of the damaged bit. Flip it back.

Four positions can carry data and three carry parity, producing the Hamming $(7,4)$ code. Every codeword has minimum distance 3: it corrects one error and detects two when used with the appropriate decoder. An additional overall parity bit yields the familiar extended SEC-DED profile: single-error correction, double-error detection.

The packing bound

There are $2^n$ binary words of length $n$. A radius-$t$ ball contains

$$\sum_{i=0}^{t} \binom{n}{i}$$

words: choose which $i$ positions were changed. If a code has $M$ codewords and corrects $t$ errors, its disjoint balls must fit:

$$M \sum_{i=0}^{t} \binom{n}{i} \le 2^n.$$

This Hamming bound says reliability consumes space. More codewords carry more information; wider separation corrects more damage. One cannot maximize both at fixed length.

Where the guarantee stops

• Minimum distance states a worst-case bound, not a probability of failure. A channel model is needed for probabilities.
• “Corrects one error” means per protected codeword, not per file or lifetime.
• Plain Hamming $(7,4)$ cannot always distinguish two flips from one; SEC-DED requires the extended construction and a matching decoder.
• Hashes, CRCs, and error-correcting codes have different aims. Detection against random corruption is not authentication against an adversary.

Lessons

• Hamming distance turns corrupt messages into points in a metric space.
• Minimum distance $d$ detects $d-1$ errors and corrects $\lfloor(d-1)/2\rfloor$.
• A syndrome turns failed parity equations into the address of an error.
• Redundancy is not waste; it is the geometric spacing that makes repair unambiguous.

Practice

1. Compute the pairwise distances among 00000, 11100, and 00111. State the resulting detection and correction guarantees.
2. Explain why repeating one bit twice detects a mismatch but cannot choose which copy is correct.
3. Use the Hamming bound to test whether 32 length-7 binary codewords could all correct one error.
4. One week later, reconstruct the correction radius by drawing two balls between codewords distance $d$ apart.

The next question is about memory

A decoder reads an input and chooses an output. But many systems cannot choose from the current input alone: whether a second 1 is alarming depends on whether the previous input was 1. The Boolean algebra from the opening chapter has acquired state. The next chapter reveals the machine that was hiding there all along.

References

1. Hamming. “Error Detecting and Error Correcting Codes.” Bell System Technical Journal, 1950. — the primary paper introducing the geometric model and code construction
2. Demaine and Devadas. “Error-Correcting Codes.” MIT 6.042J, 2010. — an accessible proof-oriented chapter
3. “Richard Wesley Hamming.” MacTutor. — institutional mathematical biography and bibliography