Information Theory

Information theory is the mathematical study of information: how much of it a message carries, how much a noisy channel can deliver, and how far a message can be compressed without losing what matters.

9 frameworks, from 1948 to today · Electrical Engineering · Engineering

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

Overview

Information theory is the mathematical study of information: how much of it a message carries, how much a noisy channel can deliver, and how far a message can be compressed without losing what matters1. Its central insight is that information is not a vague quality but a measurable quantity, and that measurement sets hard limits on what any communication system can do12. Those limits are what make the field an engineering discipline as much as a mathematical one: they tell designers what is possible before a single circuit is built. The history below follows the field from its founding in the 1940s through the coding revolutions that turned its theorems into working technology.

Shannon and the Birth of a Science of Communication

Before the 1940s, communication engineering was a craft of signal-to-noise ratios and bandwidth budgets. Engineers knew that a stronger signal or a wider channel helped, but had no general theory of how much information a channel could carry3. Nor was there a rigorous notion of what "information" in a message even was. Norbert Wiener's work on cybernetics in the 1940s touched related questions, and earlier work by Harry Nyquist and Ralph Hartley at Bell Labs had sketched capacity ideas, but the field lacked a unifying framework.

Claude Shannon supplied it in "A Mathematical Theory of Communication," published in the Bell System Technical Journal in 194814. Shannon's move was to treat a message source as a random process and to define its entropy—a measure, in bits, of the average uncertainty of its output21. A source that emits a fair coin flip has one bit of entropy per symbol; a source that almost always emits the same symbol has almost none1. Entropy gave the field its first precise answer to "how much information is in this?"

Shannon then proved two theorems that became the field's twin pillars1. The source coding theorem says a source can be compressed to its entropy and no further: the entropy is the irreducible description length25. The channel coding theorem says that every noisy channel has a capacity—a maximum rate, in bits per channel use, at which information can be sent with arbitrarily small error probability, provided the encoder is allowed to use long enough blocks167. Below capacity, reliable communication is possible; above it, errors cannot be driven to zero1. This was startling: noise did not merely degrade transmission, it set a threshold, and below that threshold noise could be defeated entirely.

Shannon's 1948 paper also introduced the noisy-channel coding theorem's companion ideas—joint source-channel separation, the rate-distortion function for lossy compression, and the notion of a channel's capacity as a supremum over input distributions. The paper was dense and its proofs non-constructive: it showed that good codes exist without saying how to build them1. That gap defined the next half-century of research.

Rate-Distortion and the Theory of Lossy Compression

Shannon's 1948 paper already contained the seed of lossy compression: if a source need not be reproduced exactly, how few bits suffice? The answer is the rate-distortion function R(D), the minimum rate at which a source can be encoded so that the average distortion stays below D. Shannon developed this in a 1959 paper, "Coding Theorems for a Discrete Source with a Fidelity Criterion," building on earlier joint work with his colleague Warren Weaver's framing of communication levels. The function formalized a trade-off every engineer recognizes: you can have fewer bits or better fidelity, and the curve tells you exactly where the frontier lies.

Rate-distortion theory mattered because it separated the question of what to send from how to send it. It also made clear that lossy compression is not a failure of exactness but a deliberate, quantifiable choice. The theory's practical influence grew slowly, as it required models of source statistics and distortion measures that were hard to specify for real signals like speech and images. Its descendants—transform coding, perceptual distortion measures, and the rate-distortion analyses behind modern video codecs—became central to digital media.

Algebraic Coding Theory: Building Codes That Work

Shannon proved good codes exist; the engineering problem was to construct them1. The first answers came from algebra. Richard Hamming, working at Bell Labs, published his error-correcting codes in 1950: by adding parity bits in a structured pattern, a receiver could detect and correct single-bit errors. Hamming codes were simple and efficient for their purpose, and they established the template of adding redundancy in a designed pattern rather than merely repeating data8.

The 1950s and 1960s brought a wave of algebraic constructions. Reed–Solomon codes, introduced by Irving Reed and Gustave Solomon in 1960, worked over finite fields and could correct bursts of errors; they later became ubiquitous in storage media, QR codes, and deep-space communication. BCH codes, developed independently by Raj Chandra Bose and D. K. Ray-Chaudhuri and by Alexis Hocquenghem in the late 1950s, generalized Hamming's idea to multiple-error correction. Convolutional codes, described by Peter Elias in 1955, encoded a continuous stream rather than fixed blocks and were decoded by the Viterbi algorithm, published by Andrew Viterbi in 1967, which made them practical for satellite and cellular links.

These codes were powerful but, for decades, fell well short of Shannon capacity on noisy channels1. The gap was a standing embarrassment: theory promised reliable communication near capacity, but practical codes needed far more redundancy. Algebraic coding theory also developed its own deep questions—bounds on code size, decoding complexity, and the structure of codes over finite fields—that became a mathematical field in its own right.

Network Information Theory: Many Senders, Many Receivers

Shannon's theory addressed a single source and a single channel1. Real systems involve networks: multiple users sharing a medium, relays, interference, and feedback. Network information theory grew from the 1960s onward to ask what the fundamental limits are when many parties communicate at once. Key results include the multiple-access channel (several senders to one receiver), the broadcast channel (one sender to several receivers), and the relay channel1910. The field's landmark synthesis is Thomas Cover and Joy Thomas's textbook Elements of Information Theory (1991), which organized these results for a generation of students.

Network information theory is famously harder than the point-to-point case: many problems remain open or are solved only for special cases. Its practical importance grew with wireless networks, where interference and cooperation among users are the central design constraints. The theory's capacity regions—the sets of simultaneously achievable rates—give network designers targets and impossibility results, even when the exact regions are unknown.

Universal Source Coding and the Minimum Description Length Principle

Shannon's source coding theorem assumed the source statistics were known. In practice they rarely are. Universal source coding asks how to compress data when the source model is unknown, learning it from the data itself. The Lempel–Ziv algorithms, published by Abraham Lempel and Jacob Ziv in 1977 and 1978, achieved this by building a dictionary of repeated substrings on the fly; they became the basis of the GIF, ZIP, and PNG formats and remain among the most widely used compression methods ever devised.

A parallel development came from statistics and machine learning. The minimum description length (MDL) principle, developed by Jorma Rissanen from the late 1970s, reframed statistical model selection as a compression problem: the best model is the one that yields the shortest description of the data plus the model itself. MDL connected information theory to inductive inference and influenced later work on Kolmogorov complexity and Bayesian model selection. Universal coding and MDL together made clear that compression and learning are two views of the same problem—finding regularity in data.

Iterative and Sparse-Graph Coding: Approaching Capacity

For decades after Shannon, the capacity gap persisted1. The turning point came from codes defined on graphs. Low-density parity-check (LDPC) codes, invented by Robert Gallager in his 1960 MIT doctoral thesis, used sparse parity-check matrices and iterative decoding; they were largely forgotten for thirty years because the decoding was computationally daunting. Turbo codes, introduced by Claude Berrou, Alain Glavieux, and Punya Thitimajshima in 1993, combined two convolutional codes with an interleaver and iterative decoding, and came within a fraction of a decibel of Shannon capacity—a result that stunned the coding community.

Turbo codes revived interest in LDPC codes, which were rediscovered in the late 1990s and shown to perform comparably or better11. The unifying idea was iterative decoding: rather than solving the decoding problem exactly, pass probabilistic messages back and forth between constraints until the estimate converges1112. This approach, formalized as belief propagation on factor graphs, connected coding to statistical physics and to graphical models in machine learning. LDPC and turbo codes now underpin Wi-Fi, 5G, and deep-space links, and the capacity gap that had stood for fifty years was largely closed.

Quantum Shannon Theory

In the 1990s, information theory extended to quantum systems. Quantum Shannon theory asks what happens to Shannon's limits when the channel carries quantum states rather than classical bits13. Key results include the no-cloning theorem (an unknown quantum state cannot be copied), quantum teleportation (using entanglement and classical bits to transmit a quantum state), and quantum channel capacities that can exceed their classical counterparts. The field, developed by researchers including Charles Bennett, Peter Shor, and many others, underlies quantum cryptography and quantum computing's communication protocols. It remains an active frontier, with many capacity questions unresolved.

Finite-Blocklength Information Theory

Shannon's coding theorem is asymptotic: it promises arbitrarily small error only as block length grows without bound5. Real systems have short blocks—a packet, a control message, a sensor reading. Finite-blocklength information theory, developed notably by Yury Polyanskiy, H. Vincent Poor, and Sergio Verdú in a 2010 paper, characterizes the best achievable rate and error probability for finite block lengths, introducing the normal approximation that adds a correction term to capacity depending on block length and error tolerance. This work matters for ultra-reliable low-latency communication in 5G and for industrial control, where waiting for long blocks is not an option.

The Field Today

Information theory today is both a mature mathematical discipline and a live engineering toolkit1. Its core—entropy, capacity, rate-distortion—remains the language in which communication limits are stated114. Its descendants are everywhere: LDPC and polar codes in 5G, rate-distortion analysis in video compression, MDL and universal coding in machine learning, network information theory in wireless design, and quantum Shannon theory in the emerging quantum internet. Open questions persist: exact capacity regions for general networks, finite-blocklength limits for multi-user systems, the information-theoretic foundations of learning and privacy, and the quantum capacities of general channels. The field's founding bet—that information can be measured, and that measurement constrains what any system can do—has held up for more than seventy years and shows no sign of weakening1.

References

  1. Information theory (introduction, Quantities of information, Historical background, The classic work, Entropy of an information source, Overview, Channel capacity, Coding theory), Wikipedia
  2. Entropy (information theory), Wikipedia
  3. Shannon–Hartley theorem (Historical development), Wikipedia
  4. A Mathematical Theory of Communication, Wikipedia
  5. Shannon's source coding theorem, Wikipedia
  6. Noisy-channel coding theorem, Wikipedia
  7. Channel capacity, Wikipedia
  8. Hamming code, Wikipedia
  9. Interference channel, Wikipedia
  10. Relay channel, Wikipedia
  11. Low-density parity-check code (introduction, History), Wikipedia
  12. Belief propagation, Wikipedia
  13. Quantum information science, Wikipedia
  14. Rate–distortion theory, Wikipedia

The frameworks of Information Theory

Each framework is a way of working the field has used: when it held, and the question it answers.

  1. 1948-Present

    Shannon Theory of Communication

    How much information can a channel carry?

    Fly to its tower in Nousfarer

  2. 1950-Present

    Algebraic Coding Theory

    How can errors be corrected efficiently?

    Fly to its tower in Nousfarer

  3. 1959-Present

    Rate-Distortion Theory

    How few bits can represent data within a distortion limit?

    Fly to its tower in Nousfarer

  4. 1961-Present

    Network Information Theory

    What are the limits when many users communicate?

    Fly to its tower in Nousfarer

  5. 1977-Present

    Universal Source Coding

    How can data be compressed without knowing its statistics?

    Fly to its tower in Nousfarer

  6. 1978-Present
  7. 1993-Present

    Iterative and Sparse-Graph Coding

    How can codes approach the capacity limit?

    Fly to its tower in Nousfarer

  8. 1993-Present

    Quantum Shannon Theory

    What are the limits of transmitting quantum information?

    Fly to its tower in Nousfarer

  9. 2010-Present

    Finite-Blocklength Information Theory

    What are the limits for finite block lengths?

    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 Theory of CommunicationAlgebraic Coding TheoryRate-Distortion TheoryNetwork Information TheoryUniversal Source CodingMinimum Description LengthIterative and Sparse-Graph CodingQuantum Shannon TheoryFinite-Blocklength Information Theory

Beyond the field

Where Information Theory's ideas came from in other fields, and what they led to there: the strongest 12 of 54 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.

Information Theory is a planet in Nousfarer

Its city has a tower for each of these 9 frameworks. Land, walk in, and climb one concept at a time.

Land on Information Theory

Related fields

Fields its ideas are linked to

More in Electrical Engineering

See where Information Theory sits on the Map of Human Knowledge