Kraft–McMillan inequality


In coding theory, the Kraft–McMillan inequality gives a necessary and sufficient condition for the existence of a prefix code or a uniquely decodable code for a given set of codeword lengths. Its applications to prefix codes and trees often find use in computer science and information theory.
Kraft's inequality was published in. However, Kraft's paper discusses only prefix codes, and attributes the analysis leading to the inequality to Raymond Redheffer. The result was independently discovered in. McMillan proves the result for the general case of uniquely decodable codes, and attributes the version for prefix codes to a spoken observation in 1955 by Joseph Leo Doob.

Applications and intuitions

Kraft's inequality limits the lengths of codewords in a prefix code: if one takes an exponential of the length of each valid codeword, the resulting set of values must look like a probability mass function, that is, it must have total measure less than or equal to one. Kraft's inequality can be thought of in terms of a constrained budget to be spent on codewords, with shorter codewords being more expensive. Among the useful properties following from the inequality are the following statements:
Let each source symbol from the alphabet
be encoded into a uniquely decodable code over an alphabet of size with codeword lengths
Then
Conversely, for a given set of natural numbers satisfying the above inequality, there exists a uniquely decodable code over an alphabet of size with those codeword lengths.

Example: binary trees

Any binary tree can be viewed as defining a prefix code for the leaves of the tree. Kraft's inequality states that
Here the sum is taken over the leaves of the tree, i.e. the nodes without any children. The depth is the distance to the root node. In the tree to the right, this sum is

Proof

Proof for prefix codes

First, let us show that the Kraft inequality holds whenever is a prefix code.
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. That subtree being of height, we have
Since the code is a prefix code, those subtrees cannot share any leaves, which means that
Thus, given that the total number of nodes at depth is, we have
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 each by choosing a word of length arbitrarily, then ruling out all words of greater length that have it as a prefix. There again, we shall interpret this in terms of leaf nodes of an -ary tree of depth. First choose any node from the full tree at depth ; it corresponds to the first word of our new code. Since we are building a prefix code, all the descendants of this node become unsuitable for inclusion in the code. We consider the descendants at depth ; there are such descendant nodes that are removed from consideration. The next iteration picks a node at depth and removes further leaf nodes, and so on. After iterations, we have removed a total of
nodes. The question is whether we need to remove more leaf nodes than we actually have available — in all — in the process of building the code. Since the Kraft inequality holds, we have indeed
and thus a prefix code can be built. Note that as the choice of nodes at each step is largely arbitrary, many different suitable prefix codes can be built, in general.

Proof of the general case

Now we will prove that the Kraft inequality holds whenever is a uniquely decodable code.
Denote. The idea of the proof is to get an upper bound on for and show that it can only hold for all if. Rewrite as
Consider all m-powers, in the form of words, where are indices between 1 and. Note that, since S was assumed to uniquely decodable,
implies. This means that each summand corresponds to exactly one word in. This allows us to rewrite the equation to
where is the number of codewords in of length and is the length of the longest codeword in. For an -letter alphabet there are only possible words of length, so. Using this, we upper bound :
Taking the -th root, we get
This bound holds for any. The right side is 1 asymptotically, so must hold.

Alternative construction for the converse

Given a sequence of natural numbers,
satisfying the Kraft inequality, we can construct a prefix code as follows. Define the ith codeword, Ci, to be the first digits after the radix point in the base r representation of
Note that by Kraft's inequality, this sum is never more than 1. Hence the codewords capture the entire value of the sum. Therefore, for j > i, the first digits of Cj form a larger number than Ci, so the code is prefix free.