Why a scratched CD still plays: the mathematics of deliberate redundancy
A music CD survives dust and scratches because its data is written twice over in a clever way. A Reed–Solomon code adds carefully chosen extra information, and the bits are shuffled across the disc so a single scratch damages only scattered fragments of any one passage. The player quietly rebuilds what the scratch destroyed.
Coding theory pulls in two opposite directions. Compression strips out wasteful repetition so data travels lighter, as the DEFLATE method does to shrink files sent over the internet. Error correction does the reverse, adding useful repetition so a message survives a noisy channel. Claude Shannon's founding work measured the uncertainty in a message as entropy and showed that no compression scheme can squeeze data below that limit.
The crudest error-correcting scheme is to send every block three times and let the receiver take a majority vote bit by bit. On a CD the trick is interleaving: the data is split into smaller blocks and sent one bit from each in rotation, so a burst of damage lands on many different blocks instead of wiping out one. Other channels need other codes. Deep space links fight steady thermal noise in the receiver, whereas mobile phone signals can fade sharply if the handset moves just a few inches.
Good codes are tied to an old puzzle about packing spheres. Push pennies together on a table and they settle into a honeycomb, each touching six neighbours. Codes do the same in many more dimensions; the Golay code used for deep space works in 24. In a handful of dimensions the packing fills space perfectly, giving the rare perfect codes: the Hamming codes and two Golay codes. More dimensions also mean more neighbours, and so more ways for noise to nudge a message into the wrong one.
The pioneers were busy after the war. The binary Golay code of 1949 fixes up to three errors in every 24-bit word and spots a fourth. Richard Hamming won the 1968 Turing Award for his Bell Labs work on such codes. In 1972 Nasir Ahmed proposed the discrete cosine transform, now underneath JPEG, MPEG and MP3.
Source: Coding theory
