Entropy lower bound for prefix codes

Every binary prefix code has expected length at least its source entropy; Shannon lengths achieve expected length strictly below $H+1$.

For a complete binary prefix code with lengths ${\ell }_i$, the Kraft inequality is an equality: ${\sum }_i{2}^{-{\ell }_i}=1$. Put $q_i=2^{-{\ell }_i}$. The difference between expected codeword length and Shannon entropy isThe Kullback-Leibler divergence is nonnegative and vanishes exactly when $p=q$. Hence a complete code is entropy-tight exactly for its dyadic matching source. For example, lengths $(1,2,2)$ match probabilities $(1/2,1/4,1/4)$. Being an optimal prefix code among symbol-by-symbol codes is a weaker condition and does not imply this equality.

For a discrete memoryless source of entropy $H$, every uniquely decodable binary code has expected length at least $H$. Shannon code lengths satisfy $H\le \overline{\ell }<H+1$, and block coding can make the expected length per source symbol arbitrarily close to $H$.