Source Coding Theorem

The Source Coding Theorem — also known as Shannon's First Theorem or the Noiseless Coding Theorem — establishes the fundamental limit on lossless data compression. Proven by Claude Shannon in 1948, it states that for any information source with entropy H (measured in bits per symbol), there exists a lossless coding scheme whose average code length per symbol can be made arbitrarily close to H, and no scheme can achieve an average length below H.

The theorem transforms entropy from a statistical curiosity into an operational bound. Entropy is not merely a measure of uncertainty; it is the irreducible cost of describing a source. Any compression algorithm that achieves rates near the entropy limit is, in a precise sense, optimal. The theorem's proof is non-constructive — it demonstrates existence without providing the code — which motivated decades of practical algorithm development from Huffman coding to Lempel-Ziv methods.

The theorem applies to memoryless sources and extends to sources with memory through extensions of the entropy concept, including block entropy and entropy rate. For a source with memory, the relevant quantity is the entropy rate — the limit of the entropy per symbol as the block length grows — which captures the long-range statistical dependencies that memoryless analysis misses.