= Solution
A <uniquely decodable code> is a map whose extension by concatenation to finite strings is <injective>. Write $\ell_j$ for its codeword lengths and assume the target alphabet has size $a\ge2$. The <Kraft–McMillan inequality> gives $K=\sum_j a^{-\ell_j}\le1$. The <Gibbs inequality> says $D(p\Vert q)=\sum_jp_j\log(p_j/q_j)\ge0$ for <probability distributions> $p,q$, with the usual convention for zero probabilities.
Set $q_j=a^{-\ell_j}/K$. For <Shannon entropy> $H(p)=-\sum_jp_j\log p_j$, the <Gibbs inequality> becomes
$$
0\le-H(p)+(\log a)\sum_jp_j\ell_j+\log K.
$$
Since $\log K\le0$, the <entropy lower bound for prefix codes> also applies to this <uniquely decodable code>:
$$
\boxed{\mathbb E\ell\ge\frac{H(p)-\log K}{\log a}\ge\frac{H(p)}{\log a}.}
$$
Back to article page
