Kraft's Inequality - Proof For Prefix Codes

Proof For Prefix Codes

Suppose that . Let be the full -ary tree of depth . Every word of length over an -ary alphabet corresponds to a node in this tree at depth . The th word in the prefix code corresponds to a node ; let be the set of all leaf nodes in the subtree of rooted at . Clearly

Since the code is a prefix code,

.

Thus, given that the total number of nodes at depth is ,

from which the result follows.

Conversely, given any ordered sequence of natural numbers,

satisfying the Kraft inequality, one can construct a prefix code with codeword lengths equal to by pruning subtrees from a full -ary tree of depth . First choose any node from the full tree at depth and remove all of its descendents. This removes fraction of the nodes from the full tree from being considered for the rest of the remaining codewords. The next iteration removes fraction of the full tree for total of . After iterations,

fraction of the full tree nodes are removed from consideration for any remaining codewords. But, by the assumption, this sum is less than 1 for all . Thus prefix code with lengths can be constructed for all source symbols.