Calculate the entropy of a source with 8 characters (A-H) where $P(A) = P(B) = \frac{1}{4}$, $P(C) = P(D) = \frac{1}{8}$, $P(E) = P(F) = P(G) = P(H) = \frac{1}{16}$. What is the redundancy?

Question

Accepted Answer

$H(X) = 2.75$ bits, which is less than $H_0(X) = 3$ bits, giving $R(X) = 0.25$ bits and $r(X) \approx 8.3\%$.
Step-by-step calculation:
$$H(X) = -\sum_{i=1}^{8} P(x_i) \cdot \log_2(P(x_i))$$
$$= -\left[2 \cdot \frac{1}{4}\log_2\!\left(\frac{1}{4}ight) + 2 \cdot \frac{1}{8}\log_2\!\left(\frac{1}{8}ight) + 4 \cdot \frac{1}{16}\log_2\!\left(\frac{1}{16}ight)ight]$$
$$= -\left[\frac{1}{2}(-2) + \frac{1}{4}(-3) + \frac{1}{4}(-4)ight]$$
$$= -\left[-1 - \frac{3}{4} - 1ight] = 2.75 	ext{ bits}$$
Maximum entropy: $H_0(X) = \log_2(8) = 3$ bits
Redundancy:
$$R(X) = 3 - 2.75 = 0.25 	ext{ bits}$$
$$r(X) = \frac{0.25}{3} = \frac{1}{12} \approx 8.3\%$$
Insight: Even though we still have 8 characters, the non-uniform distribution reduces entropy by 0.25 bits (from 3 to 2.75). An optimal compressor could encode 1 million of these characters in 2.75 million bits instead of 3 million — saving 8.3%.