The Kraft-Szilard Inequality (1949)

Additional reading: p.420 of Rissanen's paper on a universal prior for integers.

Lemma:

$$\sum_{i=1}^n 2^{-l_i} \le 1$$ (10)

is a necessary and sufficient condition for $l_1, l_2, \cdots, l_n$ to be the lengths of codewords of a prefix code of size n.

It is easiest to prove this by using the prefix-tree model of coding. We first prove the only if or necessary part and then prove the if or sufficient part.

Proof of necessity. Let $m = \underset{i}{\rm max}\quad l_i$.

Then the l_i can all be represented as the leaves of a binary tree of depth m from the root. Consider such a tree that is full, i.e. every node at depth less than m has two sub-trees and every node at depth m has two leaves. Then, the node at depth i is the ancestor of 2^m-i leaves.

So the total number of leaves fathered by all of the nodes at depths $l_1, l_2, \cdots, l_n$ is $\sum_{i = 1}^n 2^{m-l_i}$

Since no leaf is on the path to any other leaf, the above quantity cannot be greater than the number of leaves in the full tree. So

$$\begin{eqnarray*}\sum_{i=1}^n 2^{m-l_i} &\le& 2^m\\ \Rightarrow \sum_{i = 1}^n 2^{-l_i} &\le& 1\\ \end{eqnarray*}$$

This proves necessity, i.e. a code with i codewords of lengths l_i is a prefix code only if the inequality (11) holds.

We now have to prove sufficiency, i.e. If inequality (11) holds then it is possible to construct a prefix code with just the l_i as the lengths of its codewords.

Proof of sufficiency.

Again, start with a full tree of depth m. Now arrange the lengths l_i in non-decreasing order such that $l_1 \le l_2 \le \cdots \le l_n$.

Pick any unassigned node at depth l₁ from the root and delete all 2^l_n-l₁ of its descendant leaves as well as all the nodes in the paths to them. This turns the node into a leaf which is assigned a codeword of length l₁.

Repeat this process for $l_2, l_3, \cdots, l_n$. We claim that if (11) holds then it will be possible to find a unique assignment thus for each l_i.

Proof of this is by contradiction. Assume not. Then for some j < n, no unassigned and undeleted node at depth l_j could be found, i.e. all nodes at depth l_j have been either assigned or deleted. This number is 2^l_j.

But recall that each previous assignment of l_i has excluded (assigned or deleted) exactly 2^l_j-l_i nodes at depth j. So the total number of nodes at level j excluded upto this point is $\sum_{i=1}^{j-1} 2^{l_j - l_i}$. Then

$$\begin{eqnarray*}& &\sum_{i=1}^{j-1} 2^{l_j - l_i} = 2^{l_j}\\ \Rightarrow & &\... ...1} 2^{-l_i} = 1\\ \Rightarrow & &\sum_{i=1}^{j} 2^{-l_i} > 1\\ \end{eqnarray*}$$

which contradicts the Kraft inequality. So it will indeed be possible to find assignments for every length l_i if the inequality holds.