Adding structured redundancy to a message so that errors introduced in storage or transmission can be detected and repaired without asking for a retransmission. Every hard drive, phone call, deep space probe and QR code depends on it, and it is largely invisible.
Every physical channel corrupts what passes through it. Radio picks up noise, storage media degrade, cosmic rays flip bits in memory, and scratches obscure discs.
Simple repetition works and is wasteful. Sending everything three times and taking the majority triples the cost to correct one error in three, which is a poor exchange.
The question Claude Shannon answered in 1948 is how good the exchange can be made. His noisy channel coding theorem states that every channel has a capacity, and that transmission with arbitrarily small error probability is possible at any rate below it.
The theorem is remarkable for what it does not do: it proves that good codes exist without constructing one. Shannon's argument shows that a randomly chosen code is almost certainly good, which is a proof of existence that gives no method. Finding practical codes approaching the limit took the following fifty years.
The key idea is distance. Of all possible strings of a given length, only some are valid codewords, and the code is designed so that valid codewords differ from each other in many positions.
Hamming distance counts the positions in which two strings differ. If every pair of valid codewords differs in at least three positions, then any single error produces a string that is still nearer to the original codeword than to any other, and the receiver corrects by choosing the nearest valid codeword.
Detecting errors needs less separation than correcting them. A code with minimum distance d detects up to d minus one errors and corrects up to half that.
Richard Hamming produced the first practical error-correcting code at Bell Labs in 1950, out of frustration: the weekend batch runs on the relay computer would find an error, abort, and waste the whole run. His code adds parity bits at power-of-two positions such that the pattern of failed parity checks gives the binary address of the corrupted bit directly.
Different channels fail differently, and the codes are matched to the failure mode.
Reed-Solomon codes, from 1960, correct bursts of consecutive errors, which is what a scratch or a dust particle produces. They are used on CDs, DVDs, in QR codes and in deep space communication. A CD can lose a track of over four thousand consecutive bits and reconstruct the audio exactly.
Convolutional codes with Viterbi decoding operate on a continuous stream rather than blocks and were standard in satellite and mobile communication.
Low-density parity-check codes were invented by Robert Gallager in 1962, found impractical for the hardware of the time, and forgotten for thirty years. Rediscovered in the 1990s, they perform close to the Shannon limit and are now used in Wi-Fi, 5G, and modern storage.
Turbo codes, from 1993, achieved similar performance by a different route and prompted the rediscovery of Gallager's work.
Every hard drive and solid state drive corrects errors continuously; the raw error rate of the physical medium is far too high to use directly, and the drive's reported reliability is a property of the coding rather than the material.
Server memory uses error-correcting codes to survive bit flips from cosmic rays, which occur often enough at scale to matter and are the reason data centre memory differs from consumer memory.
The Voyager probes used codes to return usable images from beyond the solar system with transmitter power comparable to a refrigerator bulb.
Quantum error correction is a distinct and much harder problem, because a quantum state cannot be copied and measuring it destroys it. The codes that solve it, principally the surface code, are the central obstacle between current quantum processors and useful ones.
Reliability at the system level does not require reliability at the component level. It requires knowing how components fail and building structure that survives it.
That principle came out of coding theory and has spread well beyond it, into distributed systems, storage replication and consensus protocols. Shannon's result is that noise sets a limit on rate, not on accuracy, and almost all modern communication is built on taking that literally.
