Shannon coding (source code)

= Shannon coding
{c}
{wiki}

For source probabilities $p_i>0$, <Shannon coding> chooses binary lengths $\ell_i=\lceil-\log_2p_i\rceil$. They satisfy $\sum_i2^{-\ell_i}\le\sum_ip_i=1$, so the <Kraft inequality> ensures that a binary <prefix code> with these lengths exists.

Its expected length obeys $H\le\sum_ip_i\ell_i<H+1$, where $H=-\sum_ip_i\log_2p_i$ is the source <entropy>. For probabilities $(1/2,1/4,1/4)$, the words $0,10,11$ achieve the lengths $1,2,2$ exactly. The construction rounds each information content up separately; <Huffman coding> can improve the expected length by optimizing the whole code tree.<A Mathematical Theory of Communication by Claude Shannon>[Part I, discrete noiseless coding and codeword lengths]{ref}