Kraft–McMillan inequality

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.
• 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.

Let each source symbol from the alphabet

:$S=\backslash \{\backslash ,s\_1,s\_2,\backslash ldots,s\_n\backslash ,\backslash \}$

be encoded into a uniquely decodable code over an alphabet of size $r$ with codeword lengths

:$\backslash ell\_1,\backslash ell\_2,\backslash ldots,\backslash ell\_n.$

Then

:$\backslash sum\_\{i=1\}^\{n\}\; r^\{-\backslash ell\_i\}\; \backslash leqslant\; 1.$

Conversely, for a given set of natural numbers $\backslash ell\_1,\backslash ell\_2,\backslash ldots,\backslash ell\_n$ satisfying the above inequality, there exists a uniquely decodable code over an alphabet of size $r$ with those codeword lengths.

Image:AVLtreef.svg

Any binary tree can be viewed as defining a prefix code for the leaves of the tree. Kraft's inequality states that

: $\backslash sum\_\{\backslash ell\; \backslash in\; \backslash text\{leaves\}\}\; 2^\{-\backslash text\{depth\}(\backslash ell)\}\; \backslash leqslant\; 1.$

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

:$\backslash frac\{1\}\{4\}\; +\; 4\; \backslash left(\; \backslash frac\{1\}\{8\}\; \backslash right)\; =\; \backslash frac\{3\}\{4\}\; \backslash leqslant\; 1.$

Image:Kraft inequality example.png

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

Suppose that $\backslash ell\_1\; \backslash leqslant\; \backslash ell\_2\; \backslash leqslant\; \backslash cdots\; \backslash leqslant\; \backslash ell\_n$. Let $A$ be the full $r$-ary tree of depth $\backslash ell\_n$ (thus, every node of $A$ at level has $r$ children, while the nodes at level $\backslash ell\_n$ are leaves). Every word of length $\backslash ell\; \backslash leqslant\; \backslash ell\_n$ over an $r$-ary alphabet corresponds to a node in this tree at depth $\backslash ell$. The $i$th word in the prefix code corresponds to a node $v\_i$; let $A\_i$ be the set of all leaf nodes (i.e. of nodes at depth $\backslash ell\_n$) in the subtree of $A$ rooted at $v\_i$. That subtree being of height $\backslash ell\_n-\backslash ell\_i$, we have

:$|A\_i|\; =\; r^\{\backslash ell\_n-\backslash ell\_i\}.$

Since the code is a prefix code, those subtrees cannot share any leaves, which means that

:$A\_i\; \backslash cap\; A\_j\; =\; \backslash varnothing,\backslash quad\; i\backslash neq\; j.$

Thus, given that the total number of nodes at depth $\backslash ell\_n$ is $r^\{\backslash ell\_n\}$, we have

:$\backslash left|\backslash bigcup\_\{i=1\}^n\; A\_i\backslash right|=\; \backslash sum\_\{i=1\}^n\; |A\_i|\; =\; \backslash sum\_\{i=1\}^n\; r^\{\backslash ell\_n-\backslash ell\_i\}\; \backslash leqslant\; r^\{\backslash ell\_n\}$

from which the result follows.

Conversely, given any ordered sequence of $n$ natural numbers,

:$\backslash ell\_1\; \backslash leqslant\; \backslash ell\_2\; \backslash leqslant\; \backslash cdots\; \backslash leqslant\; \backslash ell\_n$

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

:$\backslash sum\_\{i=1\}^n\; r^\{\backslash ell\_n-\backslash ell\_i\}$

nodes. The question is whether we need to remove more leaf nodes than we actually have available — $r^\{\backslash ell\_n\}$ in all — in the process of building the code. Since the Kraft inequality holds, we have indeed

:$\backslash sum\_\{i=1\}^n\; r^\{\backslash ell\_n-\backslash ell\_i\}\; \backslash leqslant\; r^\{\backslash ell\_n\}$

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.

Now we will prove that the Kraft inequality holds whenever $S$ 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.{{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}}{{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}}

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

:$$

\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}

Consider all m-powers $S^m$, in the form of words $s\_\{i\_1\}s\_\{i\_2\}\backslash dots\; s\_\{i\_m\}$, where $i\_1,\; i\_2,\; \backslash dots,\; i\_m$ are indices between 1 and $n$. Note that, since S was assumed to uniquely decodable,

$s\_\{i\_1\}s\_\{i\_2\}\backslash dots\; s\_\{i\_m\}=s\_\{j\_1\}s\_\{j\_2\}\backslash dots\; s\_\{j\_m\}$ implies $i\_1=j\_1,\; i\_2=j\_2,\; \backslash dots,\; i\_m=j\_m$. This means that each summand corresponds to exactly one word in $S^m$. This allows us to rewrite the equation to

:$$

C^m = \sum_{\ell=1}^{m \cdot \ell_{max}} q_\ell \, r^{-\ell}

where $q\_\backslash ell$ is the number of codewords in $S^m$ of length $\backslash ell$ and $\backslash ell\_\{max\}$ is the length of the longest codeword in $S$. For an $r$-letter alphabet there are only $r^\backslash ell$ possible words of length $\backslash ell$, so $q\_\backslash ell\; \backslash leq\; r^\backslash ell$. Using this, we upper bound $C^m$:

:$$

\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}

Taking the $m$-th root, we get

:$$

C = \sum_{i=1}^n r^{-l_i} \leq \left( m \cdot \ell_{max} \right)^{\frac{1}{m}}

This bound holds for any $m\; \backslash in\; \backslash mathbb\{N\}$. The right side is 1 asymptotically, so $\backslash sum\_\{i=1\}^n\; r^\{-l\_i\}\; \backslash leq\; 1$ must hold (otherwise the inequality would be broken for a large enough $m$).

Given a sequence of $n$ natural numbers,

:$\backslash ell\_1\; \backslash leqslant\; \backslash ell\_2\; \backslash leqslant\; \backslash cdots\; \backslash leqslant\; \backslash ell\_n$

satisfying the Kraft inequality, we can construct a prefix code as follows. Define the i^th codeword, C_i, to be the first $\backslash ell\_i$ digits after the radix point (e.g. decimal point) in the base r representation of

:$\backslash sum\_\{j\; =\; 1\}^\{i\; -\; 1\}\; r^\{-\backslash ell\_j\}.$

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 $\backslash ell\_i$ digits of C_j form a larger number than C_i, so the code is prefix free.

The following generalization is found in.{{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 }}

{{Math theorem

| name = Theorem

| note =

| math_statement = If $C,\; D$ are uniquely decodable, and every codeword in $C$ is a concatenation of codewords in $D$, then $$\backslash sum\_\{c\backslash in\; C\}\; r^\{-|c|\}\; \backslash leq\; \backslash sum\_\{c\backslash in\; D\}\; r^\{-|c|\}$$

}}The previous theorem is the special case when $D=\; \backslash \{a\_1,\; \backslash dots,\; a\_r\backslash \}$.{{Math proof|title=Proof|proof=

Let $Q\_\{C\}(x)$ be the generating function for the code. That is, $$Q\_C(x)\; :=\; \backslash sum\_\{c\backslash in\; C\}\; x^$$

c

By a counting argument, the $k$-th coefficient of $Q\_C^n$ is the number of strings of length $n$ with code length $k$. That is, $$Q\_C^n(x)\; =\; \backslash sum\_\{k\backslash geq\; 0\}x^k\; \backslash \#(\backslash text\{strings\; of\; length\; \}n\backslash text\{\; with\; \}C\backslash text\{-codes\; of\; length\; \}k)$$ Similarly,

$$\backslash frac\{1\}\{1-Q\_C(x)\}\; =\; 1\; +\; Q\_C(x)\; +\; Q\_C(x)^2\; +\; \backslash cdots\; =\; \backslash sum\_\{k\backslash geq\; 0\}x^k\; \backslash \#(\backslash text\{strings\; with\; \}C\backslash text\{-codes\; of\; length\; \}k)$$

Since the code is uniquely decodable, any power of $Q\_C$ is absolutely bounded by $r|x|\; +\; r^2|x|^2\; +\; \backslash cdots\; =\; \backslash frac\{r|x|\}\{1-r|x|\}$, so each of $Q\_C,\; Q\_C^2,\; \backslash dots$ and $\backslash frac\{1\}\{1-Q\_C(x)\}$ is analytic in the disk .

We claim that for all $x\; \backslash in\; (0,\; 1/r)$, $$Q\_C^n\; \backslash leq\; Q\_D^n\; +\; Q\_D^\{n+1\}\; +\; \backslash cdots$$

The left side is $$\backslash sum\_\{k\backslash geq\; 0\}x^k\; \backslash \#(\backslash text\{strings\; of\; length\; \}n\backslash text\{\; with\; \}C\backslash text\{-codes\; of\; length\; \}k)$$ and the right side is

$$\backslash sum\_\{k\backslash geq\; 0\}x^k\; \backslash \#(\backslash text\{strings\; of\; length\}\backslash geq\; n\backslash text\{\; with\; \}D\backslash text\{-codes\; of\; length\; \}k)$$

Now, since every codeword in $C$ is a concatenation of codewords in $D$, and $D$ is uniquely decodable, each string of length $n$ with $C$-code $c\_1\backslash dots\; c\_n$ of length $k$ corresponds to a unique string $s\_\{c\_1\}\backslash dots\; s\_\{c\_n\}$ whose $D$-code is $c\_1\backslash dots\; c\_n$. The string has length at least $n$.

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

Thus, for all $x\backslash in\; (0,\; 1/r)$, and all $n\; =\; 1,\; 2,\; \backslash dots$, we have $$Q\_C\; \backslash leq\; \backslash frac\{Q\_D\}\{(1-Q\_D)^\{1/n\}\}$$ Taking $n\backslash to\; \backslash infty$ limit, we have $Q\_C(x)\; \backslash leq\; Q\_D(x)$ for all $x\backslash in\; (0,\; 1/r)$.

Since $Q\_C(1/r)$ and $Q\_D(1/r)$ both converge, we have $Q\_C(1/r)\; \backslash leq\; Q\_D(1/r)$ by taking the limit and applying Abel's theorem.

}}There is a generalization to quantum code.{{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 }}

{{Reflist|refs=

{{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

}}

{{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

}}

}}

• {{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}}.

• Chaitin's constant
• Canonical Huffman code

{{DEFAULTSORT:Kraft-McMillan inequality}}

Category:Coding theory

Category:Inequalities (mathematics)