Can a file of data be compressed indefinitely? How many bits are fundamentally required to represent a book, a stream of telemetry, or a DNA sequence without losing a single character? Before Claude Shannon, engineers had no theoretical benchmark against which to judge data compression algorithms. In his 1948 masterpiece, Shannon proved the Source Coding Theorem (also known as the Noiseless Coding Theorem), establishing that the Shannon entropy $H(X)$ of an information source represents the absolute, impenetrable physical barrier for lossless data compression. Any code operating below $H(X)$ suffers an error probability approaching $100%$, while optimal prefix codes can approach $H(X)$ with arbitrary perfection.
1. The Asymptotic Equipartition Property (AEP) & Typical Sets
The mathematical engine powering the Source Coding Theorem is the Asymptotic Equipartition Property (AEP)—the information-theoretic manifestation of the Weak Law of Large Numbers.
Let $X_1, X_2, dots, X_n$ be an independent and identically distributed (i.i.d.) sequence drawn from a discrete source with distribution $p(x)$. The joint probability of an $n$-sequence $x^n = (x_1, dots, x_n)$ is $p(x^n) = prod_{i=1}^n p(x_i)$. Taking the normalized negative logarithm:
[
-frac{1}{n} log_2 p(X_1, X_2, dots, X_n) = -frac{1}{n} sum_{i=1}^n log_2 p(X_i)
]
Because the terms $-log_2 p(X_i)$ are i.i.d. random variables with expected value $mathbb{E}[-log_2 p(X)] = H(X)$, by the Weak Law of Large Numbers:
[
-frac{1}{n} log_2 p(X_1, dots, X_n) xrightarrow{P} H(X) quad text{as } n to infty
]
This implies that for any $epsilon > 0$, nearly all probability is concentrated in a tiny fraction of sequences called the Typical Set $A_epsilon^{(n)}$:
[
A_epsilon^{(n)} = left{ x^n in mathcal{X}^n : 2^{-n(H(X) + epsilon)} le p(x^n) le 2^{-n(H(X) – epsilon)} right}
]
The Three Fundamental AEP Theorems:
- For $n$ sufficiently large, the total probability of observing a typical sequence approaches unity:
[
mathbb{P}(X^n in A_epsilon^{(n)}) > 1 – epsilon
] - Every typical sequence is approximately equiprobable, with probability $approx 2^{-n H(X)}$.
- The total number of typical sequences is bounded by:
[
(1 – epsilon) 2^{n(H(X) – epsilon)} le |A_epsilon^{(n)}| le 2^{n(H(X) + epsilon)}
]
Out of the vastly enormous space of $2^n$ possible binary strings, nature chooses almost exclusively from a minuscule subset of size $2^{n H(X)}$. Therefore, to encode these sequences losslessly, we need only index the members of $A_epsilon^{(n)}$, requiring precisely $log_2 |A_epsilon^{(n)}| approx n H(X)$ bits!
2. Prefix Codes and The Kraft-McMillan Inequality
In practical transmission, codewords must be uniquely decodable without requiring special delimiter characters. A prefix code (or instantaneous code) is a code in which no codeword is a prefix of any other valid codeword.
In 1949, Leon Kraft proved the definitive algebraic condition governing the existence of prefix codes over an alphabet of radix $D$ (where $D = 2$ for binary):
[
sum_{i=1}^m D^{-l_i} le 1
]
where $l_1, l_2, dots, l_m$ are the lengths of the individual codewords. Conversely, given any set of lengths satisfying this inequality, there exists a prefix code with those exact lengths.
3. Shannon’s Source Coding Theorem
Using the Kraft inequality, we formulate the optimization problem: minimize the average codeword length $L = sum_{i=1}^m p_i l_i$ subject to $sum D^{-l_i} le 1$. Relaxing the integer constraint on $l_i$ via Lagrange multipliers yields the optimal continuous lengths:
[
l_i^* = -log_D p_i
]
Substituting $l_i^*$ into the average length yields:
[
L^* = sum_{i=1}^m p_i (-log_2 p_i) = H(X)
]
Because physical codewords must have integer lengths, rounding up to $l_i = lceil -log_2 p_i rceil$ guarantees satisfaction of Kraft’s inequality, yielding the bounded theorem:
[
H(X) le L < H(X) + 1 quad text{bits/symbol}
]
By grouping symbols into blocks of length $n$, the per-symbol average length satisfies:
[
H(X) le frac{L_n}{n} < H(X) + frac{1}{n} implies lim_{n to infty} frac{L_n}{n} = H(X)
]
Shannon’s Fundamental Conclusion: The entropy $H(X)$ is the absolute lower limit on lossless data compression. No algorithm can compress data below this bound without irrevocable loss of information.
4. Algorithmic Realization: Huffman vs Arithmetic Coding
In 1952, MIT graduate student David Huffman published the iconic greedy bottom-up algorithm for constructing optimal prefix codes by iteratively combining the two least probable symbols into a binary tree. While Huffman coding achieves optimality for individual symbols ($L 0.5$ because it cannot assign fractional bits.
Modern high-performance compression standards (such as JPEG, CABAC in H.264/H.265 video, and Zstandard) employ Arithmetic Coding and Asymmetric Numeral Systems (ANS), which represent an entire message stream as a single fractional interval $[a, b) subset [0, 1)$, achieving near-exact compliance with the Shannon bound at fractional bit rates.
