Lesson 6

Theorem. Let the positive integers \(l_{1}, \dotsc, l_{n}\) satisfy the Kraft–McMillan inequality. Then there exists a prefix code with these symbol lengths.

Proof. Group equal \(l_{i}\) together: assume we have \(m\) distinct lengths \(l_{1} < l_{2} < \dotsb < l_{m}\), occurring \(n_{1}, n_{2}, \dotsc, n_{m}\) times. So \(n_{1}+ n_{2} + \dotsb + n_{m}=n\), and the Kraft–McMillan inequality becomes: \[\sum_{i=1}^{m}n_{i}2^{-l_i}\le 1 \ .\] We construct the prefix code step by step: first choose \(n_{1}\) words of length \(l_{1}\), then \(n_{2}\) of length \(l_{2}\), etc. Assume we've already chosen the words of lengths \(l_{1}, \dotsc, l_{k-1}\). These prevent us from selecting any of their extensions. So the number of available words of length \(l_{k}\) is: \[2^{l_k}-(n_{1}2^{l_k-l_1}+n_{2}2^{l_k-l_2}+\dotsb+n_{k-1}2^{l_k-l_{k-1}}) \ .\] If this number is at least \(n_{k}\), we can choose the required words. Dividing both sides by \(2^{l_k}\) gives: \[n_{1}2^{-l_1}+\dotsb+n_{k}2^{-l_k}\le 1 \ ,\] which follows from the inequality above.◼

Thus, we have shown that a code with minimum redundancy can be searched for among prefix codes. And now we’ll build one using Huffman's algorithm!