Entropy and Huffman coding

Question

A source emits the four letters $a,b,c,d$ with probabilities $1/2,\ 1/4,\ 1/8,\ 1/8$. Compute the entropy and compare it with the code $a=0,\ b=10,\ c=110,\ d=111$: the mean length is $1{,}75$ bits; it coincides with $H$ (optimal Huffman code).

Solution

Entropy: $H = -\tfrac12\log_2\tfrac12 - \tfrac14\log_2\tfrac14 - \tfrac18\log_2\tfrac18 - \tfrac18\log_2\tfrac18.$ With $\log_2\tfrac12=-1$, $\log_2\tfrac14=-2$, $\log_2\tfrac18=-3$: $H = \tfrac12\cdot 1 + \tfrac14\cdot 2 + \tfrac18\cdot 3 + \tfrac18\cdot 3 = 0{,}5 + 0{,}5 + 0{,}375 + 0{,}375 = \boxed{1{,}75 \text{ bit}}.$ Mean code length (bits per letter $\times$ probability): $\bar\ell = \tfrac12\cdot 1 + \tfrac14\cdot 2 + \tfrac18\cdot 3 + \tfrac18\cdot 3 = 1{,}75 \text{ bit}.$ The two values coincide: $\bar\ell = H$. When the probabilities are powers of $1/2$, the Huffman code reaches exactly the Shannon limit — it is impossible to compress any further.

Links

Topics: Probability distributions
Concepts: Entropy
Skills: Computing
People: Shannon
Exercise type: Expression evaluation