 Entropy lower bound for prefix codes

For a finite source alphabet with probabilities $p_i>0$ and binary prefix code lengths ${\ell }_i$, the expected length satisfiesTo see this, let $K={\sum }_i{2}^{-{\ell }_i}\le 1$ by Kraft inequality and put $q_i=2^{-{\ell }_i}/K$. Direct calculation givesusing nonnegativity of relative entropy. Thus the information entropy measures the unavoidable average description length, rather than the length of every individual message.

If at least two symbols have positive probability, the Shannon lengths ${\ell }_i=\lceil -{\log }_2{p}_i\rceil$ are positive, satisfy Kraft inequality, and obey $H(p)\le \overline{\ell }<H(p)+1$. For a one-symbol source, $H=0$; if codewords must have positive length, a one-bit codeword has expected length $1$, so the strict upper bound requires that separate convention or a nontrivial alphabet.