Entropy lower and Shannon upper bounds for finite prefix codes

Put $r(x)=2^{-\mathrm{\ell }(x)}>0$ on the positive support. By [F3], ${\sum }_{x}r(x)\le 1$, so [F4] gives $0\le {\sum }_{x}p(x){\log }_2(p(x)\mathrm{/}r(x))=-H(p)+{\sum }_{x}p(x)\mathrm{\ell }(x)$. Thus every such code has expected length at least $H(p)$. If the support has one point, one known block can be described by length zero and both entropy and optimal expected length are zero; no unknown message-count decoding is claimed.

Assume now that the support has at least two points. Then every positive $p(x)<1$, so $\mathrm{\ell }(x)=\lceil -{\log }_{2}p(x)\rceil$ is a positive integer. It satisfies ${\sum }_x{2}^{-\mathrm{\ell }(x)}\le {\sum }_{x}p(x)=1$, so the finite binary Kraft criterion gives a prefix code. Also $\mathrm{\ell }(x)<-{\log }_{2}p(x)+1$, hence its expected length is less than $H(p)+1$.

For singleton support step 1.1 gives $L^{\ast }(p)=H(p)=0<H(p)+1$. For support of size at least two, taking the infimum over all prefix codes in step 1.1 and using the code constructed in step 2.1 proves $H(p)\le L^{\ast }(p)<H(p)+1$. Empty support cannot occur for a probability vector.