Lesson 4

Now assume that we know the frequencies of all symbols \(p_{1}, \dotsc, p_{n}\) (\(p_{1}+\dotsb+p_{n}=1\)). We want to construct a uniquely decodable code \(\phi \colon \Sigma \to \{0,1\}^{*}\) with minimum redundancy coefficient: \(\sum_{i=1}^{n}p_{i}\cdot |\phi(a_{i})|\) (also called the average length). Of course, we want the code lengths to be as short as possible. On the other hand, we want the code to be uniquely decodable. It turns out that given a set of codeword lengths, we can determine whether such a code exists.

Theorem (Kraft–McMillan, 1949/1956). Let \(l_{1}, \dotsc, l_{n}\) be the lengths of a uniquely decodable code. Then \[2^{-l_1}+2^{-l_2}+\dotsb+2^{-l_n}\le 1 \ .\]

For prefix codes, this theorem has a particularly intuitive proof: draw a tree, complete it to a full one, and see what portion of the leaves each symbol gets (\(2^{-l_i}\), indeed). Alternatively, imagine a segment of length 1 at the root. As we descend the tree, we split the segment in half. Then, the symbol \(a_{i}\) will get a segment of length \(2^{-l_i}\).

Proof. Let \(t\) be a numerical parameter we’ll choose later. Raise the left-hand side of the inequality to the power \(t\): \[\left(\sum_{i=1}^{n}2^{-l_i}\right)^{t}=\sum_{j=1}^{t\cdot \max l_i}c_{j}2^{-j}\ .\] Here, \(c_{j}\) is the coefficient of \(2^{-j}\), i.e., the number of ways to represent \(j\) as a sum \(l_{i_1}+\dotsb+l_{i_t}\). Each such sum corresponds to a string \(\phi(a_{i_1})\dotsb\phi(a_{i_t})\). All such strings have length \(j\) and are distinct due to the unique decodability. So \(c_{j} \le 2^{j}\), and the sum does not exceed \(t \cdot \max l_{i}\). If \(\sum 2^{-l_i}> 1\), then for large enough \(t\), the inequality \[\left(\sum_{i=1}^{n}2^{-l_i}\right)^{t} \le t \cdot \max l_{i}\] would be violated (since exponentials eventually dominate linear functions).◼