Symptom

You are specifying ECC memory for a fleet. The vendor quotes SECDED: single error correct, double error detect, at 8 check bits per 64 data bits. That is 12.5% overhead, and someone in the room asks the obvious question — why not correct two errors? Or three? What does it cost?

The vendor says more bits. How many more? Nobody in the room knows, and the options in the catalogue look arbitrary: (72,64) SECDED, (255,223) Reed–Solomon, various LDPC configurations for flash. There is no visible principle connecting redundancy to correction capability, so the choice gets made on price.

There is a principle, and it is geometric. Every code is a set of points in a discrete space, correction is a sphere around each point, and the spheres must not overlap. Once you see it that way the whole catalogue becomes a sphere-packing problem, the overhead becomes computable, and the question “why not correct two errors” gets a number rather than a shrug.

Statement

Hamming distance $d(x,y)$ is the number of positions where two equal-length strings differ. The minimum distance $d$ of a code is the smallest distance between any two codewords. Then:

  • A code with minimum distance $d$ detects up to $d - 1$ errors.
  • It corrects up to $t = \lfloor (d-1)/2 \rfloor$ errors.

Hamming bound (sphere-packing bound). Any binary code of length $n$ correcting $t$ errors has at most

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

codewords. Equivalently, with $k$ information bits, $2^k \sum_{i=0}^t \binom{n}{i} \le 2^n$.

Singleton bound. $d \le n - k + 1$, always. Codes meeting it with equality are MDS codes, and Reed–Solomon is the important example.

A code meeting the Hamming bound with equality is perfect: the correction spheres tile the space exactly, with no point left over. Perfect codes are almost nonexistent, and the list is short enough to state — which is itself a striking fact about the geometry.

Argument

Why distance determines correction. Picture codewords as points in the Hamming cube ${0,1}^n$. Transmission moves a point by the number of flipped bits. If you receive $y$ and decode to the nearest codeword, you are correct whenever no other codeword is at least as close. Draw a ball of radius $t$ around each codeword: if the balls are disjoint, any received word within $t$ of a codeword has exactly one nearest neighbour and decoding is unambiguous. Balls of radius $t$ are disjoint precisely when $d \ge 2t+1$. That is the whole correction story, and it is geometry rather than algebra.

Detection is weaker and cheaper: to notice that an error happened you only need the corrupted word to miss every other codeword, which needs $d \ge e+1$ for $e$ errors. Correction costs roughly twice the distance of detection, which is why SECDED gets one correction and two detections out of $d = 4$.

Why the bound is a volume argument. A ball of radius $t$ in the Hamming cube contains $\sum_{i=0}^{t}\binom{n}{i}$ points — choose which $i$ positions flipped. If there are $M$ codewords and their balls are disjoint, the total volume cannot exceed the whole space:

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

That is the Hamming bound, and it is pigeonhole (T001) with a volume attached, exactly as the birthday bound (T074) was pigeonhole with a probability attached.

Working the ECC memory question. For SECDED over 64 data bits: correcting one error needs $2^k(1 + n) \le 2^n$ with $k = 64$. Try $n = 71$: $1 + 71 = 72$, and $2^{71}/2^{64} = 128 \ge 72$. So 7 check bits suffice for single-error correction — the (71,64) Hamming code — and the eighth bit buys the double-error detection, giving $d = 4$. That is where the vendor’s 8 comes from, and it is forced, not chosen.

Now correct two errors. We need $2^{64}\left(1 + n + \binom{n}{2}\right) \le 2^n$. The smallest $n$ that passes is 76: the ball holds $1 + 76 + 2850 = 2927$ points and $2^{76-64} = 4096$, so 12 check bits clear the bound. The bound is necessary, not sufficient — real BCH codes for double correction over 64 bits use around 14 to 16 check bits — but the shape of the answer is clear: the first error correction costs 7 bits and the second costs roughly another 7. Correction capability is roughly linear in redundancy, not free and not exponential.

Why perfect codes are rare. For the balls to tile the space exactly is a strong arithmetic coincidence. The complete list of binary perfect codes: Hamming codes ($t=1$), the binary Golay code $(23, 12, 7)$ correcting 3 errors, the repetition codes of odd length, and the trivial ones. That is it — proved by Tietäväinen and van Lint in the 1970s. The Golay code’s existence is a genuine accident of arithmetic ($\sum_{i=0}^{3}\binom{23}{i} = 2048 = 2^{11}$ exactly), and it flew on Voyager 1 and 2 to send back the Jupiter and Saturn images.

The Singleton bound and Reed–Solomon. Delete $d-1$ symbols from every codeword; the results must still be distinct, since codewords differ in at least $d$ places. So $M \le q^{n-d+1}$, giving $d \le n-k+1$. Reed–Solomon meets this with equality by treating data as coefficients of a polynomial of degree $k-1$ and transmitting $n$ evaluations: any $k$ evaluations determine the polynomial, so any $n-k$ erasures are survivable. That is the same fact as “two points determine a line,” and it is why RAID-6, QR codes, CDs, and erasure-coded object storage all use Reed–Solomon.

Forbids

Correcting $t$ errors with less redundancy than the bound allows. If someone proposes a (72,64) code correcting two errors, check: the radius-2 ball holds $1 + 72 + \binom{72}{2} = 2629$ points and you have only $2^{72-64} = 256$ to spend. Impossible, no cleverness available. This is a five-second refutation of a whole class of proposals.

Beating the Singleton bound. No code has $d > n-k+1$. Any claim of an erasure code surviving more failures than parity symbols is false, and this makes storage-vendor arithmetic checkable: an $(n,k)$ erasure code tolerates at most $n-k$ lost shards.

Correcting more errors than you have distance for, however good the decoder is. Beyond $d/2$ the nearest codeword may not be the transmitted one. The information is genuinely gone.

A code that corrects everything cheaply. Overhead grows with correction capability, and the growth rate is what the bound quantifies.

Does not forbid

It does not say the bound is achievable, and usually it is not. The Hamming bound is an upper limit on how good a code can be, while the Gilbert–Varshamov bound gives what is guaranteed to exist. Real codes live between them, and for most parameters the gap is never closed. Being told the bound permits 14 check bits does not mean a 14-bit code exists.

It does not apply to burst errors, which is what actually happens in hardware. Hamming distance counts scattered flips; real failures are a scratch on a disc, a row failure in DRAM, or a fading interval in wireless. Reed–Solomon operating on symbols rather than bits handles bursts natively — an eight-bit symbol counts as one error whether one bit flipped or all eight — and interleaving spreads bursts across codewords so a scattered-error code sees scattered errors. CD players interleave across a span of several thousand bits, which is why a 2 mm scratch is survivable.

It does not describe soft-decision decoding. The bound assumes hard decisions: each received bit is 0 or 1. Real demodulators produce likelihoods, and using them buys about 2 dB — a large amount — which is why LDPC and turbo decoders work with log-likelihood ratios and routinely correct patterns that a hard-decision decoder of the same code could not. The bound is not violated; the channel model is different.

It does not conflict with Shannon (T021), though they look contradictory. Shannon says rate $C$ is achievable with vanishing error; Hamming says correcting $t$ errors costs redundancy. The reconciliation is that Shannon allows a small error probability and considers typical error patterns, while Hamming demands correction of every pattern of $t$ errors. Guaranteeing the worst case is much more expensive than handling the average one, and the gap between the two bounds is precisely the price of worst-case guarantees.

It does not mean list decoding is impossible past $d/2$. Sudan and Guruswami–Sudan decode Reed–Solomon well beyond half the minimum distance by returning a short list of candidates rather than one answer. If you have any other way to disambiguate — a checksum, a plausibility check — this extends usable correction substantially, and it is used in practice.

Boundary

  • The three bounds together. Hamming (sphere packing) is an upper bound, Singleton is an upper bound on distance, Gilbert–Varshamov is a lower bound on what exists. Good code design is navigating between them, and asymptotically the best known binary codes still sit at GV for most rates.
  • Linear codes make it tractable. If the code is a linear subspace, minimum distance equals minimum weight of a nonzero codeword, encoding is a matrix multiply, and syndrome decoding is a table lookup. Nearly every deployed code is linear for this reason alone.
  • Where the geometry generalizes. Sphere packing in the Hamming cube is the discrete cousin of sphere packing in $\mathbb{R}^n$, and the connection is not decorative: the Leech lattice in 24 dimensions is built from the Golay code, and Viazovska’s 2016 proof of optimal packing in dimension 8 (and, with coauthors, 24) settled a question that had been open since Kepler’s cousin problem.
  • Cryptography reuses the hardness. Decoding a random linear code is NP-hard, and the McEliece cryptosystem is built on it. It is one of the few pre-quantum systems believed to survive quantum attack, which is why a 1978 proposal is a NIST post-quantum candidate.
  • Modern practice. LDPC and polar codes approach Shannon capacity and are analyzed probabilistically rather than by minimum distance; their minimum distances are often unimpressive. That is a hint about which theory to use: Hamming’s for guarantees, Shannon’s for throughput.