View source for 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|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|Huffman coding]] to [[Lempel-Ziv-Welch|Lempel-Ziv methods]].

The theorem applies to memoryless sources and extends to sources with memory through extensions of the entropy concept, including [[Block Entropy|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.

[[Category:Information Theory]]
[[Category:Mathematics]]