3
$\begingroup$

Is it true to say that Huffman codes always satisfy Kraft's inequality with strict equality?

At first, I thought the statement is wrong since for Huffman coding there is no assumptions on the probabilities. However, when I tried evaluation the Kraft inequality for several Huffman codes, I realized that it's got nothing to do with the probabilities. It's the algorithm.

I looked for a nice mathematical proof for this, but couldn't find any. Would appreciate your help.

$\endgroup$

1 Answer 1

3
$\begingroup$

All Huffman codes satisfy Kraft’s inequality with strict equality. We will give two proofs of this fact, one specific to Huffman codes, and the other applying to all minimum redundancy codes.

First proof. The first proof is inductive. Recall that Huffman’s algorithm proceeds as follows. We choose the two symbols with minimal probability, and merge them. We then run the algorithm on the new distribution. Finally, we split the merged symbol into two symbols by adding a suffix of 0 to one of them and of 1 to the other.

When there are only two symbols left, Huffman’s algorithm assigns them the codewords 0 and 1, and since $2^{-1} + 2^{-1} = 1$, we see that Kraft’s inequality is satisfied with equality.

Now suppose that there are more than two symbols. Huffman’s algorithm merges two of them, and then runs on the resulting code. The induction hypothesis shows that Kraft’s inequality is satisfied with equality on the new code. The final step is splitting one of the symbols. In this step, a codeword of length $\ell$ is replaced by two codewords of length $\ell+1$. Since $2^{-\ell} = 2 \cdot 2^{-\ell-1}$, we see that the final code also satisfies Kraft’s inequality with equality.

Second proof. The second proof applies to any minimum redundancy code. We start by associating with each prefix code a binary tree. This is done as follows. If the prefix code consists of just the empty word, then the binary tree is a leaf. Otherwise, we construct a binary tree for all codewords starting with 0, another one from all codewords starting with 1, and join the two at the root. If we think of the edges as labeled by 0 and 1, then we can recover the codewords by traversing the tree from root to leaves and concatenating the symbols written on the edges.

A simple induction shows that $\sum_f 2^{-\ell(f)} \leq 1$, where $f$ goes over all leaves, and $\ell(f)$ is the depth of $f$; this is just Kraft’s inequality. The same proof also shows that equality holds iff all internal nodes have exactly two children. In this case we call the code complete.

If the code is incomplete, there is an internal vertex with only a single child. We can replace this vertex by its child, thus obtaining a new code in which no codeword gets longer, and some get strictly shorter. The new code has less redundancy than the original one. This shows that if we start with a minimum redundancy code, then the code must be complete, and so Kraft’s inequality holds with equality.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.