= Solution
Order the prescribed lengths as $l_1\leq\cdots\leq l_N$. Construct a <prefix code> on the binary tree. At depth $l_i$, previously assigned codewords exclude $\sum_{j<i}2^{l_i-l_j}$ of the $2^{l_i}$ vertices. The <Kraft inequality> implies
$$
\sum_{j<i}2^{l_i-l_j}+1\leq2^{l_i},
$$
so an available vertex can be assigned to the next symbol. None of the assigned words is a prefix of another. Reading each word up to the next assigned vertex gives unique decoding, so this constructs the required <uniquely decodable code>.
For completeness the same length inequality is necessary even for a <uniquely decodable code> which is not a <prefix code>. Write $K=\sum_a2^{-l(a)}$ and $L=\max_a l(a)$. For $r$ successive symbols, distinct symbol strings have distinct concatenated codewords. At total length $j$ there are at most $2^j$ such strings. Therefore
$$
K^r=\sum_{j=r}^{rL}N_j2^{-j}\leq rL.
$$
Taking $r$th roots and letting $r\to\infty$ gives $K\leq1$. This is the <McMillan inequality>.
Set $q(a)=2^{-l(a)}/K$. The <relative entropy> inequality gives
$$
\mathbb E l(A)-H(A)=\sum_a p(a)\log_2\frac{p(a)}{q(a)}-\log_2K\geq0.
$$
Here <Shannon entropy> uses base $2$, with $0\log0=0$. The <relative entropy> is nonnegative, with equality precisely when the two <probability distributions> coincide; this follows from $\log t\leq t-1$. Consequently \b[equality holds exactly when]
$$
\boxed{K=1\quad\hbox{and}\quad p(a)=2^{-l(a)}\ \hbox{for every }a.}
$$
In particular all alphabet symbols must have positive probability for equality with finite prescribed lengths.
Back to article page
