= Solution
A binary <prefix code> assigns distinct finite binary strings to the source symbols, with no assigned string a prefix of another. It is instantaneous because a complete codeword is recognized without needing the next word's bits.
Associate a word of length $\ell$ with its dyadic subinterval of $[0,1)$ of length $2^{-\ell}$. A prefix relation corresponds to interval containment. Prefix-free words therefore give disjoint intervals, whose total length is at most one. This proves necessity of <Kraft inequality>.
For sufficiency, sort the requested nonnegative integer lengths increasingly and construct a code greedily in a binary tree. At depth $\ell_j$, the preceding codewords forbid exactly $\sum_{i<j}2^{\ell_j-\ell_i}$ nodes. The assumed inequality, retaining the positive contribution of the present word, bounds this integer by $2^{\ell_j}-1$. Thus at least one node is available; choose it. It is not below an earlier codeword, and the nondecreasing lengths prevent it from being a proper ancestor of an earlier word. Continue to obtain a <prefix code> of all the required lengths. Hence
$$
\boxed{\text{Such a code exists exactly when }\sum_k2^{-\ell_k}\le1}.
$$
Back to article page
