1
$\begingroup$

I have been given several examples I the aim is to explain why it is not a Huffman code. So, for instance, the first one was:

$\{00,01,10,110\}$

This code is not Huffman becuase it has just one codeword of maximum length whereas there should be two as a minimum.

Next, the one I hava a problem in proving:

$\{01,10\}$

Why this code is not a Huffman code?

$\endgroup$
  • $\begingroup$ How would you decode 00000000? With a Huffman code, any sequence of bits can be decoded (except that there might be bits missing at the end). Simpler, how would you decode 00? $\endgroup$ – gnasher729 Jan 12 at 18:17
0
$\begingroup$

(Minimum number of codewords) (Binary complete) Huffman code of maximal code length $n$ must have at least $n+1$ codewords.

The maximal code length of codewords $\{01, 10\}$ is 2. However, there are only two codewords. So those codewords is not a Huffman code.


(Exercise.) Prove the claim of the minimum number of codewords of Huffman code.

$\endgroup$
0
$\begingroup$

A Huffman code is defined by two properties:

  1. No code is a prefix of another code.

  2. If you add up $2^{-k}$, where k is the length of each code, then the total is 1.

In your second case, you have two codes of length 2. If you add $2^{-2}$ twice, the sum is 1/2, not 1. Actually, in your first example the sum is 7/8ths.

To make the sum 1, the number of codes with maximum length must be even. (If you have n codes of maximum length k, they add up to $n \cdot 2^{-k}$. If n is odd you can't get rid of the $2^{-k}$ and the sum cannot be 1). You prove Apass-Jack's claim with complete induction.

$\endgroup$
  • 1
    $\begingroup$ You're describing prefix code saturating Kraft's inequality. Huffman code are often taken to mean codes which could be produced by Huffman's algorithm under some nondeterministic choice of which two leaves to merge. These are a strict subset of minimum redundancy codes, as shown by Gallager in Variations on a Theme by Huffman. $\endgroup$ – Yuval Filmus Jan 12 at 20:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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