Lecture 16: Data Compression and Shannon’s Noiseless Coding Theorem

Quick Overview

Shannon's noiseless coding theorem establishes that the entropy H of a first-order source provides the absolute lower bound for the average length of any valid noiseless coding scheme, stating that the expected length is at least H times n minus little o of n, and that this bound is achievable up to the same lower-order term.

Key Points: Claude Shannon founded the field of information theory in 1948 in Building 2, laying the mathematical foundation for data compression. A first-order source is defined by an alphabet A (k symbols a1...ak) and a probability distribution p on A, operating like a k-sided unfair die generating IID samples. A valid coding function phi maps length n messages to variable-length 0,1 strings such that different messages map to different outputs, aiming to map frequent messages to shorter strings. The binary entropy function for a distribution p is defined as $H = -\sum{i=1}^{k} pi \log pi$ (with log base 2), which quantifies the minimum per-symbol length achievable. Shannon's theorem states the expected length $L$ for any coding function $\phi$ is $L \ge Hn - o(n)$, and conversely, there exists a $\phi$ such that $L \le Hn + o(n)$. The uniform distribution ($pi = 1/k$) maximizes the entropy, resulting in an entropy of $\log k$, corresponding to the naive encoding where no symbol is more frequent than others. The proof for the lower bound relies on analyzing $\epsilon$-typical sequences, showing that the expected length for these highly probable sequences is bounded by the entropy function using Stirling's approximation on the multinomial coefficient.

Context: The lecture introduces data compression by motivating the need for efficient communication using historical examples like telegram codebooks used to save money on costly messages, such as 'NBET' meaning 'captain is insane.' The core focus transitions to establishing the rigorous mathematical foundation for optimal data compression, centered around Claude Shannon's work from 1948, which defines a data source as a first-order source characterized by an alphabet and associated probabilities, similar to rolling a k-sided unfair die.