Error-correcting codes explained

No channel is perfect. Cosmic rays flip bits in memory, scratches erase parts of a disc, and radio signals fade. Instead of hoping for the best, digital systems add redundancy in a clever way, so that the receiver can work out what was sent even when some of it arrives wrong. The mathematics of these codes, begun in the late 1940s, quietly protects nearly every bit we store or send.

Three overlapping circles holding the seven bits of a Hamming codeword, one circle highlighted where a parity check fails
Three overlapping circles holding the seven bits of a Hamming codeword, one circle highlighted where a parity check fails

Detecting errors with parity

The simplest protection is a single parity bit: add a 1 or a 0 so that the total number of 1s is even. If one bit flips on the way, the count turns odd and the receiver knows something went wrong. Parity cannot say which bit is wrong, and two flips cancel out unnoticed, but it is cheap, and it was used for decades in memory and serial links. Detecting an error is only half the job, though: then the data must be sent again.

Correcting by repetition

To correct an error without asking again, the receiver needs enough redundancy to outvote it. Sending every bit three times, 000 or 111, lets the receiver take the majority: one flip in a triple is corrected. The price is steep: three bits for every bit of data, and two flips in the same triple still win. The question that started coding theory was whether one could do better.

Hamming's code

In 1947 Richard Hamming worked at Bell Labs on a relay computer that read programs from punched cards. When it found an error over the weekend it simply stopped, and Hamming came back on Monday to wasted runs. If a machine can detect an error, he asked, why can't it locate and correct it? His answer, published in 1950, sends 4 data bits as 7. Three parity bits, at positions 1, 2 and 4, each check a different overlapping group of positions, chosen so that every single error breaks a unique combination of checks.

The syndrome

The receiver recomputes the three checks. If all pass, the word is accepted. If some fail, writing the failing checks as binary digits, with check 4 as the highest digit, gives a number from 1 to 7: the syndrome, which is exactly the position of the flipped bit. Flipping it back restores the codeword. The trick works because the positions are numbered so that each one's binary expansion lists the checks it belongs to, which is why the code looks so tidy when drawn as three overlapping circles.

Hamming distance

The Hamming distance between two words is the number of positions where they differ. In the (7,4) code any two codewords are at least 3 apart. A word with one error is still at distance 1 from the codeword that was sent and at least 2 from every other, so decoding to the nearest codeword corrects it. In general a code whose codewords are at least d apart detects d − 1 errors and corrects (d − 1)/2 of them, rounded down. Adding an overall parity bit raises the distance to 4, giving the extended code that corrects one error and detects two.

Shannon's limit

In 1948, two years before Hamming's paper, Claude Shannon proved a startling theorem. Every noisy channel has a capacity, and data can be sent at any rate below it with as few errors as you like, by using long enough codes; above it, errors cannot be avoided. Shannon showed that such codes exist but not how to build them. Finding practical codes that come close to his limit took half a century, from Reed-Solomon codes in 1960 to turbo codes in 1993 and the rediscovery of low-density parity-check codes.

Claude Shannon, who in 1948, at Bell Labs, made precise how much information a message contains and measured it in bits.
Claude Shannon, who in 1948, at Bell Labs, made precise how much information a message contains and measured it in bits.

Codes all around us

Reed-Solomon codes let CDs play through scratches and QR codes scan with up to 30% of the symbol damaged. Server memory uses extended Hamming codes to fix single flipped bits caused by cosmic rays. Voyager's pictures of the outer planets were protected by Golay and later Reed-Solomon codes, and the LDPC and polar codes of 5G and Wi-Fi squeeze out nearly every bit the channel allows. Even the barcode on a book and the last digit of a bank account number are simple error-detecting codes.

Explore it

Open the error-correcting code simulator to encode any four data bits with the Hamming (7,4) code, flip bits by clicking them in the circles or in the row, and watch the failing circles and the syndrome point at the error before the decoder repairs it. Switch on the extra parity bit to see double errors detected, and send a message through a noisy channel to compare what arrives with and without the code.

Frequently asked questions

What is the difference between error detection and error correction?

Detection only tells the receiver that something is wrong, so it must ask for the data again; a parity bit or a checksum does this. Correction lets the receiver reconstruct the original without asking, which needs more redundancy. Systems that cannot ask again, such as a space probe millions of kilometres away or a DVD, rely on correction.

Why not just send everything twice?

Two copies show that an error happened but not which copy is right, and they double the cost. Three copies allow a majority vote but triple it. Hamming's code corrects a single error per block of seven with less than double the bits, and longer codes do far better.

Who was Richard Hamming?

An American mathematician, 1915 to 1998, who worked on the Manhattan Project and then for thirty years at Bell Labs. Besides his codes, he is known for the Hamming window in signal processing, for the Hamming distance, and for his lecture You and Your Research. He received the Turing Award in 1968.

Can a code correct any number of errors?

Only with enough redundancy. A code can correct up to (d − 1)/2 errors per block, where d is the minimum distance between codewords, and longer codes with more check bits reach larger d. Shannon's theorem sets the ultimate limit: no code can beat the channel's capacity.

Ready to try it?

Open PictorX in your browser — no install, no credit card required to start.

Open the error-correcting code simulator