Fixing Errors on the Fly

Lesson 9 of 11 · 7 min · Free, no account needed

What you will learn

Error correction adds spare bits so the receiver can find and fix flipped bits itself.
In the three circles, 4 data bits travel with 3 parity bits: a Hamming code.
The odd circles point at the one bit that flipped.
Spare bits are redundancy: the trick is to need as few as possible.

Tear pieces off a QR code. Your phone still reads it. How?
Tap the yellow spots to tear pieces off.
Three circles, seven bits. Every circle must hold an even number of 1s.
The 4 data bits sit where circles overlap. Drag a 0 or a 1 onto each purple place.
Send it through a noisy wire.
One bit will flip. Step through what the receiver checks.
Error correction.
Error correction: the receiver finds a flipped bit and fixes it, without asking for the message again.
Redundancy: the extra bits that make it possible. Here 7 bits carry 4.
This circle code is a Hamming code (Richard Hamming, 1950). QR codes and space probes use stronger cousins of it.
Three messages arrived with one bad bit each. Repair them.
Tap the bit that is inside every red circle and outside every green one.
Encode your own message.
Pick any 4 data bits, then set the purple bits so all three circles are even.
Noisy channel: repair every message before it lands on Mars.
Noise may flip one bit. Tap it, or press No error if every circle is even.
The plain way to survive noise is to send every bit three times.
How many bits does that take for a 100 bit message? Drag the marker.
Only one circle is red this time. What broke?
Tap the bit to repair.
Race: which gets 100 bits across first?
Tap your bet, then run the race.

Lessons are interactive and need JavaScript. Turn it on to play them.