6.1.1: Kraft Inequality

Last updated
Save as PDF

Page ID: 51015

Paul Penfield, Jr.
Massachusetts Institute of Technology via MIT OpenCourseWare

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Since the number of distinct codes of short length is limited, not all codes can be short. Some must be longer, but then the prefix condition limits the available short codes even further. An important limitation on the distribution of code lengths \(L_i\) was given by L. G. Kraft, an MIT student, in his 1949 Master’s thesis. It is known as the Kraft inequality:

\(\displaystyle \sum_{i} \dfrac{1}{2^{L_i}} \leq 1 \tag{6.1}\)

Any valid set of distinct codewords obeys this inequality, and conversely for any proposed \(L_i\) that obey it, a code can be found.

For example, suppose a code consists of the four distinct two-bit codewords 00, 01, 10, and 11. Then each \(L_i\) = 2 and each term in the sum in Equation 6.1 is 1/2\(^2\) = 1/4. In this case the equation evaluates to an equality, and there are many different ways to assign the four codewords to four different symbols. As another example, suppose there are only three symbols, and the proposed codewords are 00 01, and 11. In this case the Kraft inequality is an inequality. However, because the sum is less than 1, the code can be made more efficient by replacing one of the codewords with a shorter one. In particular, if the symbol represented by 11 is now represented by 1 the result is still a prefix-condition code but the sum would be (1/2\(^2\)) + (1/2\(^2\)) + (1/2) = 1.

The Kraft inequality can be proven easily. Let \(L_{max}\) be the length of the longest codeword of a prefixcondition code. There are exactly \(2^{L_{max}}\) different patterns of 0 and 1 of this length. Thus

\(\displaystyle \sum_{i} \dfrac{1}{2^{L_{max}}} = 1 \tag{6.2}\)

where this sum is over these patterns (this is an unusual equation because the quantity being summed does not depend on \(i\)). At least one of these patterns is one of the codewords, but unless this happens to be a fixed-length code there are other shorter codewords. For each shorter codeword of length \(k\) (\(k < L_{max}\)) there are exactly \(2^{L_{max−k}}\) patterns that begin with this codeword, and none of those is a valid codeword (because this code is a prefix-condition code). In the sum of Equation 6.2 replace the terms corresponding to those patterns by a single term equal to 1/2\(^k\). The sum is unchanged. Continue this process with other short codewords. When it is complete, there are terms in the sum corresponding to every codeword, and the sum is still equal to 1. There may be other terms corresponding to patterns that are not codewords—if so, eliminate them from the sum in Equation 6.2. The result is exactly the sum in Equation 6.1 and is less than or equal to 1. The proof is complete.