 Shannon's source coding theorem

For a finite-alphabet memoryless classical information source with information entropy $H$, every uniquely decodable code for blocks of $m$ source symbols has expected binary length at least $mH$. This follows from Kraft inequality for uniquely decodable codes and the entropy lower bound for prefix codes.

If at least two source symbols have positive probability, give each positive-probability block $w$ Shannon length $\ell (w)=\lceil -{\log }_{2}p(w)\rceil$. These lengths satisfy Kraft inequality, so a prefix code exists, and independence givesThus coding longer blocks approaches the information entropy in expected bits per source symbol. This is an average-length statement: rare blocks can have long codewords.

For a source with only one possible symbol, a one-bit codeword for each length-$m$ block gives rate $1/m\to 0=H$ when positive codeword lengths are required. The limiting theorem therefore remains true, although the strict one-block bound $\overline{\ell }<H+1$ needs the nontrivial-alphabet assumption. Countably infinite alphabets require additional care about finite information entropy and the chosen code construction.

Shannon's source coding theorem is a fundamental result in information theory, established by Claude Shannon in his groundbreaking 1948 paper "A Mathematical Theory of Communication." The theorem provides a formal framework for understanding how to optimally encode information in a way that minimizes the average length of the code while still allowing for perfect reconstruction of the original data.