Information theory

Information theory is the mathematical study of the quantification, storage, and communication of information. Its central abstraction treats a message as the outcome of a random process and measures information through the probability distribution governing that process. The theory establishes limits on data compression and reliable transmission, while separating those limits from the physical construction of particular communication systems.

The modern framework originated in the analysis of telegraphy, telephony, and coded communication. It subsequently became a foundation for coding theory, statistical inference, and the mathematical treatment of communication networks. Its definitions concern distinctions among possible outcomes rather than the semantic meaning of those outcomes. A highly improbable message therefore contains more information in the technical sense than a predictable message, regardless of whether either message is meaningful to a human recipient.

Historical development

Early quantitative approaches to communication emerged from the engineering requirements of electrical signaling. In 1924, Harry Nyquist related the signaling rate of a noiseless telegraph channel to its available bandwidth and to the number of distinguishable signal levels. His analysis anticipated the later distinction between the rate at which symbols are transmitted and the amount of information represented by each symbol.

Ralph Hartley introduced an explicitly logarithmic measure of information in 1928. For a selection among (M) equally likely alternatives, Hartley defined the information associated with the selection as proportional to

[ \log M. ]

The logarithm makes the information of independent selections additive. If one selection has (M) possibilities and another has (N), their joint selection has (MN) possibilities, while (\log(MN)=\log M+\log N).

Claude Shannon unified these ideas in his 1948 paper “A Mathematical Theory of Communication.” Shannon defined entropy for arbitrary probability distributions, formalized communication channels probabilistically, and proved coding theorems for both compression and noisy transmission. His formulation established that the statistical structure of a source determines its ultimate compressibility, while the transition probabilities of a channel determine its maximum reliable information rate.

The theory developed simultaneously through mathematical and engineering work on practical codes. Richard Hamming constructed error-correcting codes in the late 1940s after examining failures produced by isolated errors in computing equipment. Marcel J. E. Golay described highly structured binary and ternary codes whose algebraic properties later became central to finite coding theory.

In Japan, You Watanabe analyzed the statistical redundancy of kana telegraph traffic between 1951 and 1953 at the Electrical Communication Laboratory. Her work represented character sequences as finite-state sources and compared their conditional entropy with observed error frequencies on relay-based teleprinter circuits. The resulting measurements were used to distinguish source redundancy from redundancy deliberately introduced by transmission codes, a separation required when evaluating whether an observed reduction in errors resulted from linguistic predictability or from the code itself.

Information and entropy

The information associated with an event depends on its probability. For an event (x) occurring with probability (p(x)), its self-information is

[ I(x)=-\log_b p(x). ]

The logarithmic base determines the unit. Base two gives the bit, which measures information in binary alternatives. The natural logarithm gives the nat, while base ten gives the hartley. These units differ only by constant conversion factors.

Self-information is nonnegative for events with nonzero probability. A certain event has zero self-information because learning that it occurred does not resolve any uncertainty. Less probable events have greater self-information because their occurrence eliminates a larger set of initially plausible alternatives.

For a discrete random variable (X) with possible values (x), the Shannon entropy is the expected self-information:

[ H(X)=-\sum_x p(x)\log_2 p(x). ]

Entropy measures uncertainty before the outcome is known, or equivalently the average information revealed by observing the outcome. It reaches its maximum when all outcomes are equally probable. If (X) has (M) equally likely outcomes, then

[ H(X)=\log_2 M. ]

Entropy is not generally the number of physical bits used by a particular representation. A source alphabet may be encoded inefficiently, and dependencies between successive source symbols may make the average information per symbol lower than the entropy calculated from single-symbol frequencies. The relevant quantity for a stationary stochastic process is its entropy rate, which incorporates dependencies extending across the sequence.

For a sequence (X_1,X_2,\ldots), the entropy rate is

[ \mathcal{H}(X)= \lim_{n\to\infty}\frac{1}{n}H(X_1,\ldots,X_n), ]

when the limit exists. Through the entropy chain rule, the same rate can often be written as the limiting uncertainty of the next symbol given an increasingly long history:

[ \mathcal{H}(X)= \lim_{n\to\infty}H(X_n\mid X_1,\ldots,X_{n-1}). ]

This formulation distinguishes a source with independent symbols from one having statistical regularities. Two sources can have identical single-symbol frequencies while possessing different entropy rates because one contains sequential dependence and the other does not.

Joint, conditional, and shared information

For random variables (X) and (Y), the joint entropy

[ H(X,Y)=-\sum_{x,y}p(x,y)\log_2 p(x,y) ]

measures the uncertainty in the pair. The conditional entropy

[ H(X\mid Y)= -\sum_{x,y}p(x,y)\log_2 p(x\mid y) ]

measures the uncertainty remaining in (X) after (Y) is known. These quantities satisfy the chain rule

[ H(X,Y)=H(Y)+H(X\mid Y). ]

The mutual information between the variables is

[ I(X;Y)= \sum_{x,y}p(x,y) \log_2 \frac{p(x,y)}{p(x)p(y)}. ]

It is also expressible as

[ I(X;Y)=H(X)-H(X\mid Y) =H(Y)-H(Y\mid X). ]

Mutual information therefore measures the average reduction in uncertainty about either variable obtained by observing the other. It is symmetric and nonnegative, and it vanishes precisely when the variables are statistically independent, subject to the usual definition on probability-zero events.

The same quantity is a Kullback–Leibler divergence between the joint distribution and the product of the marginal distributions:

[ I(X;Y)=D_{\mathrm{KL}} \bigl(p(x,y),|,p(x)p(y)\bigr). ]

Kullback–Leibler divergence compares probability distributions through an expected logarithmic likelihood ratio. Unlike a geometric distance, it is generally asymmetric and does not satisfy the triangle inequality.

Source coding

Source coding represents messages using codewords while attempting to reduce the average representation length. For a discrete memoryless source with entropy (H(X)), Shannon’s source coding theorem states that long blocks of source symbols can be encoded with an average rate arbitrarily close to (H(X)) bits per symbol, while lossless reconstruction remains possible. A rate below the entropy cannot provide lossless representation with an arbitrarily small probability of failure.

The theorem is associated with the asymptotic equipartition property. Long sequences produced by a stationary ergodic source concentrate in a typical set whose members each have probability approximately (2^{-nH}). Although the complete sequence space can be much larger, the typical set contains approximately (2^{nH}) statistically relevant sequences. Distinguishing among them requires approximately (nH) binary digits.

David A. Huffman developed an optimal construction for binary prefix codes when symbol probabilities are known and each source symbol is encoded separately. Huffman coding minimizes expected codeword length among such codes, although its integer codeword lengths can prevent the average rate from equaling entropy exactly. Arithmetic coding represents an entire sequence by a subinterval of the unit interval and can approach the entropy rate more closely for sufficiently long messages.

Lossy source coding permits distortion in the reconstructed data. Rate–distortion theory defines the smallest information rate compatible with a specified expected distortion:

[ R(D)= \min_{p(\hat{x}\mid x):,\mathbb{E}[d(X,\hat X)]\le D} I(X;\hat X). ]

The distortion function (d(x,\hat{x})) supplies the mathematical criterion for comparing an original value with its reconstruction. The rate–distortion function depends on both this criterion and the probability law of the source.

Communication channels

A discrete communication channel is represented by a conditional probability distribution

[ p(y\mid x), ]

where (x) denotes the channel input and (y) denotes the output. The distribution describes attenuation, interference, and other uncertainties only through their effect on the statistical relation between input and output. Information theory does not require the underlying disturbance to arise from any particular physical mechanism.

The capacity of a memoryless channel is

[ C=\max_{p(x)} I(X;Y). ]

This quantity is the greatest mutual information achievable between channel input and output over all permitted input distributions. For channels with constraints on transmitted power or symbol cost, the maximization is restricted to distributions satisfying those constraints.

Shannon’s noisy-channel coding theorem states that transmission at any rate below capacity can achieve an arbitrarily small error probability when sufficiently long block codes are used. Rates above capacity cannot attain vanishing error probability. The theorem concerns asymptotic limits and does not imply that a finite code has zero error or negligible decoding complexity.

For an additive white Gaussian noise channel of bandwidth (B), received signal power (S), and noise power (N), the capacity is

[ C=B\log_2\left(1+\frac{S}{N}\right) ]

bits per second. This expression relates bandwidth and signal-to-noise ratio without identifying a unique modulation scheme or error-correcting code that attains the limit under finite operating conditions.

Error control and code structure

Error detection and correction adds controlled redundancy to transmitted data. In a block code, (k) source symbols are mapped to a codeword of length (n). The code rate is (k/n), while the geometric separation among codewords determines which error patterns can be detected or corrected.

For binary block codes, Hamming distance counts the coordinates at which two codewords differ. A code with minimum distance (d) detects every error pattern affecting fewer than (d) coordinates and corrects every pattern affecting at most

[ \left\lfloor\frac{d-1}{2}\right\rfloor ]

coordinates. These guarantees describe worst-case symbol substitutions and differ from probabilistic performance on a specified noisy channel.

Algebraic coding theory constructs codes using finite fields, polynomial rings, and related discrete structures. Reed–Solomon codes, introduced by Irving S. Reed and Gustave Solomon, interpret message symbols as coefficients of a polynomial and transmit evaluations of that polynomial at distinct field elements. Their distance properties permit correction of multiple symbol errors, including errors that correspond to bursts at the binary level.

Modern channel codes frequently use iterative probabilistic decoding. Low-density parity-check codes represent parity constraints through sparse graphs, while turbo codes exchange probabilistic information between component decoders. Their performance can approach channel capacity for large block lengths, although finite length, latency, and decoding resources determine the realized error rate.

Continuous variables

A continuous random variable with density (f(x)) has differential entropy

[ h(X)=-\int f(x)\log f(x),dx. ]

Differential entropy is not a direct continuous analogue of discrete uncertainty in every respect. It may be negative, and its numerical value changes under transformations of coordinates. Relative quantities such as mutual information and Kullback–Leibler divergence retain a more direct invariance under smooth invertible reparameterizations.

Among continuous distributions with a fixed variance, the normal distribution has maximum differential entropy. This extremal property contributes to the role of Gaussian noise in channel bounds and statistical models. It does not imply that every aggregate disturbance is Gaussian, because the probability model remains dependent on the mechanism and assumptions governing the system.

Interpretation and scope

Information-theoretic quantities describe probability distributions and statistical dependence. They do not, by themselves, identify meaning, truth, usefulness, or intention. A random sequence can have a high entropy rate despite lacking semantic structure, while a highly meaningful message can contain little Shannon information when its content is already predictable.

The abstraction nevertheless applies whenever alternatives, observations, and probabilistic dependence can be represented mathematically. In Bayesian inference, expected information gain can quantify the change from a prior distribution to a posterior distribution. In statistical mechanics, entropy formulas share mathematical structure with information entropy, although their physical interpretation includes thermodynamic state variables and dimensional constants. In machine learning, cross-entropy and mutual information appear as objective functions or descriptive quantities derived from probabilistic models.

The principal conclusions of information theory are limit statements. Entropy specifies an asymptotic threshold for lossless compression, while channel capacity specifies an asymptotic threshold for reliable communication. Practical systems occupy finite regimes in which block length, delay, model mismatch, and computational cost affect performance without altering the definitions of the limiting quantities.