= 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 satisfies
$$
\overline\ell=\sum_i p_i\ell_i\ge H(p)=-\sum_i p_i\log_2p_i.
$$
To see this, let $K=\sum_i2^{-\ell_i}\le1$ by <Kraft inequality> and put $q_i=2^{-\ell_i}/K$. Direct calculation gives
$$
\overline\ell-H(p)=D(p\Vert q)-\log_2 K\ge0,
$$
using 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_2p_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.
Back to article page