Source coding theorem

The source coding theorem is a foundational result in information theory that determines how efficiently a discrete information source can be represented. It establishes Shannon entropy as the limiting number of bits per source symbol required for compression under specified decoding conditions. Introduced by Claude Shannon in his 1948 paper A Mathematical Theory of Communication, it has closely related formulations for exact, variable-length coding and fixed-length coding with vanishing error probability. The distinction between these formulations is essential to understanding its scope. (people.math.harvard.edu)

Source model and entropy

In the basic model, a source produces symbols $X_1,X_2,\ldots$ independently with the same probability distribution $p$ on a finite alphabet $\mathcal X$. Each symbol is a random variable, and the source is called memoryless because previous symbols do not affect subsequent probabilities. Its entropy is

with $0\log_2 0=0$. Entropy is the expected value of the self-information $-\log_2p(X)$. It measures average uncertainty, rather than the meaning or usefulness of a message. For independent symbols, the joint entropy satisfies $H(X_1,\ldots,X_n)=nH(X)$. (people.math.harvard.edu)

A uniform distribution on $m$ symbols has entropy $\log_2m$. Unequal probabilities generally allow shorter average representations: frequent symbols can receive short codewords, while rare symbols receive longer ones. The theorem makes this intuition precise without requiring every individual message to become shorter. (isl.stanford.edu)

Exact variable-length coding

For lossless compression, the decoder must recover the encoded input exactly. A symbol code is uniquely decodable if every concatenation of codewords has only one interpretation. A prefix code satisfies the stronger condition that no codeword is a prefix of another; such codes can be decoded without waiting for later codewords. (ocw.mit.edu)

Let $\ell(x)$ denote the binary codeword length assigned to symbol $x$, and let

be its expected length. Every uniquely decodable binary symbol code satisfies $L\ge H(X)$, and a prefix code exists satisfying

The upper bound follows by choosing $\ell(x)=\lceil-\log_2p(x)\rceil$ for positive-probability symbols. These lengths satisfy the Kraft–McMillan inequality, which guarantees the existence of a corresponding prefix code. (ocw.mit.edu)

Encoding blocks of $n$ independent symbols gives an achievable expected block length $L_n$ satisfying

Thus, the overhead caused by integer codeword lengths can become arbitrarily small per symbol. This result concerns an average over messages: unusually improbable blocks may require much longer codewords. (web.stanford.edu)

Fixed-length coding with vanishing error

A second formulation encodes each block $X^n=(X_1,\ldots,X_n)$ into one of $M_n$ messages. Its rate is approximately $(\log_2M_n)/n$ bits per source symbol. The decoder produces an estimate $\widehat X^n$, with block error probability

For a finite-alphabet memoryless source, every rate $R>H(X)$ permits a sequence of codes with $P_e^{(n)}\to0$. Conversely, vanishing error requires an asymptotic rate at least $H(X)$. Entropy is therefore the infimum achievable rate; the theorem does not generally promise vanishing error at precisely the boundary rate. (isl.stanford.edu)

Unlike exact variable-length coding, this formulation may fail on some blocks. Its requirement is that their total probability tends to zero. Requiring fixed-length codes to distinguish every possible block instead makes the alphabet’s support size, rather than its probability-weighted entropy alone, decisive. (ocw.mit.edu)

Typical sequences and the proof

The central proof idea is the asymptotic equipartition property. For independent identically distributed symbols, the law of large numbers implies

in probability. Consequently, most probability mass lies in a typical set whose members have probabilities approximately $2^{-nH(X)}$. (theory.stanford.edu)

For a small tolerance $\varepsilon>0$, define typical blocks by

Their number is at most $2^{n(H(X)+\varepsilon)}$, so identifying a typical block requires roughly $nH(X)$ bits. Atypical blocks account for a probability tending to zero. Conversely, a code with only $2^{nR}$ messages, where $R<H(X)$, cannot distinguish enough typical blocks to recover most of the probability mass. These counting arguments explain both achievability and the compression limit. (theory.stanford.edu)

Algorithms and extensions

Huffman coding minimizes expected length among binary prefix codes for a known finite distribution. Applied to blocks, it approaches the entropy bound, although the number of possible blocks grows rapidly. Arithmetic coding provides a sequential alternative that avoids explicitly constructing an enormous block-code tree. The theorem specifies a limit, not a unique compression algorithm, and does not itself guarantee low computational complexity. (ocw.mit.edu)

For sources with memory, the relevant quantity is generally the entropy rate

For finite-alphabet stationary ergodic sources, corresponding coding results replace single-symbol entropy by this rate. Dependence between symbols can therefore provide compression opportunities unavailable to a model treating symbols independently. (people.math.harvard.edu)

Source coding should be distinguished from the noisy-channel coding theorem. Source coding removes statistical redundancy; channel coding introduces structured redundancy to protect transmission. Their limits are expressed respectively by source entropy and channel capacity. Allowing controlled reconstruction distortion leads instead to rate–distortion theory, which studies a different rate constraint from exact or asymptotically error-free recovery. (people.math.harvard.edu)

References

1. A Mathematical Theory of Communicationpeople.math.harvard.edu
2. Lecture 2: Basic Information Theoryisl.stanford.edu
3. Chapter 2: Coding for Discrete Sourcesocw.mit.edu
4. 441S16: Course Notesocw.mit.edu
5. Information and Entropyocw.mit.edu
6. Probability - Lossy Compressiontheory.stanford.edu
7. Lecture 17: Huffman Codingocw.mit.edu
8. The role of the asymptotic equipartition property in noiseless source codingcollaborate.princeton.edu