Loading field map
Coding theory is the branch of discrete mathematics concerned with the reliable transmission and storage of data across imperfect channels. Its central problem is deceptively simple: how can a message be represented so that, even if some of its symbols are corrupted by noise, the original information can still be recovered? The field answers this question by designing codes—structured sets of strings over a finite alphabet—and by studying the mathematical trade-offs between the efficiency of a code, the amount of error it can correct, and the complexity of encoding and decoding.
The subject is often divided into two complementary halves. Source coding (or data compression) deals with removing redundancy from a message so that it can be transmitted using as few symbols as possible. Channel coding (or error-correcting coding) deals with deliberately adding redundancy so that errors introduced during transmission can be detected or corrected. While both are essential to modern communication, the term "coding theory" in discrete mathematics most often refers to channel coding, and this article follows that emphasis.
To make the problem precise, one fixes a finite set of symbols called an alphabet, typically the binary alphabet {0, 1}. A block code of length n is a subset of all possible strings of length n over this alphabet; each string in the subset is called a codeword. A message is encoded by mapping it to one of these codewords, transmitted, and then decoded by the receiver, who must guess which codeword was sent based on the possibly corrupted string received.
The central mathematical object is the Hamming distance between two strings: the number of positions in which they differ. The minimum distance of a code is the smallest Hamming distance between any two distinct codewords. This single number governs the code's error-correcting power. If the minimum distance is d, then the code can detect up to d − 1 errors per received word and correct up to ⌊(d − 1)/2⌋ errors, because the spheres of radius ⌊(d − 1)/2⌋ around distinct codewords do not overlap. The receiver decodes by choosing the codeword closest to the received string—a rule called maximum-likelihood decoding when all codewords are equally likely.
The fundamental tension of the field is captured by three parameters: the length n, the number of codewords M (or equivalently the information rate k/n, where k = log₂ M), and the minimum distance d. A good code wants a large rate (to transmit efficiently), a large minimum distance (to correct many errors), and a small length (to minimize delay). These goals conflict. The central questions of coding theory are: What combinations of these parameters are achievable? How can one construct codes that achieve them? And how can one decode such codes efficiently in practice?
The modern field began with the work of Richard Hamming and Claude Shannon in the late 1940s, though their motivations and conclusions were strikingly different.
Shannon's 1948 information theory established a fundamental limit: for a given noisy channel, there exists a quantity called the channel capacity such that reliable communication is possible at any rate below capacity, provided one uses sufficiently long codes. Shannon's proof was nonconstructive—it showed that randomly chosen codes would work with high probability, but gave no practical way to find or decode them. This result reframed the entire problem: the question was no longer whether reliable communication was possible, but how to achieve it efficiently.
Hamming, working at Bell Labs on mechanical relay computers, faced a more immediate problem. His machines would halt when they detected an error in a computation, and he wanted a way to continue despite the error. In 1950 he introduced the first family of error-correcting codes, now called Hamming codes. These are linear codes—codewords form a vector space over the binary field—with a particularly simple structure. The (7,4) Hamming code encodes 4 bits of information into 7 bits, can correct any single error, and its decoding rule can be implemented by checking a small set of parity equations. Hamming's work established the template for much of what followed: linear codes with algebraic structure, designed for a specific error-correction capability, with efficient decoding algorithms.
These two threads—Shannon's probabilistic existence results and Hamming's explicit algebraic constructions—have coexisted ever since. The former sets the outer limits of what is possible; the latter provides the actual codes used in practice.
The dominant approach for several decades was to construct codes with rich algebraic structure, which made both analysis and decoding tractable. The foundational observation is that if the alphabet is a finite field (such as the binary field GF(2) or its extensions), then a code can be defined as the set of all polynomials of degree less than k evaluated at n distinct points. These are called Reed–Solomon codes, introduced in 1960. Their minimum distance is n − k + 1, which is optimal for their parameters in a sense made precise by the Singleton bound. Reed–Solomon codes found widespread use in compact discs, QR codes, and deep-space communication.
A closely related family, BCH codes (named after Bose, Chaudhuri, and Hocquenghem), generalize Hamming codes to correct multiple errors. Their algebraic structure—codewords correspond to polynomials whose roots include certain consecutive powers of a primitive element—allows decoding via a sequence of algebraic steps: computing syndromes, solving a linear system for the error locator polynomial, and finding its roots. This syndrome-based decoding became the standard technique for algebraic codes.
The algebraic tradition reached a natural culmination with the discovery of Goppa codes in the 1970s, which are defined using algebraic curves over finite fields. These codes generalize Reed–Solomon codes and were later shown to meet the Gilbert–Varshamov bound—a guarantee that codes with certain parameters exist—for large lengths. Goppa codes also became the basis for the McEliece cryptosystem, one of the oldest post-quantum cryptographic proposals.
The strength of the algebraic approach is its explicitness: codes are described by compact formulas, their parameters can be computed exactly, and decoding algorithms are deterministic and well understood. Its weakness is that algebraic structure imposes constraints. The best algebraic codes do not always achieve the best possible parameters, and for very long codes, the decoding algorithms become computationally expensive.
Running parallel to the algebraic tradition is a more probabilistic and combinatorial line of work. This tradition asks not "what structured codes exist?" but "what is the best possible performance, and can random or unstructured codes approach it?"
The Gilbert–Varshamov bound, proved in the 1950s, is a simple counting argument showing that codes with certain parameters must exist. The proof is greedy: one repeatedly adds a codeword that is at distance at least d from all previously chosen codewords, and a volume argument shows this process cannot get stuck too early. This bound guarantees the existence of codes that are, in a precise sense, as good as any known explicit construction for many parameter ranges.
The probabilistic method, championed by Shannon, goes further. For a random code—each codeword chosen independently and uniformly at random—the probability that the code has poor distance or rate is exponentially small. This shows that "most" codes are good, even though no one can explicitly describe a specific one. The catch is decoding: for a random code, the maximum-likelihood decoding problem is computationally intractable in general. This is the central tension of the field: good codes exist, but finding ones that are both good and efficiently decodable is hard.
This tension was partially resolved by the theory of low-density parity-check (LDPC) codes, introduced by Robert Gallager in his 1963 doctoral thesis but largely ignored for decades. An LDPC code is defined by a sparse parity-check matrix—a matrix with very few ones per row and column. The sparsity allows a decoding algorithm called belief propagation, which passes messages along the edges of a bipartite graph and converges to the correct codeword with high probability for long codes. Gallager showed that randomly chosen LDPC codes could approach the Shannon limit, but the computational resources of the 1960s made them impractical, and they were forgotten.
The probabilistic tradition also produced important impossibility results. The Hamming bound (also called the sphere-packing bound) limits how many codewords a code with given length and distance can have, because the spheres of radius ⌊(d − 1)/2⌋ around codewords must be disjoint. The Plotkin bound and the Singleton bound give further restrictions. These bounds do not tell one how to construct good codes, but they define the frontier of what is achievable, and much of the field's history is a story of constructions inching closer to these limits.
The field was transformed in the 1990s by two developments that brought the probabilistic and algebraic traditions together.
First, turbo codes, introduced in 1993 by Berrou, Glavieux, and Thitimajshima, achieved performance astonishingly close to the Shannon limit using a combination of two convolutional encoders and an iterative decoding algorithm. The key insight was that decoding could be performed by passing soft information—probabilities, not just hard decisions—back and forth between two decoders, refining the estimate of each bit over many iterations. This was a practical breakthrough that made near-optimal error correction feasible.
Second, LDPC codes were independently rediscovered in the mid-1990s, and it was recognized that they too could be decoded by iterative message-passing algorithms. The connection between LDPC codes and turbo codes was soon understood: both are instances of codes on graphs, where the code is defined by a factor graph and decoding proceeds by belief propagation on that graph. This unified perspective, developed by researchers such as David MacKay and others, showed that the algebraic and probabilistic traditions were not opposed but complementary. The algebraic tradition provided structured codes with guaranteed minimum distance; the probabilistic tradition provided codes with excellent average-case performance and efficient iterative decoding.
The modern landscape is characterized by a rich interplay between these approaches. Polar codes, introduced by Erdal Arıkan in 2009, are the first family of codes proven to achieve the Shannon limit for binary-input symmetric channels with an explicit construction and a decoding algorithm of polynomial complexity. They achieve this by a process of channel polarization: by combining and splitting channels in a recursive manner, some virtual channels become noiseless while others become pure noise, and information is sent only over the good ones. Polar codes have been adopted in fifth-generation (5G) wireless communication standards.
At the same time, the algebraic tradition continues to develop. Algebraic geometry codes and their generalizations remain an active area of research, particularly for applications requiring very long codes or specific algebraic properties. The search for codes that meet or approach the best known bounds continues, and the field now includes sophisticated tools from finite geometry, group theory, and computational algebra.
A code is only as useful as its decoder. Throughout the field's history, the difficulty of decoding has shaped which codes are considered practical. Maximum-likelihood decoding is NP-hard for general linear codes, meaning that no efficient algorithm is known and none is expected to exist. This is why the algebraic tradition emphasized codes with special structure that permits polynomial-time decoding, and why the probabilistic tradition focused on codes whose graph structure enables iterative decoding.
The distinction between hard-decision decoding (which commits to a single received symbol) and soft-decision decoding (which uses reliability information about each symbol) is also fundamental. Soft-decision decoding is more powerful but more complex; modern iterative decoders for turbo and LDPC codes are soft-decision algorithms. The trade-off between decoding complexity and error-correction performance is a central engineering concern, and much of the field's applied research is devoted to finding the right balance for specific channels and applications.
Coding theory today is a mature field with a clear intellectual structure. Its core is the study of codes as combinatorial objects with algebraic or probabilistic structure, governed by fundamental bounds and characterized by their parameters. Its methods draw on linear algebra, finite fields, algebraic geometry, graph theory, and probability theory. Its applications span virtually all digital communication: wireless networks, satellite links, deep-space probes, data storage (from hard drives to flash memory), optical fiber, and quantum communication, where a parallel theory of quantum error correction has developed.
The field is not organized into rival schools in the sense of competing paradigms that exclude one another. Rather, it is organized around a shared set of questions—What codes exist? How good are they? How can they be decoded?—with different research traditions emphasizing different methods. The algebraic tradition values explicit construction and guaranteed performance; the probabilistic tradition values asymptotic optimality and average-case behavior; the iterative-decoding tradition values practical algorithms that work well on real channels. These traditions have converged substantially since the 1990s, and contemporary research often combines elements of all three.
The most active current frontiers include the search for codes with better trade-offs between rate, distance, and decoding complexity; the development of codes for new channel models (such as channels with memory, burst errors, or adversarial errors); and the extension of coding theory to quantum information. The field's foundational results—Shannon's capacity theorem, the Hamming bound, the Gilbert–Varshamov bound—remain as relevant today as when they were proved, and they continue to define the space within which all coding schemes must operate.