How a computer finds one flipped bit and fixes it: Hamming's code
30seconds
A bit can flip in memory, on a disk or in a radio signal, and nothing tells you which one went wrong. In 1950 Richard Hamming published a code that finds the bad bit and flips it back.
Three overlapping parity checks cover seven bits. When one bit flips, exactly the checks that cover it fail, and the pattern of failures spells out that bit's position in binary. Break one yourself and watch it heal.
Deep dive · 4 min
More in Computing
View all →
How your phone finds the quickest route: Dijkstra's shortest-path algorithm
Your phone finds the fastest route across millions of roads without trying them all. The trick is a rule Edsger Dijkstra devised in 1956: always finish the…
Why eight yes/no answers can draw a fractal, make noise or compute: elementary cellular automata
Take a row of lit and dark squares and repeat one tiny rule to make the next row: look at a square and its two neighbours, then decide if it is lit. There are…
Why one flipped bit can be found and fixed: Hamming's error-correcting code
A single flipped bit can turn a good file into garbage, yet a machine can find and repair it without ever seeing the original. In 1950 Richard Hamming, tired…
Why swapping cards at random is not a fair shuffle: Fisher–Yates and the 27 paths
Shuffling three cards by swapping each one with a random card from the whole row looks fair, but it is not. It makes 3 × 3 × 3 = 27 equally likely paths for…
How to find one name among a billion in 30 looks: binary search
Pick a number from 1 to 1,000,000 and you can find it in at most 20 yes-or-no questions. The trick is binary search: look in the middle of a sorted list, throw…
Why common letters get short codes in a ZIP file: Huffman coding
ASCII spends 8 bits on every letter, whether it is a common e or a rare z. In 1951 a graduate student, David Huffman, found a way to give frequent symbols…