Reinventing Hamming codes

Transcript: this stretch, timestamped

The map so far has been one long argument about the source side of Shannon's 1948 paper: entropy H(p) is the number of bits a message really contains, compression is the art of getting close to it, and cross-entropy is what you pay for guessing the distribution wrong. That is Shannon's first coding theorem, the one P6 built. This arc is the second one. Once a message is compressed, every bit in it matters — there is no slack left to absorb damage, which is precisely what makes a compressed file so fragile. So you deliberately put structure back in, in the smallest amount that will let a receiver undo the damage a noisy channel does. Shannon proved that a specific amount is enough; Richard Hamming, a few years earlier and for entirely practical reasons, built the first scheme that actually did it. This page reinvents that scheme; P20 collapses it to a line of code.

Outline, with timestamps

• 00:03 — The puzzle: a scratched CD reads back different bits and still yields a bit-for-bit correct file.
• 01:07 — Triplicate-and-vote burns two-thirds of the disk. The real target: a 256-bit block with 9 bits of redundancy and 247 free.
• 04:16 — The setup: a 16-bit block, positions numbered 0–15, four of them reserved — and reserved at the powers of two.
• 05:50 — Parity: one bit whose only job is to make the count of 1s even. Detects any single flip, locates nothing.
• 08:27 — The insight: don't check the whole block, check carefully chosen subsets. Twenty questions, each answer worth one bit of location.
• 10:29 — Two checks pin down the column; two more pin down the row. Four questions, one address.
• 12:34 — The parity bits protect themselves as a byproduct; and the scheme scales as eight questions for 256 positions.
• 14:14 — The seventeenth outcome. Four checks have 16 answers but there are 16 positions plus "no error", so position 0 has to go: (15,11).
• 15:16 — Position 0 comes back as a parity bit over the whole block, and that buys double-error detection.
• 17:56 — Play receiver: 0, 1 or 2 bits are flipped, and the four checks tell you which.

Two theorems, one channel

Shannon's 1948 paper contains two coding theorems, usually taught apart, and they point in opposite directions along the same pipe. The source coding theorem says a source with entropy H(p) bits per symbol can be compressed to H(p) bits per symbol and no fewer — the floor P6 derived, under which the whole compression arc of this map lives.

The noisy-channel coding theorem says: a channel has a number attached to it, its capacity C = max I(X;Y) — the mutual information between what you put in and what comes out, maximised over input distributions. For any rate R < C there exist codes of increasing block length whose probability of decoding error goes to zero. For R > C no such codes exist. Capacity is a hard wall in exactly the way entropy is a hard floor.

For the channel this video is about — the binary symmetric channel, which independently flips each bit with probability p — the capacity works out to

C = 1 − H₂(p)     where  H₂(p) = p·log₂(1/p) + (1−p)·log₂(1/(1−p))

bits per channel use. At p = 0.01, H₂(0.01) = 0.0808 and so C = 0.919 bits per use. Read that number carefully: it says you can push 0.919 useful bits through every physical bit of a channel that corrupts one bit in a hundred, and be arbitrarily reliable doing it. That is a shocking claim and it is why Shannon's theorem is the founding result of the field.

Where does a Hamming code sit against that wall? The (15,11) code has rate 11/15 = 0.733, the extended (16,11) code 0.688 — both well under 0.919, and neither drives the error probability near zero, because a Hamming code corrects exactly one error no matter how long the block gets. (My addition, not the video's: push the family out to (2ʳ−1, 2ʳ−1−r) and the rate climbs towards 1 while the expected number of errors per block climbs too, so the failure probability climbs towards 1 with it. Hamming codes are optimal in a packing sense — the next-but-one section explains that — and simultaneously nowhere near capacity-achieving. Different questions.) Closing the gap to C took another fifty years and a different family of ideas, turbo and LDPC codes. Hamming's contribution is the one that makes the task feel possible at all.

"Hamming codes are not as widely used as more modern codes, like the Reed-Solomon algorithm, but there is a certain magic to the contrast between just how impossible this task feels at the start, and how utterly reasonable it seems once you learn about Hamming."— Grant Sanderson, 02:40

The naive scheme (00:37) — store each bit three times, take the majority — costs two-thirds of your storage and still guarantees nothing once two copies of the three are hit. What follows spends 5 bits out of 16, or 9 out of 256 with 247 left for payload (01:07). The general frame: only some strings count as valid messages, and the receiver snaps whatever arrives to the nearest valid one, the way you read through a typo (03:13). All the design work is choosing valid messages that are far apart and cheap to snap to.

The origin story is worth getting right, because it is a rare case where the founding date and the founding annoyance are both on record (03:46). Richard W. Hamming left Los Alamos for Bell Telephone Laboratories in 1946, where he stayed until 1976 and for a while shared an office with Claude Shannon. He had weekend-only access to a relay machine, and one Friday in 1947 he queued up a long calculation, came back on Monday, and found the run had aborted on a misread bit early in the sequence. The machine could already detect the error — that is what the parity hardware was for. His complaint was that having detected it, the machine gave up instead of fixing it. Three years of work later he published Error detecting and error correcting codes in the April 1950 Bell System Technical Journal, which introduced both the codes and the notion of distance between codewords that the field still runs on. So: Bell Labs, frustration in 1947, publication in 1950 — Grant's "the 1940s" is the discovery, not the paper.

Parity: one bit that notices any change

The building block (05:50) is a single bit whose entire job is to make the number of 1s in the block even. The sender counts; if the count is odd, the parity bit goes to 1, otherwise 0. The receiver counts again. An odd count means something changed.

The reason this works is worth stating in one sentence, because it is the sentence the rest of the scheme leans on: flipping any single bit changes the total count of 1s by exactly ±1, and therefore always changes its parity (06:20). It does not matter which bit, or which direction — 0→1 adds one, 1→0 subtracts one, and both flip even to odd. In the algebraic language of P20, parity is the XOR of every bit in the group, and XOR is exactly the "sum mod 2" that makes that argument trivial.

What parity cannot do is locate: one bit of output distinguishes two states, and "clean" versus "broken" already uses both. Nor can it count — three errors look like one, five look like one, two look like none (07:21). That is the standard complaint, and the standard answer is that no scheme escapes it in principle: enough noise turns one valid message into a different valid message and nothing can tell (07:54). Every real code is a bet about how many errors are plausible, not a guarantee.

"Storing data is the same thing as sending a message just from the past to the future instead of from one place to another."— Grant Sanderson, 05:20

The leap: parity over overlapping subsets

Hamming's insight (08:27) is that parity is not obliged to cover the whole block. Run it over half the block and its single bit of output stops meaning "something broke" and starts meaning "the break, if any, is in this half". That is a bit of address. Stack up four such answers about four cleverly chosen halves and you have four bits of address, which is enough to name one of sixteen positions.

Which halves? Grant builds them geometrically, laying the 16 positions out as a 4×4 grid in reading order and taking the halves you would draw with a ruler: the odd columns, the right half, the odd rows, the bottom half (10:29). The first two answers between them name a column, the second two name a row, and a row and a column name a square (10:59). It is a binary search in two dimensions at once.

Now write the four halves out as position lists and the geometry evaporates into something better. Each of Grant's halves is exactly "the positions whose index has a particular binary bit turned on".

Check any row by hand: 1, 3, 5, 7, 9, 11, 13, 15 in binary all end in 1; 8 through 15 all start with 1. Now the payoff. Suppose exactly one bit, at position j, is flipped. Group 2ⁱ contains position j if and only if bit i of j is 1, so check i fails if and only if bit i of j is 1. Line the four answers up as (c₈ c₄ c₂ c₁) and you are not reading four clues that need combining — you are reading j itself, written in binary. Grant flags the connection to binary counting and asks you to find it yourself (12:01); that is the whole of it.

Two consequences fall straight out. First, an error in one of the four parity bits is found by the same four questions as any other, with no special case (12:34) — position 8's index is 1000, so flipping it fails only check 8, and the syndrome reads 8. Second, the scheme scales by log: 256 positions need 8 questions, and each question costs exactly one bit of the block to answer (13:07). The redundant bits are fully determined by the message bits (13:41), which is what "redundant" means here — no new information, only resilience.

Why four, and why positions 1, 2, 4, 8

Here is where the counting bites (14:14). Four yes/no checks produce 2⁴ = 16 distinct outcomes. A 16-bit block has 16 positions that might be wrong. But you also need an outcome that means "nothing is wrong", and 16 outcomes cannot cover 17 cases. Something has to give.

What gives is position 0 — and it is forced, not chosen. Position 0's index is 0000, so it belongs to none of the four groups; a flip there would produce the all-clear syndrome, which is already spoken for. So position 0 is dropped from the code entirely, "no error" claims the all-zero syndrome unambiguously, and the block shrinks to 15 bits: 4 parity, 11 message. That is the (15,11) Hamming code (14:44), and the same arithmetic in general says r parity bits can protect a block of n = 2ʳ − 1 bits carrying 2ʳ − 1 − r of message.

The choice of positions 1, 2, 4, 8 for the parity bits is also forced once you want the encoder to be easy, and this is the "something really elegant by the end" that Grant defers at 04:48. Position 1 is the only position in group 1 that is in no other group; the same for 2, 4 and 8 in their groups. So each parity bit participates in exactly one equation, and the sender can set all four independently, in any order, with no risk of one fixing a group and breaking another. Bunch the parity bits together at the end of the block and you lose that: the equations tangle, and you need actual linear algebra to solve them.

The same construction as linear algebra over GF(2)

This section is my addition — Grant deliberately keeps the video in the language of halves and questions, and gets to the algebra by a different route in Part 2. It is worth having both.

Work in GF(2), the field with two elements, where addition is XOR. Define the parity-check matrix H as the 4×15 matrix whose j-th column is the 4-bit binary numeral for j:

position:  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
row c₈  :  0  0  0  0  0  0  0  1  1  1  1  1  1  1  1
row c₄  :  0  0  0  1  1  1  1  0  0  0  0  1  1  1  1
row c₂  :  0  1  1  0  0  1  1  0  0  1  1  0  0  1  1
row c₁  :  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1

Each row of H is the indicator vector of one of the four parity groups in the table above — row c₁ has 1s at 1, 3, 5, …, row c₈ has 1s at 8 through 15. So the statement "all four groups have even parity" is precisely the matrix equation Hc = 0, and the code is the null space of H: dimension 15 − 4 = 11, hence 2¹¹ codewords, hence 11 message bits. The columns at positions 1, 2, 4 and 8 are the four standard basis vectors, which is the algebraic restatement of why those positions make good parity bits.

Now let a received word be r = c + e where c is a codeword and e is the error pattern. By linearity, Hr = Hc + He = He. If the error is a single flip at position j, then e is the j-th standard basis vector and He is simply the j-th column of H — the binary numeral for j. The syndrome is the address. That one line contains the entire decoder, and it is true by construction because we defined the columns to be the numerals.

The same matrix gives the minimum distance for free. No single column is zero, and no two columns are equal, so no combination of one or two columns XORs to zero — meaning no nonzero codeword has weight 1 or 2. But some triples do: columns 1, 2 and 3 are 0001, 0010, 0011, and 0001 ⊕ 0010 = 0011. So the minimum distance is exactly 3, which by the standard ⌊(d−1)/2⌋ rule corrects one error. Everything Grant establishes by picture is visible here as a fact about the columns of a matrix.

The zeroth bit, back to work: SECDED

Fifteen is an awkward block size, and there is a discarded bit lying around. Put position 0 back and give it a job: make the parity of the entire 16-bit block even, after the other four parity bits are already set (15:16). This is the extended Hamming code, (16,11) (15:49).

The extra bit adds no correcting power — the four inner checks already do that. What it adds is the ability to tell "one" from "two", and the mechanism is worth spelling out, because it is easy to nod along to without actually having. Write the decoder's evidence as a pair: c₀, the parity of the whole block, and s = (c₈c₄c₂c₁), the four-bit inner syndrome.

The bottom row is the whole point. An odd number of flips always toggles c₀; an even number always leaves it alone. So c₀ answers "odd or even count?" while s answers "any error, and if a single one, where?" The pair (c₀ = 0, s ≠ 0) is impossible for zero or one error and consistent only with two: an unambiguous double-error alarm. Algebraically, the extra all-1s row in the parity-check matrix forces every codeword to have even weight, pushing the minimum distance from 3 to 4 — exactly enough to correct 1 and detect 2. The combination is standard enough to have an acronym, SECDED, and it is what ECC memory in a server has been doing for decades.

Note what the receiver cannot do with a double error: the syndrome s = h_i ⊕ h_j is a perfectly valid column, so it names some innocent third position. Correcting there would make things worse. The only safe response is to flag the block. And at three flips the alarm fails too — three errors toggle c₀ back to odd, so the block masquerades as a single error and gets silently miscorrected.

A full block, encoded and broken

Grant walks a complete example, encoder then decoder (16:22), and it is genuinely worth doing rather than watching. The bits themselves live only in the animation, so what follows is a worked example of my own construction, with every number checkable by hand.

Take the 11-bit message 1 0 1 1 0 0 1 0 1 1 0. Lay it into the eleven non-reserved positions in order — 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15 — leaving 0, 1, 2, 4 and 8 empty (16:52). Then set each parity bit so its group comes out even, and finally set bit 0 so the whole block comes out even.

position : 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
value    : 0  0  1  1  0  0  1  1  1  0  0  1  0  1  1  0
role     : P  p  p  m  p  m  m  m  p  m  m  m  m  m  m  m
                                          (P = overall, p = parity, m = message)

Now corrupt it. Flip position 13, so that bit goes from 1 to 0, and re-run the four checks on the received word. Group 1 now holds 0,1,0,1,0,1,0,0 — three 1s, odd, so c₁ = 1. Group 2 is untouched (13 is not in it), c₂ = 0. Group 4 holds 0,0,1,1,0,0,1,0 — odd, c₄ = 1. Group 8 holds 1,0,0,1,0,0,1,0 — odd, c₈ = 1. Read them off: c₈c₄c₂c₁ = 1101₂ = 13. The whole block now has 7 ones, odd, so c₀ = 1 and the receiver knows it is looking at one flip and not two. Flip 13 back, strip the five non-message positions, and the original 11 bits come out (19:01).

Now break it twice. Flip both 6 and 13. Group 1 sees only 13: c₁ = 1. Group 2 sees only 6: c₂ = 1. Group 4 sees both, so its parity flips twice and comes back even: c₄ = 0. Group 8 sees only 13: c₈ = 1. Syndrome 1011₂ = 11 — which is exactly h₆ ⊕ h₁₃ = 0110 ⊕ 1101 = 1011, and it points at the entirely undamaged position 11. But two flips leave the whole-block parity even, c₀ = 0, and (c₀ = 0, s ≠ 0) is the double-error signature from the table above. The receiver refuses the bait.

Is the trade worth it? Concretely, on a binary symmetric channel with p = 0.01, sending 11 raw bits gives a 1 − 0.99¹¹ = 10.47% chance the chunk is wrong. Wrapped in the extended (16,11) code and sent as 16 bits:

Binomial: 0.99¹⁶ = 0.85146, 16·0.01·0.99¹⁵ = 0.13761, 120·0.01²·0.99¹⁴ = 0.01042, remainder 0.00051. My arithmetic, not the video's.

So five extra bits take you from "one chunk in ten is quietly corrupt" to "999 chunks in a thousand come out right or come out flagged". That is the deal, and it is the deal an entire industry took.

Where people get stuck

"Four bits can't back up eleven, so how is this not magic?" — because the parity bits are not a backup. They do not encode what the message says; they encode four true/false facts about it, chosen so that the four facts jointly locate a discrepancy. You are not storing a copy of the data, you are storing a copy of the data's address space. Once you see that four bits is exactly enough to write down a number from 0 to 15, the mystery dissolves.

"Why powers of two, when the parity bits could go anywhere?" — they could, and the code would work; what you lose is the easy encoder. Positions 1, 2, 4, 8 are the only positions belonging to exactly one group each, so each parity bit can be computed from message bits alone with no circular dependency. Put a parity bit at position 3 instead and it sits in two groups, so setting it to fix group 1 disturbs group 2. Algebraically: those four columns of H are the standard basis, so the system is already solved.

"What if the error hits a parity bit?" — nothing special happens, which is the elegant part (12:34). Position 4 is in group 4 and no other, so a flip there fails exactly check 4 and the syndrome reads 0100 = 4. The decoder does not need to know, or care, which positions carry message and which carry parity; it just reads the number.

"If it detects two errors, why can't it fix them?" — because the evidence is genuinely ambiguous, not because the decoder is lazy. Two flips at i and j produce syndrome h_i ⊕ h_j, which is some other valid column h_k. From s alone the receiver cannot distinguish "flips at i and j" from "flip at k" — those two error patterns give identical received words, so no algorithm can. Only c₀ breaks the tie, and it only says "even number", never which pair.

Going deeper, verified

• What is error correction? Hamming codes in hardware — Ben Eater (2020) · the companion video Grant points to at 02:40; the same scheme built on breadboards out of XOR gates, which is the fastest way to believe the parity groups are physical.
• Hamming codes part 2: The one-line implementation — 3Blue1Brown (2020) · the direct sequel, and the subject of P20: the whole decoder as an XOR over the indices of the bits that are on.
• Error detecting and error correcting codes — Richard W. Hamming (1950), Bell System Technical Journal 29(2):147–160 · the original, written around the (7,4) case; short, readable, and it introduces the distance-based framing the whole field still uses.
• A Mathematical Theory of Communication — Claude E. Shannon (1948) · both coding theorems in one place: the source coding theorem this map has been building, and the noisy-channel theorem this arc is about. Part II covers the noisy case.
• Information Theory, Inference, and Learning Algorithms — David J. C. MacKay (2003), free full PDF · Chapter 1 does the (7,4) Hamming code with syndrome decoding, Chapters 9–10 prove the noisy-channel coding theorem, and Part VI shows why LDPC codes reach the capacity Hamming codes do not.

Exercises

1. Encode, break, repair — take the 11-bit message 0 1 1 0 1 0 0 1 1 0 1, lay it into positions 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, and produce the full 16-bit extended block. Then have someone flip one bit without telling you which, and recover it from the four group parities alone. A good answer states the four parity bits and bit 0 explicitly, and shows the syndrome read as a binary numeral matching the flipped position. Cross-check against the interactive at harryli0088.github.io/hamming-code, built by a viewer of this video.
2. Find the ambiguity — pick any two positions i ≠ j in 1–15, compute h_i ⊕ h_j, and identify the innocent position k that a decoder without the whole-block parity bit would wrongly "correct". Then show there is no pair whose XOR is zero, and conclude that the plain (15,11) code always miscorrects a double error rather than sometimes catching it. A good answer explains why this is a statement about the columns of H being distinct and nonzero.
3. Price the redundancy against capacity — for p ranging over 10⁻⁴ to 10⁻¹, plot three curves: the binary-symmetric-channel capacity C = 1 − H₂(p), the extended Hamming rate 11/16, and the probability that a 16-bit block suffers two or more errors. A good answer identifies the crossover where the code stops helping (the block-failure probability rises above the raw 11-bit failure probability), notes that the rate line is flat while capacity falls, and observes that the gap between 11/16 and C at small p is the room later codes went on to claim.
4. Scale the family — construct the parity-check matrix for r = 5, giving a (31,26) code, and verify the packing identity 2²⁶ × 32 = 2³¹. A good answer lists the five parity positions, gives the size of one of the parity groups (16 positions), and states the rate 26/31 = 0.839 against the 11/15 = 0.733 of the smaller code — the rate improves, while the correcting power stays at one error.