RightSignal

Algorithms · 13 of 131 / 3

Error-correcting codes

The concept

Why a scratched DVD still plays perfectly

A scratched disc still plays without a skip because it stores more than the song: extra numbers computed from that same data, used to spot and fix damage.

Those extra numbers are called error-correcting codes. If a few bits go missing or get flipped, the player treats it like a sudoku puzzle: enough of the picture is still there to work out exactly what the missing pieces must have been.

Algorithms · 13 of 132 / 3

Error-correcting codes

Real-life use case

Tear the corner off a QR code and it still scans

Point your phone at a QR code with a torn corner or a coffee stain over part of it, and it still opens the right link. A video call also stays clear even when some data gets lost or garbled on a shaky Wi-Fi connection.

Both the QR code and your phone's wireless connection carry the same kind of extra clues. That is why they keep working even when a chunk of the pattern is physically missing or scrambled.

Algorithms · 13 of 133 / 3

Error-correcting codes

How it helps

The extra clues rebuild what's missing, like a sudoku puzzle

The trick is to add numbers computed from the real data, not random padding, so a damaged piece can be worked out from what survived. Example: know three ages and their total, and you can still find a forgotten age exactly.

Add enough of these clues and a lot of damage can be rebuilt exactly, not just noticed. Add too few, and the system can only tell you something broke, without being able to fix it.

Got it?

5 quick questions on Error-correcting codes.

Learn first: Hamming distance
Related: Exponential backoff · B-trees · Bloom filters · CPU scheduling
In the brief: Concept of the day, Tue, Oct 13

Your RightSignal

Topics in News

Why a scratched DVD still plays perfectly

Tear the corner off a QR code and it still scans

The extra clues rebuild what's missing, like a sudoku puzzle

Got it?