The one-line implementation

Transcript: this stretch, timestamped

This is the last page of the map, and it closes the arc that started with compression. The first half of this site watched Shannon's entropy set a floor on how short a message can be made: squeeze until the encoded stream is statistically indistinguishable from a fair coin. This arc runs the same machinery backwards. A stream that looks like coin flips has no slack left in it, so a single flipped bit is unrecoverable — you cannot tell it from a different legitimate message. Error correction therefore re-inserts redundancy, but a measured amount, placed where it does maximum work. P19 derived Hamming's placement by hand. This page shows that the derivation, once you believe it, compresses into a single line of code, and then steps back to ask what having four descriptions of the same object buys you.

Outline, with timestamps

• 00:00 — Recap: parity groups that binary-search down to a single flipped bit.
• 00:31 — The reveal: read the four check results as bits and they spell the error's position.
• 01:31 — Relabel the 16 slots in binary; each index bit defines one parity group.
• 03:40 — Why the parity bits live at 1, 2, 4, 8: exactly one index bit set, so exactly one group touched.
• 04:43 — XOR as parity, as addition mod 2, as vector addition over GF(2).
• 05:44 — Stack the on-positions and XOR the column: all four parities in one operation.
• 07:19 — Why the result is the address of the error, for 0→1 and 1→0 alike.
• 08:22 — The line of Python: reduce(xor, [i for i, b in enumerate(bits) if b]).
• 10:31 — What the line does not do: the meta parity bit, block sizing, burst errors, Reed–Solomon.
• 12:08 — One algorithm, multiple perspectives; Hamming's meandering path and Shannon down the hall.

00:31 — The four answers were always an address

Part 1 left you doing four parity checks and interpreting them as a sequence of yes/no questions that halve the search space: is the error in this half? in this quarter? The video's opening move is to stop reading them as questions and start reading them as digits. Write each check's answer as a bit — 1 for "this group has odd parity, something is wrong in here", 0 for "even, clean" — stack the four bits with the first check as the least significant, and the binary number you have written is the position of the flipped bit. Position 7 is 0111, which is 4 + 2 + 1, and sure enough position 7 sits inside the first, second and third parity groups but not the fourth. Nothing is special about 7.

That single observation kills the entire "keep a candidate set and halve it" implementation you might otherwise have written. There is no bookkeeping, no interval, no loop over halves. You compute four parity bits, you concatenate them, and you index into the block. In hardware that is four XOR trees and a decoder; in software it is about to become one expression.

01:31 — The parity groups were never arbitrary: they are the index bits

Here is where the video stops asserting and starts explaining. Take the 16 slots and label them 0000 through 1111 in binary. These labels are not data — nothing about them is transmitted — they are the addresses of the slots, and they were implicit the whole time.

Now look only at the last bit of each label and highlight every slot where it is 1. Those slots are 1, 3, 5, 7, 9, 11, 13, 15 — which is precisely the first parity group from part 1 (02:04). Look at the second-to-last bit and highlight: 2, 3, 6, 7, 10, 11, 14, 15 — the second group. Third bit: 4–7 and 12–15. Top bit: the whole upper half, 8–15. The four groups you were handed as a construction in part 1 are just the four "bit k of the address is on" sets.

Which reframes each check. Check k is no longer "is the error in this weird striped region"; it is the question "if there is an error, is bit k of its address a 1?" Four such questions, four bits, one address. Generalising is now mechanical: a block of 2ⁿ slots has n-bit addresses, so it needs n parity groups — six for a 64-slot block (03:09), twenty for a million.

It also explains the placement that looked like a lucky choice in part 1 (03:40). The parity bits sit at positions 1, 2, 4, 8 because those are exactly the addresses with a single bit set. Position 4 is 0100: it belongs to group 2 and to no other group. So the parity bit at position 4 is a control knob wired to syndrome bit 2 alone. Set it, and nothing else moves. That non-interference is what makes encoding a single pass rather than a system of equations to solve.

04:43 — XOR computes every parity at once, and here is why

XOR of two bits is 1 exactly when they differ, which is the same as saying it is their parity: the sum mod 2. Extend it to bit strings componentwise and you get addition with no carrying — vector addition in (ℤ/2)ⁿ, i.e. over the two-element field GF(2). The property that matters is that XOR-ing many strings together is column-wise parity of all of them at once (05:13): column k of the result is 1 if and only if an odd number of the inputs had a 1 in column k.

Now the move (05:44). Take the block, look at which slots hold a 1, write down the addresses of those slots in binary, and XOR the whole list together. Call the result the syndrome S:

S  =  ⊕  { i  :  bit at position i is 1 }        (⊕ = XOR, i written in binary)

Claim: bit k of S is the parity of parity-group k. The proof is one line and it is worth doing rather than nodding at. By the column-wise property,

bit_k(S)  =  ⊕      bit_k(i)        (XOR over on-positions i)
             i on

          =  #{ i : bit i is on  AND  bit_k(i) = 1 }   mod 2

          =  #{ on-bits in group k }  mod 2

          =  parity of group k.

Read that middle step slowly, because it is the whole lesson (06:19). XOR-ing a column of bits is counting the 1s mod 2. The 1s in column k come from exactly those on-positions whose address has bit k set — and "positions whose address has bit k set" is the definition of group k. So the count is the number of on-bits in group k, and its parity is the group's parity check. The four checks are not like the XOR; they are the four bits of the XOR, computed simultaneously because the four groups are stored in four independent columns and XOR never carries between columns. No-carry is doing the load-bearing work: a carry would let group 0 contaminate group 1.

Two corollaries fall out immediately (07:19). If a slot flips 0→1, its address joins the XOR, so S goes from 0 to that address. If a slot flips 1→0, its address leaves the XOR — but over GF(2) removing a term and adding it again are the same operation, since x ⊕ x = 0 (07:50). Either way the syndrome becomes the address of the corrupted slot. A clean block gives 0000; any single error gives its own index, in binary, ready to use.

A block, worked end to end

Let us do a real 16-slot block rather than gesture at one. Slots are numbered 0–15. Slot 0 is the whole-block parity bit (more on it below); slots 1, 2, 4, 8 are the four Hamming parity bits; the remaining eleven slots — 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15 — carry the message. That is the extended Hamming(16, 11) code.

Step 1 — the message. Suppose the eleven data slots, in order 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, carry 1 0 1 1 1 0 0 1 0 0 1. So the data slots that are on are 3, 6, 7, 9, 12, 15.

Step 2 — the encoder runs the same XOR. XOR those addresses:

3    0011
6    0110   →  0101   (=5)
7    0111   →  0010   (=2)
9    1001   →  1011   (=11)
12   1100   →  0111   (=7)
15   1111   →  1000   (=8)

data-only syndrome  S₀ = 8 = 1000

The encoder wants the finished block to satisfy S = 0. Each parity bit at 2ᵏ contributes exactly 2ᵏ to the XOR when it is on, and contributes to no other bit of the syndrome — so the answer is simply copy the bits of S₀ into the parity slots. Here S₀ = 1000, so slot 8 is set to 1 and slots 1, 2, 4 to 0. This is the encoder (06:49): the decoder's operation, run once on the data alone, with the result written into the powers-of-two slots. Because those slots are the standard basis vectors of the syndrome space, the assignment is unique and order-free — there is no iteration and nothing to solve.

Step 3 — the overall parity bit. The block now reads, slots 1 through 15: 0 0 1 0 0 1 1 1 1 0 0 1 0 0 1. That is seven 1s, an odd count, so slot 0 is set to 1 to make the total even. Slot 0 has address 0000, which contributes nothing to any XOR — which is precisely why the overall-parity bit can live there without disturbing the Hamming syndrome. The finished 16-bit block, slot 0 first:

slot   0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
bit    1  0  0  1  0  0  1  1  1  1  0  0  1  0  0  1
role   P* p  p  d  p  d  d  d  p  d  d  d  d  d  d  d

on-positions: 0, 3, 6, 7, 8, 9, 12, 15
XOR:  0⊕3=3 ⊕6=5 ⊕7=2 ⊕8=10 ⊕9=3 ⊕12=15 ⊕15=0     →  S = 0000  ✓
number of 1s = 8, even                              →  overall parity ✓

Step 4 — corrupt it. Flip slot 11 from 0 to 1. Now 11 joins the XOR, so S = 0 ⊕ 11 = 1011. The receiver reads 11, flips slot 11 back, and is done. The table checks the same thing the slow way, group by group, so you can see the two computations agree column for column:

Both routes give 11. Flip a 1 instead — say slot 12 goes from 1 to 0 — and the syndrome is 1100 = 12, again the right address, because dropping 12 from the XOR and adding it are the same act.

Step 5 — two errors, and what slot 0 buys. Flip slots 11 and 12. The syndrome is 11 ⊕ 12 = 0111 = 7: non-zero, and pointing confidently at slot 7, which is innocent. The bare Hamming code has no defence here. But count the 1s in the block: two flips changed the count by +1 − 1 = 0, so it is still even, and the overall-parity bit at slot 0 says "an even number of errors" (10:31). Even count with a non-zero syndrome is a contradiction under the single-error hypothesis, so the receiver knows it is looking at a double error and refuses to "correct" slot 7. That is the whole extended code:

My addition, not Grant's: this is the standard SECDED behaviour — single error correction, double error detection. Hamming(15, 11) has minimum distance 3, so it corrects one error; adding the overall parity bit lifts the distance to 4, which buys detection of two. And the unextended code is perfect in the technical sense: 2¹¹ × (1 + 15) = 2¹¹ × 16 = 2¹⁵, so the radius-1 balls around the codewords tile the space of 15-bit strings exactly, with nothing left over. Not one bit of the block is wasted.

08:22 — The line itself

Written out, the decoder is this:

from functools import reduce
from operator import xor

syndrome = reduce(xor, [i for i, b in enumerate(bits) if b], 0)

Read it right to left: enumerate pairs each slot with its index, if b keeps only the slots holding a 1, i takes their indices, and reduce(xor, …) folds the list into a single integer. In the video the random test block returns 9 (09:29); a properly encoded block returns 0, and flipping any one bit makes it return that bit's index (10:01). The ^ operator in Python is doing bitwise XOR on the machine words, which is exactly the column-wise parity argument above, four columns at a time in one instruction.

Three things about the line are worth naming. First, the initial value 0 matters: an all-zero block has no on-positions and must fold to 0, not raise. Second, nothing in it mentions 16 — the same line decodes 256 slots, or a million, with the register width being the only limit. Third, the encoder is the same line: run it over the data slots alone, then write the result's bits into slots 1, 2, 4, 8, …, as in step 2 above. Encoder and decoder differ only in what you do with the number that comes out.

What the line does not handle is the overall-parity bit, the detect-two-errors logic in the table above, and everything about choosing a block size. Bigger blocks are more efficient — 256 slots spend about 3% of themselves on redundancy, a million-bit block needs 21 parity bits and it is genuinely startling that 21 questions locate one flip among a million (12:35) — but efficiency is not the only axis. The probability of two or more flips in a block grows with the block, and Hamming handles exactly one (13:08). Worse, real noise arrives in bursts, which is the pathological case: a burst puts several errors in one block and none in its neighbours. The standard fix is interleaving — write blocks into rows and transmit columns, so a contiguous burst is smeared one bit into each of many blocks. Beyond that you leave Hamming's regime for Reed–Solomon (13:39), which is symbol- rather than bit-oriented, eats bursts naturally, and is tunable to any number of correctable errors per block.

12:08 — One algorithm, four perspectives

The closing chapter's real subject is not Hamming codes. It is that the same object now has four descriptions, and each one makes a different question easy. Keeping all four is the point.

The matrix view is worth pinning down, because Grant mentions it only to say it gives little intuition (12:02), and he is right about intuition but it is the view under which the theorems get proved. H is the 4×15 matrix whose columns are the binary numerals 1 through 15. Multiplying it by the block vector v over GF(2) sums the columns where v is 1 — which is exactly XOR-ing the addresses of the on-bits. Codewords are the v with H·v = 0, an 11-dimensional subspace: 2¹¹ = 2048 valid blocks. Minimum distance 3 follows in a sentence, and it is a nice sentence: any two distinct columns of H are different and non-zero, so no two of them sum to zero, so no weight-2 vector is a codeword; hence no two codewords differ in fewer than 3 places. Every property of the code is a property of "the columns are all the non-zero 4-bit strings, each exactly once."

Grant's point about hardware versus software (11:01) generalises: the parity-group story is the one to teach and to etch into silicon, the XOR story is the one to type, the binary-search story is the one that tells you why the cost is what it is, and the matrix story is the one that scales to the codes people actually deploy. A perspective is not a restatement; it is a different set of cheap questions.

15:43 — Two questions from one 1948 paper

Grant ends with Hamming's own account, in The Art of Doing Science and Engineering, of how meandering the discovery was: lattices, higher-dimensional arrangements, a lot of wrong turns, and only then the question "what is the most efficient I could conceivably be about this?" (14:10). Parity checks happened to already be on his mind, which in the 1940s was not common.

"There are like half a dozen times throughout this book that he references the Louis Pasteur quote, luck favors a prepared mind."— Grant Sanderson, 14:41

Hamming and Shannon shared an office at Bell Labs, and Shannon's A Mathematical Theory of Communication appeared in 1948, concurrent with this code. That is the right place to close this map, because the two halves of the site are two questions from that one paper. How short can a message be made? — answer: its entropy, H(p) = Σ p(x)·log₂(1/p(x)) bits per symbol, and a compressor that reaches the bound leaves an output with no structure left to exploit, statistically a fair coin. How much noise can a channel take? — answer: the noisy-channel coding theorem, which says that below the channel capacity arbitrarily reliable transmission is possible, at a cost in rate but not in correctness. The first question says take redundancy out until there is none. The second says put a measured amount back, and tells you how little you can get away with.

Hamming codes are the concrete, hand-sized instance of the second answer: to point at one flipped bit among 2ⁿ you need n bits of address, so you spend n bits and not one more (11:31). Against the naive instinct — send the message three times — that is the difference between 200% overhead and 3%. Both are answers about the same currency, bits, measured the same way, in the same paper.

"Ironically, the ideas that most profoundly shape the ways that a future generation thinks will end up looking to that future generation simpler than they really are."— Grant Sanderson, 16:13

Where people get stuck

"The XOR gives the position — but positions of what, bits or indices?" This trips almost everyone the first time. You are not XOR-ing the data. You are XOR-ing the index numbers of the slots whose data happens to be 1. The data bits act only as a filter deciding which addresses enter the sum. A block of all 1s and a block of all 0s both have syndrome 0, for completely different reasons — the first because every address appears and they cancel in pairs across the full range, the second because the sum is empty.

"Why doesn't setting one parity bit break the other parity checks?" Because the parity slots are at 1, 2, 4, 8, and those addresses have exactly one bit set each. In matrix language the four parity columns of H form the identity matrix, so the encoder is solving a system that is already diagonal. Put a parity bit at, say, slot 6 (0110) and it would sit in two groups at once, and you would genuinely have to solve equations. The powers of two are not an aesthetic choice; they are the choice that makes the system triangular.

"A syndrome of 0 means the block is fine." It means the block is a codeword. Three errors can also land you on a valid codeword, or on the wrong one, and the code will cheerfully accept it. Hamming codes are guaranteed only within their distance: one error corrected, two detected (with the extension). Everything past that is undefined behaviour, which is why block sizing and interleaving are engineering decisions, not afterthoughts.

"Slot 0 seems like a wasted position." It is unusable by the Hamming code proper — address 0000 contributes nothing to the syndrome, so a flip there is invisible to all four checks, and conversely syndrome 0 is already spoken for as "no error". That is exactly what makes it the right home for the overall-parity bit: it is the one slot whose state the syndrome cannot see, so it can carry independent information for free. The apparent waste is the extension's opportunity.

Going deeper, verified

• But what are Hamming codes? The origin of error correction — 3Blue1Brown (2020) · Part 1, the hands-on derivation this video compresses; covered on P19.
• What is error correction? Hamming codes in hardware — Ben Eater (2020) · The companion Grant links: the same scheme built on a breadboard, where the "four XOR trees" become actual wires.
• The almost impossible chessboard puzzle — Stand-up Maths with Matt Parker and Grant Sanderson (2019) · The same index-XOR logic solving a different problem on 64 squares; the best exercise in the identity "syndrome = address".
• Error Detecting and Error Correcting Codes — R. W. Hamming, Bell System Technical Journal 29(2), 147–160 (1950) · The original. Short, readable, and already framed in terms of distance rather than tricks.
• A Mathematical Theory of Communication — C. E. Shannon (1948) · The paper both halves of this map descend from: entropy as the compression floor, capacity as the noise ceiling.
• The Art of Doing Science and Engineering — Richard Hamming (1997; Stripe Press edition) · Chapter 12 is Hamming's own account of the discovery, wrong turns included.

Exercises

1. Encode a block by hand, then break it — Take the eleven data bits 1 1 0 0 1 0 1 1 0 1 0 into slots 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15. XOR the on-addresses to get S₀, write its bits into slots 1, 2, 4, 8, set slot 0 for even overall parity, and verify the full block XORs to 0. Then flip one slot of your choosing and confirm the syndrome is its index. A good answer states S₀ explicitly and shows the group-by-group parity table agreeing with the XOR, as in the worked example above.
2. Write the encoder as one line too — The video gives the decoder as a single reduce. Write the matching encoder in the same spirit: a function taking 11 data bits and returning a 16-bit list, using the same fold. Then write a loop that, for all 2¹¹ = 2048 messages and all 16 single-bit flip positions, checks that the decoder recovers the flipped index — 32,768 cases, and all of them should pass. Extend it to all 120 two-bit flip pairs per codeword and confirm every one is detected (even overall parity, non-zero syndrome) and none is silently mis-corrected.
3. Price the redundancy — For block sizes 2ⁿ with n = 4, 8, 12, 20, compute the number of parity bits (n plus one for the extension), the number of data bits, and the overhead as a percentage. Compare each against the naive triple-repetition code (200% overhead, corrects one error per triple). Then compute, for a per-bit flip probability of 10⁻⁶, the probability that a block of each size contains two or more flips — 1 − (1−p)ᴺ − N·p·(1−p)ᴺ⁻¹ — and say which block size you would actually ship, and why the answer is not "the biggest one".