Shannon's source coding theorem (source code)

= Shannon's source coding theorem
{c}
{wiki}

= Shannon source coding theorem
{c}
{synonym}

= Shannon noiseless coding theorem
{c}
{synonym}

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_2p(w)\rceil$. These lengths satisfy <Kraft inequality>, so a <prefix code> exists, and independence gives
$$
H\le\frac{\mathbb E\ell}{m}<H+\frac1m.
$$
Thus 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\to0=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.