Back to the on-screen lesson ·
The arithmetic test that decides which sets of codeword lengths a prefix code can have, and the tree argument behind it.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to compute the Kraft sum of a set of codeword lengths and decide whether a prefix code with them exists, prove necessity by counting the descendants each codeword owns in the tree, carry out the shortest-first construction that proves sufficiency, recognise a complete code, work out how much of the budget a code leaves unspent, and use the leftover to decide which lengths a format can still afford.
Prefix codes and their trees, and the fact that a codeword rules out everything below it. This lesson turns that observation into an exact arithmetic test on the lengths alone, before any codewords are chosen.
The Kraft sum of a set of lengths is $\sum_i 2^{-\ell_i}$, and each term is the share of the tree that codeword claims. A code is complete when the sum is exactly $1$ and no leaf is wasted. McMillan's theorem extends the inequality from prefix codes to every uniquely decodable code.
Kraft's inequality: a binary prefix code with codeword lengths $\ell_1, \ldots, \ell_m$ exists if and only if $$\sum_{i=1}^m 2^{-\ell_i} \le 1.$$ Necessity: grow the tree to depth $L = \max \ell_i$; a codeword at depth $\ell_i$ owns $2^{L - \ell_i}$ of the $2^L$ nodes at depth $L$, and prefix-freeness makes these sets disjoint, so $\sum 2^{L - \ell_i} \le 2^L$. Sufficiency: place the codewords shortest first, each at the leftmost node not below an earlier codeword; the inequality guarantees such a node exists at every step. Equality means the code is complete: no leaf is wasted. McMillan's theorem extends necessity to every uniquely decodable code, so nothing is gained by giving up the prefix property. Kraft's inequality is the bridge between codes and probabilities: the numbers $q_i = 2^{-\ell_i}$ behave like a (sub)probability distribution, which is exactly what the source coding theorem exploits.
Another way: picture
The unit interval $[0, 1)$ cut into dyadic pieces: a codeword of length $\ell$ is a piece of width $2^{-\ell}$ at the position its bits spell in binary. Prefix-free codewords are disjoint pieces, so their widths sum to at most $1$; a complete code tiles the whole interval.
Another way: steps
Think of the code tree as a budget of $1$. A codeword of length $\ell$ spends $2^{-\ell}$ of it, because it claims a whole subtree and forbids everything below. Prefix-freeness makes the claims disjoint, so the spending can never exceed the budget: that is Kraft's inequality $\sum_i 2^{-\ell_i} \le 1$.
| Codeword of length $\ell$ | share of the tree $2^{-\ell}$ | leaves lost at depth $5$ |
|---|---|---|
| $1$ | $1/2$ | $16$ |
| $2$ | $1/4$ | $8$ |
| $3$ | $1/8$ | $4$ |
| $4$ | $1/16$ | $2$ |
| $5$ | $1/32$ | $1$ |
The last column counts the same thing at a fixed depth $L = 5$: a codeword at depth $\ell$ owns $2^{L - \ell}$ of the $2^L$ deepest nodes, and disjointness gives $\sum_i 2^{L - \ell_i} \le 2^L$, which is Kraft after dividing by $2^L$. Equality means every leaf is used: the code is complete, and there is no room for one more codeword of any length.
| lengths | Kraft sum | prefix code? | note |
|---|---|---|---|
| $1, 2, 2, 2$ | $1/2 + 3/4 = 1.25$ | no | over budget |
| $1, 2, 3, 3$ | $1/2 + 1/4 + 1/8 + 1/8 = 1$ | yes | complete: $0, 10, 110, 111$ |
| $2, 2, 3, 4, 4$ | $1/4 + 1/4 + 1/8 + 1/16 + 1/16 = 3/4$ | yes | a quarter of the tree unused |
| $1, 1, 2$ | $1/2 + 1/2 + 1/4 = 1.25$ | no | two length-$1$ words fill the tree |
To build the code once the sum is at most $1$: sort the lengths shortest first and give each codeword the leftmost node at its depth that is not below an already chosen codeword. The inequality guarantees such a node exists at every step. Lengths $2, 2, 3, 4, 4$ give $00, 01, 100, 1010, 1011$, and the free quarter under $11$ is exactly the $1 - \tfrac{3}{4}$ the sum left unspent.
McMillan's theorem says the inequality is necessary for every uniquely decodable code, not just prefix codes. So giving up instant decoding buys nothing: whatever lengths a uniquely decodable code achieves, a prefix code achieves too.
Common mistakes
The first error is adding one term per distinct length rather than one per codeword: four codewords contribute four terms even when several share a length. The second is reading the inequality as a statement about optimality — it decides only whether a code with those lengths exists, and says nothing about whether the code is any good. The third is thinking equal lengths are required, or that a sum below $1$ is somehow wrong; a sum below $1$ simply means tree left over. And a sum above $1$ rules out not only prefix codes but every uniquely decodable code, which is McMillan's contribution and is easy to forget.
Lengths $1, 2, 2, 2$: $\tfrac{1}{2} + 3 \cdot \tfrac{1}{4} = 1.25 > 1$.
Sum the $2^{-\ell}$.
No prefix code exists; lengths $1, 2, 3, 3$ sum to exactly $1$ and give the complete code $0, 10, 110, 111$.
The tree runs out of leaves.
Lengths $2, 2, 3, 4, 4$: sum $\tfrac{1}{4} + \tfrac{1}{4} + \tfrac{1}{8} + \tfrac{1}{16} + \tfrac{1}{16} = \tfrac{3}{4} \le 1$.
Feasible, not complete.
Shortest first, leftmost free: $00, 01, 100, 1010, 1011$; the leftover $\tfrac{1}{4}$ is the unused subtree under $11$.
Common denominator $2^4 = 16$: the terms are $8, 2, 1, 1$ sixteenths.
Sum $= \tfrac{12}{16} = \tfrac{3}{4} \le 1$.
A prefix code exists, for instance $0, 100, 1010, 1011$, and a quarter of the tree is still free.
A complete code has one codeword of length $1$ and two of length $3$; the rest have length $5$.
Spent so far: $\tfrac{1}{2} + \tfrac{2}{8} = \tfrac{3}{4}$; remaining budget $\tfrac{1}{4}$.
Each length-$5$ codeword costs $\tfrac{1}{32}$, so there are $\tfrac{1/4}{1/32} = 8$ of them.
Equivalently $2^{5 - 2} = 8$.
Kraft mass used: $\tfrac{1}{2} + \tfrac{1}{4} = \tfrac{3}{4}$; left: $\tfrac{1}{4}$.
Each word of length $4$ costs $\tfrac{1}{16}$: four more words, $1100, 1101, 1110, 1111$.
Compute the Kraft sum $\sum_i 2^{-\ell_i}$ for each set of binary codeword lengths.
| Kraft sum | |
|---|---|
| Lengths $1, 2, 3, 3$ | |
| Lengths $1, 2, 2, 2$ | |
| Lengths $1, 2, 4, 4$ |
Build the proof that any binary prefix code with lengths $\ell_1, \ldots, \ell_m$ satisfies $\sum_i 2^{-\ell_i} \le 1$.
This task has no paper form; do it on a device.
Kraft's inequality holds for the lengths $2, 2, 3, 4, 4$. Put the steps of the standard construction in the order they are carried out.
Number the steps in order (write the number in the box):
Do codeword lengths $1, 3, 2$ admit a binary prefix code?
A file format encodes three record types with the prefix codes $0$, $110$ and $111$, and a fourth type is to be added with a codeword of length $L$. Give the set of whole-number lengths $L$ that can be used, as an interval.
This task has no paper form; do it on a device.
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
A complete binary prefix code has one codeword of length $1$ and two of length $3$. All its remaining codewords have length $4$. How many are there?
Answer:
You can decide which length sets are possible, build a code from any feasible set, and say how much tree is left over. Say in your own words why prefix-freeness is what makes the descendant sets disjoint, and what would go wrong without it. Next: how short a code can be on average, and Shannon's answer.
13. Your turn: how many codewords of length $4$ can join a prefix code that already has $0$ and $10$?, step 2