Loading field map
Information theory is the mathematical study of the transmission, storage, and processing of information. Despite its name, it is not primarily a theory about the meaning of messages. Instead, it provides a precise, quantitative framework for measuring information, determining the fundamental limits of data compression and reliable communication, and designing systems that approach those limits. It is a foundational discipline within electrical engineering, but its concepts have permeated statistics, computer science, physics, and biology.
The field's origin lies in a practical engineering problem: how to send a message from a source (a person, a sensor, a computer) to a destination through a physical medium (a wire, the air, an optical fiber) that introduces noise, distortion, and loss. Before information theory, engineers treated this as a problem of improving signal strength or filtering out noise. The key conceptual leap was to separate the problem of representation from the problem of transmission.
The fundamental questions are:
The answers to these questions, provided by Claude Shannon in his landmark 1948 paper "A Mathematical Theory of Communication," define the field. The central insight is that information is a measure of surprise or uncertainty. A message that is certain to occur carries no information; a message that is one of many equally likely possibilities carries a great deal.
The foundational measure is entropy, denoted H(X). For a discrete random variable X with possible outcomes x₁, x₂, ..., xₙ, each with probability p(xᵢ), the entropy is:
H(X) = -Σ p(xᵢ) log₂ p(xᵢ)
Entropy is measured in bits. It represents the average number of binary questions needed to determine the value of X, or equivalently, the minimum average number of bits required to represent the outcome of X without loss. A fair coin has an entropy of 1 bit; a coin that always lands heads has an entropy of 0 bits. The entropy is maximized when all outcomes are equally likely, and it is a measure of the uncertainty associated with the random variable.
This definition extends to joint entropy H(X, Y) for pairs of variables, and conditional entropy H(X|Y), which measures the remaining uncertainty about X after Y is known. The reduction in uncertainty about X provided by knowing Y is the mutual information I(X; Y) = H(X) - H(X|Y). Mutual information is a symmetric measure of how much one random variable tells us about another, and it is the central quantity for communication: it quantifies how much information about the transmitted signal is present in the received signal.
The first major theorem, the source coding theorem (or noiseless coding theorem), states that a source with entropy H(X) can be encoded into a binary sequence with an average length arbitrarily close to H(X) bits per symbol, but no encoding scheme can do better than H(X) bits per symbol on average without losing information. This establishes entropy as the fundamental limit of lossless compression.
Practical schemes like Huffman coding and arithmetic coding achieve this limit for known probability distributions. For sources with unknown statistics, universal coding schemes (like Lempel-Ziv, used in gzip) approach the entropy of the source asymptotically as the amount of data grows. The theorem also extends to lossy compression, where some distortion is allowed. The rate-distortion function R(D) specifies the minimum number of bits per symbol needed to represent a source such that the average distortion does not exceed a given level D. This is the theoretical basis for all lossy compression formats, such as JPEG for images and MP3 for audio.
The second major theorem, the channel coding theorem (or noisy-channel coding theorem), addresses the problem of noise. A channel is defined by its input alphabet, output alphabet, and a set of conditional probabilities p(y|x) that describe how an input symbol x is transformed into an output symbol y. The channel capacity C is the maximum of the mutual information I(X; Y) over all possible input distributions p(x).
The theorem states that for any rate R < C, there exists a coding scheme (an encoder and decoder) that can transmit information at rate R with an arbitrarily small probability of error. Conversely, for any rate R > C, reliable communication is impossible; the error probability cannot be made arbitrarily small. This is a remarkable result: it says that noise does not impose a fundamental barrier to communication, only a limit on the rate at which it can be done. The capacity C is a property of the channel itself, not of any particular coding scheme.
The theorem is non-constructive; it proves the existence of good codes but does not tell you how to find them. The subsequent decades of coding theory have been devoted to finding practical codes that approach capacity. Early codes (like Hamming codes and Reed-Solomon codes) were algebraic and could correct a fixed number of errors but fell short of capacity. The field was revolutionized by the discovery of turbo codes (1993) and the rediscovery of low-density parity-check (LDPC) codes, which use iterative decoding algorithms and come remarkably close to the Shannon limit for many channels. These are now used in most modern communication systems, from satellite links to Wi-Fi.
The field is organized around two complementary problems, which are often treated as separate sub-disciplines:
A fundamental result, the separation theorem, states that for a point-to-point communication system, the optimal strategy is to first compress the source to its entropy (source coding) and then protect the compressed bits with a channel code designed for the channel (channel coding). This separation is optimal in the sense that it achieves the best possible performance. This theorem is practically important because it allows engineers to design the source coder and channel coder independently. However, the separation theorem holds only for point-to-point scenarios; in multi-user networks (e.g., broadcast channels, multiple-access channels), joint design can sometimes outperform separation.
Shannon's original theory dealt with a single source and a single destination. The field has since expanded to consider networks with multiple senders and receivers. This is the domain of network information theory. The problems are considerably more complex. For example:
A landmark result in this area is the network coding theorem, which shows that in a network where intermediate nodes can perform algebraic operations on packets (rather than just store-and-forward), the achievable throughput can exceed what is possible with traditional routing. This has had a major impact on the theory of data networks, although its practical deployment has been limited.
Information theory is not divided into rival schools in the way that, say, psychoanalysis or economics are. It is a coherent mathematical discipline. However, there are distinct research traditions that have shaped its development:
The Shannonian tradition is the core of the field. It is characterized by a probabilistic, statistical approach. Its methods are based on random coding arguments, typical sequences, and the law of large numbers. It focuses on existence proofs and fundamental limits. This tradition remains the dominant one, and its concepts (entropy, mutual information, capacity) are the standard vocabulary of the field.
The algebraic coding tradition grew out of the search for explicit, practical codes. It uses tools from abstract algebra (finite fields, polynomial rings) to construct codes with guaranteed minimum distance properties. This tradition is less concerned with the probabilistic limits and more with the explicit construction of codes that can be efficiently encoded and decoded. While Shannon's random codes are provably good, they are impractical because they require an exponentially large lookup table for decoding. Algebraic codes (like Reed-Solomon codes) provide structure that enables efficient decoding. This tradition coexists with the Shannonian tradition; modern coding theory often combines algebraic constructions with probabilistic decoding algorithms.
The algorithmic information theory tradition, initiated by Ray Solomonoff, Andrey Kolmogorov, and Gregory Chaitin in the 1960s, takes a different approach to defining information. Instead of measuring information probabilistically, it defines the information content of a single string as the length of the shortest program that can produce it (the Kolmogorov complexity). This is a more absolute notion of information that does not depend on an assumed probability distribution. It has deep connections to computability theory and has been influential in theoretical computer science, but it is not directly applicable to engineering problems because the Kolmogorov complexity is uncomputable.
The statistical inference tradition connects information theory to statistics. The concepts of entropy and mutual information are used in model selection (e.g., the Akaike information criterion and the minimum description length principle), in hypothesis testing, and in the design of experiments. This tradition views information theory as a general theory of inference and learning, not just a theory of communication.
Information theory remains an active and vibrant field. Its core results are now a century-old, but they continue to be extended and applied in new contexts. The current landscape is characterized by several trends:
The field's enduring contribution is not just a set of theorems but a way of thinking. It provides a quantitative language for discussing the fundamental limits of any system that processes or transmits information. Its central lesson—that noise can be overcome, but only at a price measured in rate—remains as relevant today as it was in 1948.