= Dyadic source matched to a complete prefix code
{title2=$\overline\ell=H(p)\ \Longleftrightarrow\ p_i=2^{-\ell_i}$}
For a complete binary <prefix code> with lengths $\ell_i$, the <Kraft inequality> is an equality: $\sum_i2^{-\ell_i}=1$. Put $q_i=2^{-\ell_i}$. The difference between <expected codeword length> and <Shannon entropy> is
$$
\overline\ell-H(p)=\sum_i p_i\log_2\frac{p_i}{q_i}.
$$
The <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.
Back to article page
