= 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.
Back to article page