View source for Kraft–McMillan inequality

In [[coding theory]], the '''Kraft–McMillan inequality''' gives a necessary and sufficient condition for the existence of a [[prefix code]]<ref name="EIT" /> (in Leon G. Kraft's version) or a uniquely decodable code (in [[Brockway McMillan]]'s version) for a given set of [[Code word (communication)|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 {{harvtxt|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 {{harvtxt|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 ==

Kraft's inequality limits the lengths of codewords in a [[prefix code]]: if one takes an [[exponential function|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 (information theory)|redundancy]].
* If Kraft's inequality holds with equality, the code in question is a complete code.<ref name="de2011luckiness" /> 
* If Kraft's inequality does not hold, the code is not [[Variable-length code#Uniquely decodable codes|uniquely decodable]].
* For every uniquely decodable code, there exists a prefix code with the same length distribution.

== Formal statement ==
Let each source symbol from the alphabet
:<math>S=\{\,s_1,s_2,\ldots,s_n\,\}</math>

be encoded into a uniquely decodable code over an alphabet of size <math>r</math> with codeword lengths

:<math>\ell_1,\ell_2,\ldots,\ell_n.</math>

Then

:<math>\sum_{i=1}^{n} r^{-\ell_i} \leqslant 1.</math>

Conversely, for a given set of natural numbers <math>\ell_1,\ell_2,\ldots,\ell_n</math> satisfying the above inequality, there exists a uniquely decodable code over an alphabet of size <math>r</math> with those codeword lengths.

== Example: binary trees ==

[[Image:AVLtreef.svg|thumb|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 [[leaf node|leaves]] of the tree. Kraft's inequality states that

: <math> \sum_{\ell \in \text{leaves}} 2^{-\text{depth}(\ell)} \leqslant 1. </math>

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

:<math> \frac{1}{4} + 4 \left( \frac{1}{8} \right) = \frac{3}{4} \leqslant 1.</math>

== Proof ==

=== Proof for prefix codes ===
[[Image:Kraft inequality example.png|upright=1.5|thumb|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 <math>S</math> is a prefix code.

Suppose that <math>\ell_1 \leqslant \ell_2 \leqslant \cdots \leqslant \ell_n </math>. Let <math>A</math> be the full <math>r</math>-ary tree of depth <math>\ell_n</math> (thus, every node of <math>A</math> at level <math>< \ell_n</math> has <math>r</math> children, while the nodes at level <math>\ell_n</math> are leaves). Every word of length <math>\ell \leqslant \ell_n</math> over an <math>r</math>-ary alphabet corresponds to a node in this tree at depth <math>\ell</math>. The <math>i</math>th word in the [[prefix code]] corresponds to a node <math>v_i</math>; let <math>A_i</math> be the set of all leaf nodes (i.e. of nodes at depth <math>\ell_n</math>) in the subtree of <math>A</math> rooted at <math>v_i</math>. That subtree being of height <math>\ell_n-\ell_i</math>, we have

:<math>|A_i| = r^{\ell_n-\ell_i}.</math> 
Since the code is a prefix code, those subtrees cannot share any leaves, which means that

:<math>A_i \cap A_j = \varnothing,\quad i\neq j.</math>

Thus, given that the total number of nodes at depth <math>\ell_n</math> is <math>r^{\ell_n}</math>, we have

:<math> \left|\bigcup_{i=1}^n A_i\right|= \sum_{i=1}^n |A_i| = \sum_{i=1}^n r^{\ell_n-\ell_i} \leqslant r^{\ell_n}</math>

from which the result follows.

Conversely, given any ordered sequence of <math>n</math> natural numbers,

:<math>\ell_1 \leqslant \ell_2 \leqslant \cdots \leqslant \ell_n</math>

satisfying the Kraft inequality, one can construct a prefix code with codeword lengths equal to each <math>\ell_i</math> by choosing a word of length <math>\ell_i</math> 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 <math>r</math>-ary tree of depth <math>\ell_n</math>.  First choose any node from the full tree at depth <math>\ell_1</math>; 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 <math>\ell_n</math> (i.e., the leaf nodes among the descendants); there are  <math>r^{\ell_n-\ell_1}</math> such descendant nodes that are removed from consideration. The next iteration picks a (surviving) node at depth <math>\ell_2</math> and removes <math>r^{\ell_n-\ell_2}</math> further leaf nodes, and so on.  After <math>n</math> iterations, we have removed a total of

:<math>\sum_{i=1}^n r^{\ell_n-\ell_i}</math>

nodes. The question is whether we need to remove more leaf nodes than we actually have available &mdash; <math> r^{\ell_n}</math> in all &mdash; in the process of building the code. Since the Kraft inequality holds, we have indeed

:<math> \sum_{i=1}^n r^{\ell_n-\ell_i} \leqslant r^{\ell_n}</math>

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 <math>S</math> 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.<ref>{{Cite journal |last=Karush |first=J. |date=April 1961 |title=A simple proof of an inequality of McMillan (Corresp.) |url=https://ieeexplore.ieee.org/document/1057625 |journal=IEEE Transactions on Information Theory |language=en |volume=7 |issue=2 |pages=118 |doi=10.1109/TIT.1961.1057625 |issn=0018-9448}}</ref><ref>{{Cite book |last1=Cover |first1=Thomas M. |title=Elements of information theory |last2=Thomas |first2=Joy A. |date=2006 |publisher=Wiley-Interscience |isbn=978-0-471-24195-9 |edition=2nd |location=Hoboken, N.J}}</ref>

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 <math>C = \sum_{i=1}^n r^{-l_i}</math>. The idea of the proof is to get an upper bound on <math>C^m</math> for <math>m \in \mathbb{N}</math> and show that it can only hold for all <math>m</math> if <math>C \leq 1</math>. Rewrite <math>C^m</math> as

:<math>
\begin{align}
C^m & = \left( \sum_{i=1}^n r^{-l_i} \right)^m \\
& = \sum_{i_1=1}^n \sum_{i_2=1}^n \cdots \sum_{i_m=1}^n r^{-\left(l_{i_1} + l_{i_2} + \cdots + l_{i_m} \right)} \\
\end{align}
</math>

Consider all [[Cartesian product#Cartesian power|''m''-powers]] <math>S^m</math>, in the form of words <math>s_{i_1}s_{i_2}\dots s_{i_m}</math>, where <math>i_1, i_2, \dots, i_m</math> are indices between 1 and <math>n</math>. Note that, since ''S'' was assumed to uniquely decodable,
<math>s_{i_1}s_{i_2}\dots s_{i_m}=s_{j_1}s_{j_2}\dots s_{j_m}</math> implies <math>i_1=j_1, i_2=j_2, \dots, i_m=j_m</math>. This means that each summand corresponds to exactly one word in <math>S^m</math>. This allows us to rewrite the equation to

:<math>
C^m = \sum_{\ell=1}^{m \cdot \ell_{max}} q_\ell \, r^{-\ell}
</math>

where <math>q_\ell</math> is the number of codewords in <math>S^m</math> of length <math>\ell</math> and <math>\ell_{max}</math> is the length of the longest codeword in <math>S</math>. For an <math>r</math>-letter alphabet there are only <math>r^\ell</math> possible words of length <math>\ell</math>, so <math>q_\ell \leq r^\ell</math>. Using this, we upper bound <math>C^m</math>:

:<math>
\begin{align}
C^m & = \sum_{\ell=1}^{m \cdot \ell_{max}} q_\ell \, r^{-\ell} \\
& \leq \sum_{\ell=1}^{m \cdot \ell_{max}} r^\ell \, r^{-\ell} = m \cdot \ell_{max}
\end{align}
</math>

Taking the <math>m</math>-th root, we get
:<math>
C = \sum_{i=1}^n r^{-l_i} \leq \left( m \cdot \ell_{max} \right)^{\frac{1}{m}}
</math>

This bound holds for any <math>m \in \mathbb{N}</math>. The right side is 1 asymptotically, so <math>\sum_{i=1}^n r^{-l_i} \leq 1</math> must hold (otherwise the inequality would be broken for a large enough <math>m</math>).

=== Alternative construction for the converse ===
Given a sequence of <math>n</math> natural numbers,

:<math>\ell_1 \leqslant \ell_2 \leqslant \cdots \leqslant \ell_n</math>

satisfying the Kraft inequality, we can construct a prefix code as follows.  Define the ''i''<sup>th</sup> codeword, ''C''<sub>i</sub>, to be the first <math>\ell_i</math> digits after the [[radix point]] (e.g. decimal point) in the base ''r'' representation of

:<math>\sum_{j = 1}^{i - 1} r^{-\ell_j}.</math>

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 <math>\ell_i</math> digits of ''C''<sub>''j''</sub> form a larger number than ''C''<sub>''i''</sub>, so the code is prefix free.

== Generalizations ==

The following generalization is found in.<ref>{{cite arXiv|last=Foldes |first=Stephan |title=On McMillan's theorem about uniquely decipherable codes |date=2008-06-21 |class=math.CO |eprint=0806.3277 }}</ref>

{{Math theorem
| name = Theorem
| note = 
| math_statement = If <math display="inline">C, D</math> are uniquely decodable, and every codeword in <math display="inline">C</math> is a concatenation of codewords in <math display="inline">D</math>, then <math display="block">\sum_{c\in C} r^{-|c|} \leq \sum_{c\in D} r^{-|c|} </math>
}}The previous theorem is the special case when <math>D= \{a_1, \dots, a_r\}</math>.{{Math proof|title=Proof|proof=

Let <math display="inline">Q_{C}(x)</math> be the [[generating function]] for the code. That is, <math display="block">Q_C(x) := \sum_{c\in C} x^{|c|}</math>

By a counting argument, the <math display="inline">k</math>-th coefficient of <math display="inline">Q_C^n</math> is the number of strings of length <math display="inline">n</math> with code length <math display="inline">k</math>. That is, <math display="block">Q_C^n(x) = \sum_{k\geq 0}x^k \#(\text{strings of length }n\text{ with }C\text{-codes of length }k)</math> Similarly,<br />
<math display="block">\frac{1}{1-Q_C(x)} = 1 + Q_C(x) + Q_C(x)^2 + \cdots = \sum_{k\geq 0}x^k \#(\text{strings with }C\text{-codes of length }k)</math>

Since the code is uniquely decodable, any power of <math display="inline">Q_C</math> is absolutely bounded by <math display="inline">r|x| + r^2|x|^2 + \cdots = \frac{r|x|}{1-r|x|}</math>, so each of <math display="inline">Q_C, Q_C^2, \dots</math> and <math display="inline">\frac{1}{1-Q_C(x)}</math> is analytic in the disk <math display="inline">|x| < 1/r</math>.

We claim that for all <math display="inline">x \in (0, 1/r)</math>, <math display="block">Q_C^n \leq Q_D^n + Q_D^{n+1} + \cdots</math>

The left side is <math display="block">\sum_{k\geq 0}x^k \#(\text{strings of length }n\text{ with }C\text{-codes of length }k)</math> and the right side is

<math display="block">\sum_{k\geq 0}x^k \#(\text{strings of length}\geq n\text{ with }D\text{-codes of length }k)</math>
 
Now, since every codeword in <math display="inline">C</math> is a concatenation of codewords in <math display="inline">D</math>, and <math display="inline">D</math> is uniquely decodable, each string of length <math display="inline">n</math> with <math display="inline">C</math>-code <math display="inline">c_1\dots c_n</math> of length <math display="inline">k</math> corresponds to a unique string <math display="inline">s_{c_1}\dots s_{c_n}</math> whose <math display="inline">D</math>-code is <math display="inline">c_1\dots c_n</math>. The string has length at least <math display="inline">n</math>.

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

Thus, for all <math display="inline">x\in (0, 1/r)</math>, and all <math display="inline">n = 1, 2, \dots</math>, we have <math display="block">Q_C \leq \frac{Q_D}{(1-Q_D)^{1/n}}</math> Taking <math display="inline">n\to \infty</math> limit, we have <math display="inline">Q_C(x) \leq Q_D(x)</math> for all <math display="inline">x\in (0, 1/r)</math>.

Since <math display="inline">Q_C(1/r)</math> and <math display="inline">Q_D(1/r)</math> both converge, we have <math display="inline">Q_C(1/r) \leq Q_D(1/r)</math> by taking the limit and applying [[Abel's theorem]].

}}There is a generalization to [[quantum code]].<ref>{{Cite journal |last1=Schumacher |first1=Benjamin |last2=Westmoreland |first2=Michael D. |date=2001-09-10 |title=Indeterminate-length quantum coding |url=https://link.aps.org/doi/10.1103/PhysRevA.64.042304 |journal=Physical Review A |volume=64 |issue=4 |pages=042304 |doi=10.1103/PhysRevA.64.042304|arxiv=quant-ph/0011014 |bibcode=2001PhRvA..64d2304S |s2cid=53488312 }}</ref>

== Notes ==
{{Reflist|refs=
<ref name="EIT">{{citation
 | last1 = Cover | first1 = Thomas M.
 | last2 = Thomas | first2 = Joy A.
 | title = Elements of Information Theory
 | edition = 2nd
 | year = 2006 
 | publisher = John Wiley & Sons, Inc
 | isbn = 978-0-471-24195-9
 | pages = 108–109
 | doi = 10.1002/047174882X.ch5
 | chapter = Data Compression
 }}</ref>
<ref name="de2011luckiness">{{citation
 | last1 = De Rooij | first1 = Steven
 | last2 = Grünwald | first2 = Peter D.
 | title = Philosophy of Statistics
 | edition = 1st
 | year = 2011 
 | publisher = Elsevier
 | isbn = 978-0-080-93096-1
 | pages = 875
 | chapter = LUCKINESS AND REGRET IN MINIMUM DESCRIPTION LENGTH INFERENCE
 }}</ref>
}}

== References ==
* {{citation
 | last = Kraft | first = Leon G.
 | title = A device for quantizing, grouping, and coding amplitude modulated pulses
 | publisher = MS Thesis, Electrical Engineering Department, [[Massachusetts Institute of Technology]]
 | location = Cambridge, MA
 | year = 1949
 | hdl = 1721.1/12390
 | type = Thesis
 }}.

* {{citation
 | last = McMillan | first = Brockway
 | title = Two inequalities implied by unique decipherability
 | journal = IEEE Trans. Inf. Theory
 | volume = 2 | issue = 4 | year = 1956 | pages = 115–116
 | doi = 10.1109/TIT.1956.1056818}}.

==See also==
*[[Chaitin's constant]]
*[[Canonical Huffman code]]

{{DEFAULTSORT:Kraft-McMillan inequality}}
[[Category:Coding theory]]
[[Category:Inequalities]]