2
$\begingroup$

I have a question regarding the redundancy of Huffman coding. I know that for a general prefix code we have the following inequality:

$$ H(X) \le R \le H(X) + 1 $$

$R$ being the rate (average codeword length) and $H$ is the entropy. Based on this relation, how can we conclude that Huffman coding is very inefficient if entropy of the source is much smaller than 1 bit/symbol?

$\endgroup$
1
$\begingroup$

If $X$ is any non-constant source, then any codeword in any prefix code for $X$ has length at least $1$, and so $R \geq 1$. Therefore if $X$ is a source with very low entropy then there's a large discrepancy between $H(X) \approx 0$ and $R \approx 1$.

As a concrete example, consider a binary source in which the probability of one of the options is $\epsilon$. Then $H(X) = \epsilon \log (1/\epsilon) + O(\epsilon)$ whereas $R = 1$.

$\endgroup$
  • $\begingroup$ I don't understand how based on that relation we can conclude that R has to be at least 1 bit/symbol. If H is very close to zero, but still nonzero, doesn't the relation imply that R is somewhere between 0 and 1?! I am confused $\endgroup$ – Niousha May 24 at 8:44
  • $\begingroup$ It’s not based on that relation. It’s based on the definition of $R$. $\endgroup$ – Yuval Filmus May 24 at 9:14
  • $\begingroup$ Thank you. I had the wrong idea about R, since in examples for Vector Huffman coding I'd seen for example R = 0.78 bit/pixel. $\endgroup$ – Niousha May 24 at 15:46
  • $\begingroup$ That can only happen if you’re encoding blocks of symbols. $\endgroup$ – Yuval Filmus May 24 at 16:43

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.