Kraft–McMillan inequality

(Redirected from Kraft–McMillan theorem)

In coding theory, the Kraft–McMillan inequality gives a necessary and sufficient condition for the existence of a prefix code[1] (in Leon G. Kraft's version) or a uniquely decodable code (in Brockway McMillan's version) for a given set of codeword lengths. Its applications to prefix codes and trees often find use in computer science and information theory. The prefix code can contain either finitely many or infinitely many codewords.

Kraft's inequality was published in Kraft (1949). 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 (1956). 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

edit

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:

  • If Kraft's inequality holds with strict inequality, the code has some redundancy.
  • If Kraft's inequality holds with equality, the code in question is a complete code.[2]
  • If Kraft's inequality does not hold, the code is not uniquely decodable.
  • For every uniquely decodable code, there exists a prefix code with the same length distribution.

Formal statement

edit

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

edit
 
9, 14, 19, 67 and 76 are leaf nodes at depths of 3, 3, 3, 3 and 2, respectively.

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

edit

Proof for prefix codes

edit
 
Example for binary tree. Red nodes represent a prefix tree. The method for calculating the number of descendant leaf nodes in the full tree is shown.

First, let us show that the Kraft inequality holds whenever the code for   is a prefix code.

Suppose that  . Let   be the full  -ary tree of depth   (thus, every node of   at level   has   children, while the nodes at level   are leaves). 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 (i.e. of nodes at depth  ) 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 (i.e., all words that have this first word as a prefix) become unsuitable for inclusion in the code. We consider the descendants at depth   (i.e., the leaf nodes among the descendants); there are   such descendant nodes that are removed from consideration. The next iteration picks a (surviving) 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

edit

Now we will prove that the Kraft inequality holds whenever   is a uniquely decodable code. (The converse needs not be proven, since we have already proven it for prefix codes, which is a stronger claim.) The proof is by Jack I. Karush.[3][4]

We need only prove it when there are finitely many codewords. If there are infinitely many codewords, then any finite subset of it is also uniquely decodable, so it satisfies the Kraft–McMillan inequality. Taking the limit, we have the inequality for the full 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 (otherwise the inequality would be broken for a large enough  ).

Alternative construction for the converse

edit

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 (e.g. decimal 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.

Generalizations

edit

The following generalization is found in.[5]

Theorem — If   are uniquely decodable, and every codeword in   is a concatenation of codewords in  , then  

The previous theorem is the special case when  .

Proof

Let   be the generating function for the code. That is,  

By a counting argument, the  -th coefficient of   is the number of strings of length   with code length  . That is,   Similarly,
 

Since the code is uniquely decodable, any power of   is absolutely bounded by  , so each of   and   is analytic in the disk  .

We claim that for all  ,  

The left side is   and the right side is

 

Now, since every codeword in   is a concatenation of codewords in  , and   is uniquely decodable, each string of length   with  -code   of length   corresponds to a unique string   whose  -code is  . The string has length at least  .

Therefore, the coefficients on the left are less or equal to the coefficients on the right.

Thus, for all  , and all  , we have   Taking   limit, we have   for all  .

Since   and   both converge, we have   by taking the limit and applying Abel's theorem.

There is a generalization to quantum code.[6]

Notes

edit
  1. ^ Cover, Thomas M.; Thomas, Joy A. (2006), "Data Compression", Elements of Information Theory (2nd ed.), John Wiley & Sons, Inc, pp. 108–109, doi:10.1002/047174882X.ch5, ISBN 978-0-471-24195-9
  2. ^ De Rooij, Steven; Grünwald, Peter D. (2011), "LUCKINESS AND REGRET IN MINIMUM DESCRIPTION LENGTH INFERENCE", Philosophy of Statistics (1st ed.), Elsevier, p. 875, ISBN 978-0-080-93096-1
  3. ^ Karush, J. (April 1961). "A simple proof of an inequality of McMillan (Corresp.)". IEEE Transactions on Information Theory. 7 (2): 118. doi:10.1109/TIT.1961.1057625. ISSN 0018-9448.
  4. ^ Cover, Thomas M.; Thomas, Joy A. (2006). Elements of information theory (2nd ed.). Hoboken, N.J: Wiley-Interscience. ISBN 978-0-471-24195-9.
  5. ^ Foldes, Stephan (2008-06-21). "On McMillan's theorem about uniquely decipherable codes". arXiv:0806.3277 [math.CO].
  6. ^ Schumacher, Benjamin; Westmoreland, Michael D. (2001-09-10). "Indeterminate-length quantum coding". Physical Review A. 64 (4): 042304. arXiv:quant-ph/0011014. Bibcode:2001PhRvA..64d2304S. doi:10.1103/PhysRevA.64.042304. S2CID 53488312.

References

edit
  • McMillan, Brockway (1956), "Two inequalities implied by unique decipherability", IEEE Trans. Inf. Theory, 2 (4): 115–116, doi:10.1109/TIT.1956.1056818.

See also

edit