# Gap between the average length of a Huffman code and its entropy

Difference between “average length” and “entropy” gives the percent of optimal. The optimal case is when the average length of a code is equal to the entropy. For example if average length is 1 and entropy is 0.72: (1- 0.72) = 0.28 -> 28% worse than optimal.

If both “average length” and “entropy” are 1, the compression is optimal.

But what does it mean if the result is negative value?

Note: entropy : -(pr*lg(pr)). Average length: probability*number of bit

• The average number of bits you need simply can't be lower than the entropy, so the result could not be negative. – R B Feb 3 '14 at 15:16
• Are you defining entropy as the en.wikipedia.org/wiki/Kolmogorov_complexity ? – Chad Brewbaker Feb 3 '14 at 15:19
• I defined the entropy as follow: - (p1 Log p1 + p2 Log p2). P= probability. Base of Log is 2. – user21415 Feb 3 '14 at 15:31
• @user21415 Can you please fix your English? It is hard to understand your sentences. It would be even better if your formulas were written in LaTeX. – Yuval Filmus Feb 6 '14 at 5:25

Shannon's source coding theorem shows that you cannot compress data more than its entropy, even if you encode chunks at a time. For the specific case of prefix-free codes (even uniquely-decodable codes), this follows from Kraft's inequality, which for a uniquely-decodable code with codeword lengths $\ell_i$ states that $$\sum_i 2^{-\ell_i} \leq 1,$$ and furthermore every code can be "improved" (by only decreasing its codeword lengths) so that equality holds. Suppose that the probability of the $i$th symbol is $p_i$. The average codeword length is $E = \sum_i p_i \ell_i$. We want to minimize $E$ given the constraint $\sum_i 2^{-\ell_i} = 1$, and furthermore $\ell_i \geq 0$ are integers. Relaxing integrality, we can find the optimum using Lagrange multipliers: it satisfies $p_i = \lambda 2^{-\ell_i} \log_e 2$ for some $\lambda$. Kraft's inequality forces the solution $2^{-\ell_i} = p_i$, and so $$E \geq \sum_i p_i (-\log_2 p_i).$$ The right-hand side is simply the entropy of the distribution.
This argument immediately gives a criterion for when Huffman's code reaches the entropy: this happens if $-\log_2 p_i$ is always an integer, that is, all probabilities are of the form $1/2^k$ (for integer $k$).