Information Theory

What Is Information Theory?

Information theory is a mathematical discipline concerned with the quantification, storage, and transmission of information. Founded by Claude Shannon in his landmark 1948 paper "A Mathematical Theory of Communication," the field establishes fundamental limits on how efficiently data can be compressed and how reliably it can be transmitted over noisy channels. Rather than specifying a particular technology, information theory provides bounds that any communication or compression system must respect, regardless of implementation.

The discipline draws on probability theory, combinatorics, and statistical mechanics. Shannon's formulation drew on earlier work by Harry Nyquist and Ralph Hartley on signal bandwidth and information capacity, and it developed in parallel with Norbert Wiener's cybernetics, a related discipline concerned with communication and control in both machines and biological systems. Information theory now underpins telecommunications, data storage, cryptography, statistical inference, and machine learning.

Entropy and Information Measures

Entropy is the central measure of information theory, quantifying the average uncertainty in a random variable. For a discrete random variable with probability distribution p(x), the Shannon entropy H(X) is defined as the expected value of the log-probability of each outcome, measuring how many bits are needed on average to describe the variable's outcomes. A uniform distribution over N symbols has maximum entropy of log₂N bits, while a deterministic variable has entropy zero. Related measures include conditional entropy, which captures remaining uncertainty about one variable given knowledge of another, and mutual information, which quantifies the statistical dependence between two variables. These measures are developed in detail in lecture notes from Stanford's EE 376A information theory course.

Channel Capacity and Coding

Shannon's channel coding theorem establishes that every noisy communication channel has a capacity, measured in bits per second, below which data can be transmitted with arbitrarily small error probability. For the additive white Gaussian noise (AWGN) channel, capacity is given by the Shannon-Hartley formula C = W log₂(1 + S/N), where W is the channel bandwidth, S is the signal power, and N is the noise power. This result, published in Shannon's 1948 paper now archived at Harvard, demonstrated that reliable communication over a noisy channel is always possible below capacity, while above capacity errors become unavoidable. Achieving capacity in practice requires channel codes such as turbo codes, low-density parity-check (LDPC) codes, and polar codes, which approach the theoretical limit with manageable complexity.

Source Coding and Data Compression

Source coding addresses the efficient representation of information, removing redundancy to reduce the number of bits required for storage or transmission. The source coding theorem, also due to Shannon, states that a source with entropy H can be encoded at a rate arbitrarily close to H bits per symbol, but no lower. Huffman coding, arithmetic coding, and Lempel-Ziv algorithms are practical realizations of this principle, assigning shorter codes to more probable symbols or patterns. The tension between source coding (compression) and channel coding (error correction) is a central theme in information theory: a well-compressed source that has had its redundancy removed is also more fragile when sent over a noisy channel, requiring explicit error-correction coding to be added back. The IEEE Transactions on Information Theory is the primary journal for advances in this field, covering both fundamental theory and applications.

Applications

Information theory has applications in a wide range of disciplines, including: