= Solution
A binary <uniquely decodable code> assigns a finite binary word to each source symbol, so that no two distinct finite sequences of source symbols have the same concatenated encoding. This does not require the stronger prefix property. All codeword lengths are positive.
Put $S=\sum_j2^{-l_j}$ and let $A_{k,L}$ count sequences of $k$ source symbols whose encoded total length is $L$. Expanding the product gives
$$
S^k=\sum_{L=kl_{\min}}^{kl_{\max}}A_{k,L}2^{-L}.
$$
Unique decodability makes these encodings distinct, so $A_{k,L}\leq2^L$, the number of binary strings of that length. There are at most $k(l_{\max}-l_{\min})+1$ possible lengths. Therefore
$$
S^k\leq k(l_{\max}-l_{\min})+1.
$$
Taking $k$th roots and letting $k\to\infty$ proves the <McMillan inequality>:
$$
\boxed{\sum_j2^{-l_j}\leq1.}
$$
Back to article page
