How does a scratched CD still play?

Every message that travels or gets stored is damaged a little on the way. Electrical noise on a wire, a speck of dust on a disc, a cosmic ray hitting a memory chip: each can turn a bit (a single 0 or 1) into its opposite. Engineers call this a bit flip, and the path the bits take, whether a cable, a radio link or a disc, a channel.

A common belief is that a digital copy is perfect because a digital channel is perfect. It isn’t. Digital copies are perfect because the bits carry extra information that lets the receiver find and repair the damage. That extra information is an error-correcting code, and this page builds one from scratch.

Sending a picture through a noisy channel

The obvious defence is repetition. Send every bit three times and let the receiver take a vote: if it gets 1, 1, 0, it assumes the bit was a 1. A single flip is outvoted. The price is that you send three times as many bits.

Below, a 32 × 20 picture (640 bits, one per pixel) goes through a channel that flips each bit with the probability you set. Pixels that arrive wrong are shown in red. Compare no protection with the three-times vote, and with a fourth method, Hamming(7,4), which we’ll take apart in a moment. Watch both columns of numbers: the errors left and the bits it cost to send.

At 5% noise, an unprotected picture loses about 32 of its 640 pixels on average. Voting brings that down to about 5, because a pixel is lost only when two of its three copies flip. Hamming’s code leaves about 12, more than voting, but it sends 1,120 bits instead of 1,920. At 1% noise the gap nearly closes: about 6 wrong pixels unprotected, and under 1 for either code. Turn the noise up past about 10% and every method struggles: a code is built for a certain amount of damage, and beyond it, it fails.

Three circles that find a flipped bit

In 1947 Richard Hamming was using the relay computers at Bell Telephone Laboratories. Over weekends nobody was there to restart them, and the machines could detect an error but not fix it: they simply abandoned the job. After coming in two weekends in a row to find his work thrown away, he asked: if a machine can tell that an error happened, why can’t it tell where? His answer was published in 1950.

The idea starts with a parity bit: an extra bit chosen so that a group of bits holds an even number of 1s. If one bit in the group flips, the count becomes odd, and you know something went wrong, though not which bit. Hamming’s trick is to use several overlapping groups. Each bit belongs to a different combination of groups, so the pattern of groups that fail identifies the culprit.

Hamming(7,4) protects 4 data bits (d1–d4) with 3 parity bits (p1–p3), 7 bits in all. Draw three overlapping circles, A, B and C. Put a data bit in each region where circles overlap, and a parity bit in each region that belongs to one circle only. Each parity bit is set so its circle holds an even number of 1s.

Seven bits have exactly seven places for a single error to land, and three circles that can each pass or fail give seven different failure patterns (plus “all pass”). So every single error has its own fingerprint, and the receiver can correct it with no guessing and no resending. The cost is 3 extra bits per 4 data bits, against 8 extra for sending everything three times.

Two errors defeat it, and in the worst way. Two flips make a failure pattern too, and it is always the fingerprint of some third bit. The decoder can’t tell the difference, so it “corrects” that third bit, and the word ends up with three errors. The reason is distance: any two valid 7-bit codewords differ in at least 3 places. One flip leaves you 1 step from the right codeword and at least 2 from any other, so the nearest one is right. Two flips can leave you closer to the wrong one.

Why a scratch is different

Noise on a wire tends to flip bits here and there, one at a time. A scratch on a disc is different. It destroys a long unbroken run of bits, called a burst. A Hamming codeword is only 7 bits long, so a burst of 20 bits wipes out three codewords completely. Each has many errors, far more than one per codeword.

The fix is to shuffle the bits before storing them, so that neighbours on the disc belong to different codewords. This is interleaving. With an interleaving depth of 16, the disc stores bit 1 of 16 codewords in a row, then bit 2 of the same 16, and so on. A scratch across 16 neighbouring bits now hits 16 different codewords once each, and every one of those single errors can be corrected.

The rule is simple: with depth D, any burst of up to D bits touches each codeword at most once, so it is always fully corrected. Longer bursts may still be fixed if they happen to fall kindly, but there is no guarantee. Nothing comes free. The receiver must hold 7D bits in memory before it can unshuffle them, which adds delay.

What a real CD does

A compact disc, which Philips and Sony brought to market in 1982, uses the same two ideas with stronger parts. Instead of Hamming codes it uses two Reed–Solomon codes, invented by Irving Reed and Gustave Solomon in 1960. They work on whole bytes (8 bits) rather than single bits, so a byte with all 8 bits wrong counts as one error. The two codes are interleaved crosswise with long delays between them, a scheme called CIRC (cross-interleaved Reed–Solomon code). For every 3 bytes of music it stores 1 extra byte.

CIRC corrects a burst of about 4,000 bits completely, which is about 2.5 mm of track. Beyond that, up to about 12,000 bits (7.5 mm), the player can’t recover the true samples, but because the interleaving leaves good samples on both sides of each lost one, it fills the gaps by interpolation: it guesses each missing value from its neighbours. Your ear doesn’t notice. Only larger damage makes a disc skip or click.

How long is that on a real disc? The laser reads the spiral track as it passes at a constant speed of 1.2 to 1.4 metres per second, so a millimetre of track goes by in less than a millisecond. A CD carries 44,100 sound samples per second for each stereo channel.

Most scratches don’t run along the track, though. A scratch straight across the disc, from the centre outwards, crosses each turn of the spiral for only its own width, a fraction of a millimetre, so each turn suffers a short burst that CIRC fixes easily. A scratch that follows the circle of the track is the dangerous kind.

All of this sits under a limit found by Claude Shannon in 1948, two years before Hamming’s paper. Shannon proved that every noisy channel has a capacity: below that rate, codes exist that make errors as rare as you like; above it, none do. He didn’t say how to build such codes. Hamming’s codes were one of the first steps toward them. (The three-circle picture is a later teaching device; Hamming described the same checks with binary position numbers.)