Coding Theory

Coding theory is the mathematics of making messages survive a hostile channel.

10 frameworks, from 1948 to today · Combinatorics · Mathematics

still a working view ended · each leads to its entry below

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

  1. Coding theory (introduction, Channel coding, Linear block codes), Wikipedia
  2. Error correction code, Wikipedia
  3. Information theory (Historical background), Wikipedia
  4. Noisy-channel coding theorem, Wikipedia
  5. Concatenated error correction code (Background), Wikipedia
  6. Hamming code, Wikipedia
  7. Linear code, Wikipedia
  8. BCH code, Wikipedia
  9. Reed–Solomon error correction, Wikipedia
  10. Hamming bound, Wikipedia
  11. Convolutional code (History, introduction), Wikipedia
  12. Algebraic geometry code (History), Wikipedia
  13. Low-density parity-check code, Wikipedia
  14. Belief propagation, Wikipedia
  15. Reed–Muller code, Wikipedia
  16. Linear network coding, Wikipedia
  17. Quantum error correction, Wikipedia
  18. Five-qubit error correcting code (History), Wikipedia
  19. CSS code, Wikipedia
  20. 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.

  1. 1948-Present

    Shannon information theory

    How fast can information be sent reliably?

    Fly to its tower in Nousfarer

  2. 1950-Present

    Algebraic block coding

    How do we build codes that correct errors?

    Fly to its tower in Nousfarer

  3. 1952-Present
  4. 1955-1995

    Convolutional code

    How do we encode a continuous stream of data?

    Fly to its tower in Nousfarer

  5. 1981-Present

    Algebraic geometry code

    Can curves over finite fields yield better codes?

    Fly to its tower in Nousfarer

  6. 1993-Present
  7. 1995-Present

    Quantum error correction

    How do we protect quantum information from noise?

    Fly to its tower in Nousfarer

  8. 2000-Present

    Network coding

    How should information flow through a network?

    Fly to its tower in Nousfarer

  9. 2007-Present

    Distributed storage coding

    How do we store data so it survives failures?

    Fly to its tower in Nousfarer

  10. 2008-Present

    Polar Coding

    Can we construct codes that provably reach capacity?

    Fly to its tower in Nousfarer

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.

Shannon information theoryAlgebraic block codingCombinatorial coding theoryConvolutional codeAlgebraic geometry codeIterative decoding and capacity-appro…Quantum error correctionNetwork codingDistributed storage codingPolar Coding

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.

A city in Nousfarer: a red-carpeted stair climbing terraces to a crowned tower on an acropolis, more towers round it, forest and snowy mountains beyond.
A city in Nousfarer, the game played in the browser.

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 Theory

Related fields

Fields its ideas are linked to

More in Combinatorics

See where Coding Theory sits on the Map of Human Knowledge