Kraft–McMillan inequality

In coding theory, the Kraft–McMillan inequality gives a necessary and sufficient condition for the existence of a prefix code

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 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 ith codeword, Ci, 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 Cj form a larger number than Ci, so the code is prefix free.

Generalizations

The following generalization is found in.

The previous theorem is the special case when <math>D= \{a_1, \dots, a_r\}</math>.</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.

Kraft–McMillan inequality

Alternative construction for the converse

Generalizations

Notes

References

See also