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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$
4
  • $\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
    Commented May 24, 2019 at 8:44
  • $\begingroup$ It’s not based on that relation. It’s based on the definition of $R$. $\endgroup$
    – Yuval Filmus
    Commented May 24, 2019 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
    Commented May 24, 2019 at 15:46
  • $\begingroup$ That can only happen if you’re encoding blocks of symbols. $\endgroup$
    – Yuval Filmus
    Commented May 24, 2019 at 16:43

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.