How Error-Correcting Codes Work

01 The Problem: Noisy Channels

Every digital transmission faces a fundamental adversary: noise. Whether a signal travels through a copper wire, a fiber optic cable, a radio wave, or the vacuum of space, physical interference corrupts the bits. A zero flips to a one. A packet vanishes entirely. Without protection, a single bit error in a compressed file can render the entire document unreadable. The question that launched coding theory was deceptively simple: can we add structured redundancy to data so that corruption can be not only detected but automatically repaired?

The answer transformed telecommunications. When Richard Hamming was working at Bell Labs in the late 1940s, he grew frustrated with punched card readers that detected errors but could not correct them — forcing him to rerun jobs from the beginning. His solution, published in 1950, was the first systematic error-correcting code: a method to encode four data bits with three check bits so that any single-bit error could be located and fixed automatically. The Hamming(7,4) code was born, and with it the entire discipline of coding theory.

02 Parity: The Simplest Detection

The most primitive form of error protection is the parity bit. A single extra bit appended to a group of data bits indicates whether the count of ones in the group is even or odd. If a single bit flips during transmission, the received parity will disagree with the recomputed parity — the receiver knows something went wrong. The cost is minimal: one bit of overhead per group. But the capability is equally minimal. Parity detects an odd number of bit flips; it is blind to two-bit errors, and it cannot correct anything. It tells you that corruption occurred, not which bit is wrong.

Hamming's insight was to generalize parity into a system of overlapping checks. Instead of one parity bit for the whole group, assign multiple parity bits, each covering a different subset of the data bits. The pattern of which parity checks pass and which fail creates a binary address — a syndrome — that points directly to the corrupted bit. This is the core mechanism shared by every error-correcting code: redundancy arranged so that the pattern of violations uniquely identifies the error location.

03 Hamming Codes: Locating the Error

The Hamming(7,4) code encodes four data bits into seven transmitted bits by adding three parity bits. The parity bits occupy positions that are powers of two — positions 1, 2, and 4 — while data bits fill the remaining positions 3, 5, 6, and 7. Each parity bit checks every position whose binary representation includes that bit's position in its address. Position 3 (binary 011) is checked by parity bits at positions 1 and 2. Position 5 (binary 101) is checked by parity bits at positions 1 and 4. This overlapping coverage means every single-bit error produces a unique combination of parity failures.

When the receiver recomputes all three parity checks, the resulting three-bit syndrome is a number from 0 to 7. A syndrome of 0 means no error. A syndrome of 3 means position 3 is corrupted. A syndrome of 5 means position 5 is corrupted. The receiver simply flips the indicated bit and recovers the original data perfectly. The overhead is substantial — three check bits for four data bits, a code rate of 4/7 ≈ 0.571 — but the guarantee is powerful: any single-bit error is detected and corrected without retransmission.

04 Beyond Single Errors: BCH and Reed-Solomon

Hamming codes handle one error per block. But real channels produce bursts — consecutive runs of corrupted bits caused by scratches on a disc, lightning strikes on a radio link, or dropout in a storage medium. The breakthrough for multi-error correction came in 1960 when Irving Reed and Gustave Solomon published a code that operates not on individual bits but on symbols — groups of bits treated as elements of a finite field.

Reed-Solomon codes encode a message as a sequence of coefficients of a polynomial. The encoder evaluates this polynomial at multiple points, producing more evaluation points than there are coefficients. If some points are corrupted, the receiver can still recover the original polynomial as long as enough uncorrupted points remain. The mathematics of finite fields — Galois theory applied to practical engineering — gives RS codes a remarkable property: a code that adds 2t check symbols can correct up to t corrupted symbols, each of which may contain multiple bit errors packed into a burst.

05 Convolutional Codes and the Viterbi Algorithm

Block codes process data in fixed chunks. Convolutional codes take a different approach: they process a continuous stream of bits, where each output bit depends on the current input and several previous inputs. The encoder maintains a shift register — a memory of recent bits — and produces output bits as linear combinations of the register contents. The result is a code with memory, where the influence of any input bit spreads across multiple output bits.

Decoding convolutional codes was historically expensive until Andrew Viterbi published his algorithm in 1967. The Viterbi algorithm performs maximum-likelihood decoding by tracing the most probable path through a trellis — a graph representing all possible encoder states over time. At each step, it keeps only the best path to each state, discarding alternatives. The algorithm's elegance is that it finds the optimal decoded sequence without exhaustive search, making real-time decoding feasible. Convolutional codes with Viterbi decoding became the workhorse of satellite communication, including the Voyager deep-space missions that relied on them to transmit data across billions of kilometers.

06 Modern Codes: Turbo and LDPC

The theoretical foundations laid by Claude Shannon in 1948 proved that reliable communication is possible at any rate below channel capacity, but for decades the practical codes that approached this limit were computationally infeasible. The breakthrough came in the 1990s. In 1993, Claude Berrou and colleagues introduced turbo codes, which combine two convolutional codes with an interleaver and decode them iteratively — each decoder passes soft information to the other until they converge on a solution. In 1996, researchers rediscovered low-density parity-check (LDPC) codes, first proposed by Robert Gallager in 1960 but ignored for decades because they were computationally impractical with the hardware of the time.

Both turbo and LDPC codes approach the Shannon limit — the theoretical maximum efficiency — within fractions of a decibel. LDPC codes are now used in 5G NR, Wi-Fi 802.11n/ac/ax, DVB-S2 satellite broadcasting, and 10-gigabit Ethernet. The gap between Shannon's proof and practical implementation spanned nearly fifty years, a testament to how theoretical limits can outpace engineering capability by generations.

07 Where Error Correction Lives

Error-correcting codes are invisible infrastructure. When a CD plays despite a scratch, a QR code scans despite partial damage, a satellite streams data from deep space, or a solid-state drive retains data after years of use, error correction is doing the work. Reed-Solomon codes guard the data on CDs, DVDs, and Blu-ray discs. QR codes embed Reed-Solomon error correction at selectable levels — the highest level can recover up to 30% of the code's data modules. The Voyager spacecraft used convolutional codes and Reed-Solomon codes together to transmit data from the outer solar system with bit error rates below 10⁻⁶ over links with raw error rates orders of magnitude higher.

Modern systems layer multiple codes. A 5G downlink might use LDPC for data channels and polar codes for control channels. A hard drive applies an outer Reed-Solomon code over an inner modulation code, catching errors the inner code misses. The principle is always the same: add mathematical structure that the channel cannot destroy, so that the receiver can reconstruct what was sent even when the physical signal arrives damaged. Error-correcting codes are the reason digital storage and communication work at all — the silent mathematics that makes the digital world reliable.