Why one flipped bit can be found and fixed: Hamming's error-correcting code
30seconds
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 of weekend jobs dying on the Bell Labs relay computer, showed how: add a few parity bits, each watching an overlapping group of positions.
When a bit flips, the checks that fail spell out the address of the culprit in binary. Flip a bit yourself in the interactive, read the three checks, and watch the decoder fix it. Then flip two and see the clever scheme get fooled.
Deep dive · 4 min
More in Computing
View all →
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…
How a computer finds one flipped bit and fixes it: Hamming's code
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…
Why 0.1 + 0.2 isn't 0.3: flip the 64 bits a computer uses for decimals
Type 0.1 + 0.2 into almost any programming language and you get 0.30000000000000004. Nothing is broken. Computers count in powers of two, and a tenth is an…
How a Bloom filter says "definitely not" using just a few bits
How can a computer check whether a word is on a huge list using only a few bits per entry? A Bloom filter flips a handful of switches for every word you add…