One wrong bit changes the message
Every message a computer sends is a string of 0s and 1s, and every wire, radio link and memory chip adds a little noise. Most of the time the noise is too small to matter. Now and then it spikes at the wrong moment and a 0 is read as a 1, or a 1 as a 0. That is a bit flip.
The machine sends the word HELLO, eight bits per letter, four bits at a time. As the Scene starts, each bit has a 5% chance of flipping. That sounds small, but a letter has eight bits, so about one letter in three arrives wrong: an H becomes a G or a J, and the receiver has no way to tell. A wrong bit looks exactly like a right one.
Try it: slide Chance a bit flips down to 1%, then up to 15%. At 1% most words arrive whole; at 15% the display fills with nonsense. The counter on the bench shows how many of the last 50 blocks arrived wrong.
Parity: counting the 1s
The simplest fix is to send one extra bit, a parity bit, chosen so that the number of 1s in the block is always even. If one bit flips on the way, the count turns odd and the receiver knows something went wrong. What it does not know is which bit to blame, so the best it can do is ask for the block again.
To repair an error rather than just notice it, the receiver needs to know where the error is. Richard Hamming worked this out at Bell Labs in the late 1940s, annoyed that the relay computer he used would stop at an error over the weekend instead of fixing it. He published his codes in 1950.
Three checks that overlap
Hamming’s (7,4) code adds three parity bits to every four data bits, making blocks of seven. Number the positions 1 to 7. The parity bits go in positions 1, 2 and 4, and each one covers a different, overlapping group:
- Check A covers positions 1, 3, 5 and 7.
- Check B covers positions 2, 3, 6 and 7.
- Check C covers positions 4, 5, 6 and 7.
Drawn as three overlapping circles, every position sits in its own region: position 7 is inside all three, position 5 inside A and C only, position 1 inside A alone. Each parity bit is set so that its circle holds an even number of 1s.
When one bit flips, every circle that contains it turns odd and the others stay even. The failing circles overlap in exactly one region, and that region holds the culprit. The groups were chosen so that this pattern spells the position in binary: read the checks as C B A, writing 1 for a failing check, and a flip at position 5 gives 1 0 1, which is 5. The receiver flips that bit back, and the block is repaired.
Try it: step Check and repair to Parity checks. Three light-blue parity cards join the four data cards, and the board shows the last block that failed a check, with the failing circles in red and the number they spell. Step on to Repaired and watch the receiver fix the bit and the display spell HELLO again.
When the code is fooled
The code assumes at most one flip per block. If two bits flip, two sets of circles change and the pattern points at a third bit that was fine. The receiver dutifully flips it, and the block ends up with three wrong bits. Slide Chance a bit flips up to 15% to see the board say so. At a 15% chance per bit, about 28 blocks in 100 take two or more flips, against 48 in 100 that go wrong with no code at all.
At 5% per bit the numbers are much kinder. With no code, 18.5% of four-bit blocks arrive wrong. With the code, only blocks with two or more flips among their seven bits are lost: 4.4%. At 1% per bit, the code cuts wrong blocks from 3.9% to 0.2%. The cost is that three bits in every seven carry no message.
Codes everywhere
Every technology that stores or sends data uses error-correcting codes. The memory in servers uses a Hamming code with one more parity bit over the whole block, which lets it fix any single flip and detect, though not fix, any two. QR codes and the discs that came before streaming use Reed–Solomon codes, which repair whole runs of damaged bits, so a scratched disc still plays and a smudged QR code still scans. Wi-Fi, mobile networks and spacecraft use much longer codes that a computer decodes by weighing probabilities.
Claude Shannon showed in 1948 that every noisy channel has a capacity, a top rate of reliable information per bit sent. Below that rate, codes exist that make errors as rare as you like; above it, no code can. For a line that flips 5% of bits the capacity is about 0.71 data bits per bit sent. Hamming’s code runs at 4/7, or 0.57, and still lets some errors through. Modern codes come within a whisker of Shannon’s limit.
What this model leaves out
Each bit here flips on its own with the same, known chance. Real noise often comes in bursts that hit several neighbouring bits at once, which is why practical systems shuffle bits between blocks before sending them and use codes built for bursts. Real receivers also measure how sure they are of every bit, not just 0 or 1, and good decoders use that. Hamming’s code is the simplest code that corrects errors, not the one most systems use today. The sparks, cards and pulses are drawn for clarity and slowed down by many millions of times, and the red edges on flipped cards show what only someone who knew the original could see.