- Atlas
- Mathematics
- Coding Theory
Coding Theory
Coding theory is the mathematics of making messages survive a hostile channel.
10 frameworks, from 1948 to today · Combinatorics · Mathematics
- Shannon information theory 1948-Present
- Algebraic block coding 1950-Present
- Combinatorial coding theory 1952-Present
- Convolutional code 1955-1995
- Algebraic geometry code 1981-Present
- Iterative decoding and capacity-approaching codes 1993-Present
- Quantum error correction 1995-Present
- Network coding 2000-Present
- Distributed storage coding 2007-Present
- Polar Coding 2008-Present
Overview
Coding theory is the mathematics of making messages survive a hostile channel1. A sender wants to transmit data—across a noisy telephone line, from a deep-space probe, off a scratched disc, or between servers in a data centre—and the channel may corrupt some of it1. The coder adds redundancy in a controlled way so that the receiver can detect or correct errors, and the theory asks how much redundancy is necessary, how to construct codes that achieve it, and how to decode them efficiently12. The field sits inside combinatorics because its central objects—codes—are finite sets of words with prescribed distance structure, and its deepest questions are about packing, counting, and algebraic structure. But its history is driven by engineering demand as much as by pure curiosity: each era's codes were built to solve a problem that existing codes could not.
Shannon's 1948 framework: the channel capacity
Before coding theory there was a puzzle. Engineers knew that repeating every symbol three times lets a receiver correct one error, but repetition is wasteful: to halve the error rate you double the transmission time. Was there a fundamental trade-off between reliability and speed? Claude Shannon's 1948 paper "A Mathematical Theory of Communication" answered no. Shannon defined the channel capacity—the maximum rate at which information can be sent with arbitrarily small error probability—and proved that for any rate below capacity, codes exist whose error probability is as small as desired345. The proof was non-constructive: it showed such codes exist by averaging over random codes, without exhibiting one. This created the field's central tension. Shannon told engineers the target; he did not tell them how to hit it. For the next five decades, coding theory was largely the search for explicit, efficiently decodable codes approaching capacity.
Shannon also introduced the vocabulary that persists: entropy as a measure of information, mutual information, and the noisy-channel coding theorem. His 1949 companion paper on secrecy systems founded cryptographic coding as a sibling field. The information-theoretic viewpoint—codes as probability distributions over messages—remained distinct from the combinatorial viewpoint—codes as finite sets with distance properties—and the two traditions have interacted productively ever since.
Hamming, Golay, and the birth of algebraic block coding
The first constructive codes came from Richard Hamming at Bell Labs, published in 1950. Hamming asked how to encode data so that a single error can be corrected with minimal redundancy. His answer: append parity-check bits that test overlapping subsets of the message bits6. A Hamming code of length 7 encodes 4 data bits into 7, with 3 check bits, and corrects any single error76. The key concept was Hamming distance—the number of positions in which two words differ—and the realisation that a code correcting t errors needs minimum distance 2t+1. Hamming's codes are linear: the sum (modulo 2) of two codewords is again a codeword, which makes encoding and decoding tractable through linear algebra17.
Marcel Golay, working independently around the same time, constructed the Golay code, a perfect code of length 23 correcting 3 errors, and a ternary version of length 11. The binary Golay code turned out to be connected to the Leech lattice and to sporadic finite groups, a hint that coding theory would keep turning up structures of independent mathematical interest.
The algebraic generalisation came from David Slepian (1956) and especially from the school around Richard Hamming and later Elwyn Berlekamp: linear block codes over finite fields, described by a generator matrix and a parity-check matrix. The Reed–Muller codes, introduced by David Muller in 1954 and given an efficient decoding algorithm by Irving Reed the same year, were among the first families with a recursive structure and a clean algebraic description. The BCH codes (Bose–Chaudhuri–Hocquenghem, 1959–60) and the Reed–Solomon codes (Irving Reed and Gustave Solomon, 1960) extended the algebraic approach to multiple-error correction89. Reed–Solomon codes, which work over a field of size at least the code length, became ubiquitous in practice—on CDs, in QR codes, in deep-space telemetry—because they correct bursts of errors efficiently.
Combinatorial bounds: how good can a code be?
Alongside construction came limitation. How many codewords can a code of length n and minimum distance d have? The Hamming bound (sphere-packing) and the Singleton bound gave upper limits; the Gilbert–Varshamov bound (1952) gave a lower limit by a greedy argument, showing that codes with certain parameters must exist. The Plotkin bound handled the regime of large distance. These bounds framed the central combinatorial question: for which parameters do codes exist, and how close can constructions come to the bounds? The perfect codes—those meeting the Hamming bound with equality—were classified: Hamming codes, the Golay codes, and trivial cases110. The classification, completed in stages through the 1970s, was a landmark of combinatorial coding theory.
The MacWilliams identities (1963), relating the weight enumerator of a code to that of its dual, gave a powerful algebraic-combinatorial tool and connected coding theory to invariant theory and to the theory of designs. The Assmus–Mattson theorem (1969) showed that codes with certain weight distributions yield combinatorial designs, a bridge between coding theory and design theory that remains active.
Convolutional codes and the Viterbi algorithm
A different architecture emerged in the 1950s and 1960s: convolutional codes, introduced by Peter Elias in 195511. Instead of encoding fixed blocks, a convolutional encoder processes a continuous stream, with each output depending on the current input and a sliding window of past inputs11. This made them natural for continuous transmission and gave them strong burst-error performance. The decoding breakthrough was Andrew Viterbi's 1967 algorithm, which finds the most likely path through a trellis—a time-indexed state diagram—in time linear in the sequence length. The Viterbi algorithm became one of the most widely deployed algorithms in engineering, used in satellite links, mobile telephony, and magnetic recording. Convolutional codes with Viterbi decoding dominated practical digital communication from the 1970s through the 1990s, and their analysis via free distance and transfer functions became a standard part of the coding curriculum.
Algebraic geometry codes: the 1980s surprise
In 1981, Valery Goppa constructed codes from algebraic curves over finite fields, using the Riemann–Roch theorem to bound their parameters. Algebraic geometry codes (also called Goppa codes) generalised Reed–Solomon codes—which correspond to the projective line—to curves of higher genus. The shock came when Tsfasman, Vlăduț, and Zink showed in 1982 that certain modular curves yield codes beating the Gilbert–Varshamov bound, something no classical construction had achieved12. This was the first proof that the GV bound is not asymptotically optimal, and it brought deep algebraic geometry into coding theory. The codes are not always practical—decoding them efficiently was a challenge—but they reshaped the field's sense of what is possible and forged lasting links between coding theory and arithmetic geometry.
Iterative decoding and the return to Shannon
By the late 1980s, the gap between practical codes and Shannon capacity remained large—several decibels in signal-to-noise ratio. The turning point came from two directions. In 1993, Claude Berrou, Alain Glavieux, and Punya Thitimajshima introduced turbo codes, which concatenate two convolutional encoders separated by an interleaver and decode them iteratively, each decoder passing soft information to the other. Turbo codes came within a fraction of a decibel of capacity, a result initially met with disbelief. Around the same time, Robert Gallager's 1962 doctoral thesis on low-density parity-check (LDPC) codes was rediscovered. Gallager had shown that sparse parity-check matrices with iterative message-passing decoding could approach capacity, but his work had been forgotten because the computation was infeasible in 1962. By the 1990s, computation had caught up, and LDPC codes proved at least as good as turbo codes and easier to analyse.
The unifying idea was iterative decoding on a graph: represent the code by a factor graph and run belief propagation, passing messages between variable nodes and check nodes1314. This connected coding theory to statistical physics (spin glasses), to artificial intelligence (Bayesian networks), and to the theory of expander codes (Sipser–Spielman, 1996), which gave the first linear-time decodable codes approaching capacity. The polar codes of Erdal Arıkan (2008) completed this arc: a construction with an explicit recursive structure and a provably capacity-achieving low-complexity decoder, the first such family for symmetric channels. Polar codes were adopted for the control channel of 5G15.
Coding for networks, storage, and quantum machines
As classical point-to-point coding matured, the field's centre of gravity shifted to new settings. Network coding, introduced by Rudolf Ahlswede, Ning Cai, Shuo-Yen Robert Li, and Raymond Yeung in 2000, showed that in a network with multiple senders and receivers, allowing intermediate nodes to mix packets linearly can achieve throughput that routing cannot. This spawned a large literature on linear network codes, random network coding, and their algebraic foundations16.
Distributed storage codes addressed a practical problem: storing data redundantly across many disks so that any k of n can reconstruct it (Reed–Solomon erasure coding) while minimising repair traffic when a disk fails. Regenerating codes (Dimakis, Godfrey, Wu, Wainwright, Ramchandran, 2007) formalised the trade-off between storage overhead and repair bandwidth, and locally repairable codes followed. These codes now underpin cloud storage systems.
Quantum error correction, anticipated by Peter Shor in 1995 and developed by Steane, Calderbank, and others, extended classical coding ideas to protect quantum states from decoherence1718. The Calderbank–Shor–Steane (CSS) codes built quantum codes from pairs of classical codes, and stabiliser codes generalised the framework1917. The surface code and topological codes became leading candidates for fault-tolerant quantum computing20. Quantum coding theory is now a field in its own right, with its own bounds, constructions, and decoding algorithms, but its combinatorial skeleton—codes as subspaces with distance—descends directly from the classical tradition.
The present: a field of many channels
Coding theory today is less a single research programme than a family of them, united by the combinatorial and algebraic study of redundancy. Classical algebraic coding—BCH, Reed–Solomon, algebraic geometry codes—remains central to storage and to the theory of designs. Capacity-approaching codes—LDPC, turbo, polar—dominate modern communication standards and continue to be refined for short blocklengths, where finite-length effects matter. Network coding and distributed storage coding have grown into substantial applied-mathematical fields with their own conferences and journals. Quantum coding theory is expanding rapidly as quantum hardware matures. Open questions persist at every scale: the exact asymptotic behaviour of code rates for general channels, the construction of capacity-achieving codes with low-complexity and low error floors, the decoding of algebraic geometry codes at practical speeds, and the design of codes for adversarial and Byzantine settings. What Shannon framed as an existence question in 1948 has become a vast constructive and combinatorial enterprise, and the field's history is the record of closing, step by step, the distance between what is possible and what can be built.
References
- Coding theory (introduction, Channel coding, Linear block codes), Wikipedia
- Error correction code, Wikipedia
- Information theory (Historical background), Wikipedia
- Noisy-channel coding theorem, Wikipedia
- Concatenated error correction code (Background), Wikipedia
- Hamming code, Wikipedia
- Linear code, Wikipedia
- BCH code, Wikipedia
- Reed–Solomon error correction, Wikipedia
- Hamming bound, Wikipedia
- Convolutional code (History, introduction), Wikipedia
- Algebraic geometry code (History), Wikipedia
- Low-density parity-check code, Wikipedia
- Belief propagation, Wikipedia
- Reed–Muller code, Wikipedia
- Linear network coding, Wikipedia
- Quantum error correction, Wikipedia
- Five-qubit error correcting code (History), Wikipedia
- CSS code, Wikipedia
- Stabilizer code, Wikipedia
The frameworks of Coding Theory
Each framework is a way of working the field has used: when it held, and the question it answers.
- 1948-Present
- 1950-Present
- 1952-Present
- 1955-1995
- 1981-Present
Algebraic geometry code
Can curves over finite fields yield better codes?
- 1993-Present
Iterative decoding and capacity-approaching codes
How close to capacity can practical codes get?
- 1995-Present
Quantum error correction
How do we protect quantum information from noise?
- 2000-Present
- 2007-Present
Distributed storage coding
How do we store data so it survives failures?
- 2008-Present
How the ideas connect
Each arrow runs from an earlier idea to the later one it shaped. The list below says what passed between them.
Algebraic block coding influenced by Shannon information theory
Shannon's 1948 paper set the goal of approaching channel capacity with explicit codes, and Hamming's 1950 construction answered it directly by giving the first efficient linear error-correcting code. The algebraic block-coding tradition that followed defined itself as the constructive response to Shannon's non-constructive existence proof.
Carried by Claude Shannon; Richard Hamming; A Mathematical Theory of Communication (1948).
Iterative decoding and capacity-approaching codes influenced by Shannon information theory
The iterative-decoding revolution was driven by the goal of closing the gap to Shannon capacity, which turbo codes and rediscovered LDPC codes brought to within a fraction of a decibel. Shannon's capacity is the explicit target against which these codes were measured.
Carried by Claude Berrou; Robert Gallager.
Polar Coding influenced by Shannon information theory
Arıkan's polar codes were explicitly designed to achieve Shannon capacity with an efficient decoder, and the polarisation phenomenon is analysed through mutual information, the central quantity of Shannon's theory. The construction is presented as a constructive solution to the capacity-achieving problem Shannon posed.
Carried by Erdal Arıkan.
Algebraic geometry code grew out of Algebraic block coding
Goppa's algebraic geometry codes generalised Reed–Solomon codes, which correspond to the projective line, to curves of higher genus using the Riemann–Roch theorem. The construction is a direct extension of the algebraic block-code framework over finite fields.
Carried by Valery Goppa; Irving Reed; Gustave Solomon.
Iterative decoding and capacity-approaching codes influenced by Convolutional code
Turbo codes concatenate two convolutional encoders separated by an interleaver and decode them iteratively, so the convolutional architecture and its trellis decoding are the direct substrate of the 1993 construction. Berrou and colleagues built turbo codes explicitly on convolutional component codes.
Carried by Claude Berrou; Alain Glavieux; Punya Thitimajshima.
Combinatorial coding theory influenced by Shannon information theory
The Gilbert–Varshamov bound of 1952 was framed as a combinatorial lower bound on the code sizes whose existence Shannon had proved probabilistically, turning his existence theorem into a counting problem about finite sets of words.
Carried by Edgar Gilbert; Rom Varshamov.
Convolutional code influenced by Shannon information theory
Convolutional codes were designed as a practical route toward the reliable transmission at rates below capacity that Shannon's theorem promised. The Viterbi algorithm's maximum-likelihood decoding is an explicit realisation of Shannon's optimal receiver for a memoryless channel.
Carried by Peter Elias; Andrew Viterbi.
Quantum error correction influenced by Shannon information theory
Quantum error correction took the classical coding framework of encoding against noise and recast it for quantum channels, with the quantum capacity and no-cloning constraints analysed in Shannon-style information-theoretic terms. The stabiliser formalism borrows the parity-check idea from classical coding.
Carried by Peter Shor; Andrew Steane.
Network coding influenced by Shannon information theory
Network coding grew out of information-theoretic analysis of multi-terminal communication, asking for the capacity of networks rather than point-to-point channels. The max-flow min-cut characterisation of network capacity is a direct extension of Shannon's channel-capacity programme.
Carried by Rudolf Ahlswede; Ning Cai; Shuo-Yen Robert Li.
Combinatorial coding theory grew out of Algebraic block coding
Combinatorial coding theory grew out of the algebraic constructions of Hamming, Golay and the Reed–Muller codes by asking how many codewords of given length and distance can exist at all. The sphere-packing and Singleton bounds were posed against the parameters of those explicit algebraic codes.
Carried by Richard Hamming; Marcel Golay.
Convolutional code influenced by Algebraic block coding
Elias's convolutional codes extended the linear-algebraic encoding machinery of block codes to a sliding-window architecture over a continuous stream. The generator-matrix formalism of linear block coding carried over directly into the convolutional setting.
Carried by Peter Elias.
Iterative decoding and capacity-approaching codes revived Algebraic block coding
Gallager's 1962 low-density parity-check codes, an algebraic block construction with sparse parity-check matrices, were rediscovered in the 1990s and became central to capacity-approaching iterative decoding. The revival made his linear block-code construction the basis of modern LDPC practice.
Carried by Robert Gallager.
Quantum error correction influenced by Algebraic block coding
The first quantum codes were built by adapting classical linear block codes and their parity-check matrices to the stabiliser formalism. Calderbank–Shor–Steane codes are constructed directly from classical self-orthogonal linear codes.
Carried by Peter Shor; Andrew Steane; Robert Calderbank.
Network coding influenced by Algebraic block coding
Linear network codes are defined by generator matrices over finite fields exactly as linear block codes are, and the algebraic framework of linear coding carried over to the network setting. Random linear network coding uses the same finite-field linear algebra.
Carried by Shuo-Yen Robert Li; Raymond Yeung; Ning Cai.
Algebraic geometry code influenced by Combinatorial coding theory
The Tsfasman–Vlăduț–Zink result was framed as a comparison with the Gilbert–Varshamov bound, the central benchmark of combinatorial coding theory. Showing that algebraic geometry codes beat that bound gave the combinatorial tradition its first asymptotic counterexample.
Carried by Michael Tsfasman; Serge Vlăduț; Dmitry Zink.
Distributed storage coding influenced by Iterative decoding and capacity-approaching codes
Distributed storage coding adapted the erasure-correcting and iterative-decoding machinery of capacity-approaching codes to data-centre storage, with regenerating codes and locally repairable codes built on the same finite-field linear-algebraic and message-passing techniques.
Carried by Alexandros Dimakis; P. Vijay Kumar.
Polar Coding influenced by Iterative decoding and capacity-approaching codes
Polar coding belongs to the capacity-approaching programme opened by turbo and LDPC codes, and Arıkan's successive-cancellation decoding was developed in dialogue with the iterative-decoding literature. Polar codes were adopted alongside LDPC codes in 5G standards.
Carried by Erdal Arıkan.
Beyond the field
Where Coding Theory's ideas came from in other fields, and what they led to there: the strongest 12 of 39 links.
Shannon information theory led to Information-theoretic security in Applied Cryptography
Information-theoretic security derives from Shannon information theory, using its entropy and equivocation measures to define perfect secrecy.
Carried by Claude Shannon.
Shannon information theory led to Network Information Theory in Information Theory
Network information theory is a direct extension of Shannon information theory, taking its entropy and capacity tools to multi-user settings.
Carried by Claude Shannon.
Shannon information theory led to Rate-Distortion Theory in Information Theory
Rate-distortion theory is a direct outgrowth of Shannon's information theory, formulated by Shannon himself as its lossy-coding extension.
Carried by Claude Shannon.
Shannon information theory led to Universal Source Coding in Information Theory
Universal source coding is a branch of Shannon information theory, extending its source-coding theorem to sources whose statistics are unknown.
Carried by Claude Shannon.
Shannon information theory influenced Finite-Blocklength Information Theory in Information Theory
Shannon's coding theorems and the asymptotic capacity notion are the direct starting point for finite-blocklength theory, which quantifies the gap from capacity at finite blocklength. The later results (normal approximation) are refinements of Shannon's asymptotic statements.
Carried by Claude Shannon; Y. Polyanskiy; S. Verdú.
Shannon information theory led to Perfect Secrecy and Information-Theoretic Cryptography in Security Theory
Shannon's 1948 mathematical theory of communication supplied the entropy and equivocation measures, and his 1949 'Communication Theory of Secrecy Systems' applied them directly to ciphers, making perfect secrecy a branch of information theory.
Carried by Claude Shannon; Communication Theory of Secrecy Systems (1949).
Shannon information theory influenced Error detection and correction in Reliability Fault Tolerance
Shannon's 1948 paper framed communication over noisy channels and proved that reliable transmission is possible below channel capacity, setting the problem that error-correcting codes were built to solve.
Carried by Claude Shannon; A Mathematical Theory of Communication (1948).
Shannon information theory led to Algebraic Coding Theory in Information Theory
Algebraic coding theory grew directly out of Shannon's 1948 coding theorems, which posed the existence of efficient codes and set the bounds that algebraic constructions like Hamming and Golay codes were built to approach.
Carried by Claude Shannon; Richard Hamming; Marcel Golay.
Shannon information theory influenced Iterative and Sparse-Graph Coding in Information Theory
Shannon's channel capacity theorem and random-coding argument are the framework's defining target: capacity-approaching codes are defined by how close they come to Shannon capacity. Iterative decoding work explicitly framed itself as approaching the Shannon limit.
Carried by Claude Shannon.
Shannon information theory influenced Error-Correcting Coding in Communication Systems
Shannon's information theory established the channel capacity and the noisy-channel coding theorem that defined the goal and limits of error-correcting coding. Hamming and others built explicit codes in response to Shannon's bounds.
Carried by Claude Shannon; Richard Hamming.
Shannon information theory influenced Quantum Shannon Theory in Information Theory
Quantum Shannon theory generalises Shannon's coding theorems to quantum channels and sources, taking the capacity questions, typicality arguments and coding setup directly from Shannon's framework. The whole subfield is framed as the quantum counterpart of Shannon's theory.
Carried by Claude Shannon; Benjamin Schumacher; Alexander Holevo.
Shannon information theory led to Information-Theoretic Cryptography in Cryptography
Information-theoretic cryptography is built directly on Shannon's mathematical theory of communication, using its entropy and channel concepts to define secrecy. Shannon himself made the transfer in his 1949 secrecy paper.
Carried by Claude Shannon; Communication Theory of Secrecy Systems (1949).

Coding Theory is a planet in Nousfarer
Its city has a tower for each of these 10 frameworks. Land, walk in, and climb one concept at a time.
Land on Coding TheoryRelated fields
Fields its ideas are linked to
- Information Theory 16 links
- Communication Systems 7 links
- Signal Processing 4 links
- Combinatorics 2 links
- Reliability Fault Tolerance 2 links
- Abstract Algebra 1 link
- Enumerative Combinatorics 1 link
- Computational Imaging 1 link
- Thermodynamics 1 link
- Applied Cryptography 1 link
- Security Theory 1 link
- Storage Systems 1 link