Question 2 of 5: Source Coding — Huffman Codes and Entropy

Question 2: Source Coding — Huffman Codes and Entropy (25 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. A memoryless eight-letter source with the alphabet and probability assignment below (the probabilities sum to 1.00, so the assignment is complete and no letter is missing).

Find. (a) a Huffman codeword set and its average length; (b) the source entropy in bits per symbol; (c) a reasoned buy/no-buy verdict on a vendor claiming to compress below that entropy.

Approach. Build the Huffman tree by repeatedly merging the two least-probable nodes, read the codewords off the root-to-leaf paths, compute the average length as $\sum p_i \ell_i$, compute $H = -\sum p_i\log_2 p_i$ independently, and compare the two against the source-coding theorem.

1. Part (a) — Merge the two least-probable nodes, repeatedly. Huffman's rule is greedy and bottom-up: the two rarest symbols must sit deepest in the tree, so they are combined into a single node of their summed probability and the process repeats on the reduced alphabet. Seven merges reduce eight leaves to one root:

   Merge	Nodes combined	Probabilities	New node
   1	H, E	0.01 + 0.07	0.08
   2	B, {H,E}	0.08 + 0.08	0.16
   3	G, C	0.10 + 0.11	0.21
   4	F, {B,H,E}	0.12 + 0.16	0.28
   5	{G,C}, A	0.21 + 0.25	0.46
   6	D, {F,B,H,E}	0.26 + 0.28	0.54
   7	{G,C,A}, {D,F,B,H,E}	0.46 + 0.54	1.00 (root)

   Ties are broken arbitrarily (merge 2 combines two nodes of equal probability 0.08); a different tie-break yields a different but equally optimal code with the same average length.
2. Read the codewords off the tree. Labelling the lower-probability branch of each merge 0 and the higher-probability branch 1, and reading from the root downwards:
   Figure 2.1 — The Huffman tree. Each internal node is annotated with the probability of the sub-tree beneath it; the codeword for a letter is the sequence of branch labels from the root to that leaf. The two rarest letters, H (0.01) and E (0.07), end up deepest at five bits; the two commonest, D (0.26) and A (0.25), take only two.
3. Tabulate the code and compute the average codeword length. With $\ell_i$ the length of the codeword for letter $i$, $$\bar{L} = \sum_{i} p_i \ell_i.$$

   Letter	$p_i$	Codeword	$\ell_i$	$p_i\ell_i$
   A	0.25	01	2	0.50
   B	0.08	1110	4	0.32
   C	0.11	001	3	0.33
   D	0.26	10	2	0.52
   E	0.07	11111	5	0.35
   F	0.12	110	3	0.36
   G	0.10	000	3	0.30
   H	0.01	11110	5	0.05

   Summing the last column, $$\boxed{\bar{L} = 2.73\ \text{bits/symbol}}$$ The code is prefix-free by construction — no codeword is the start of another, because every codeword ends at a leaf — so a received bit stream decodes uniquely without any separator. As a check, the lengths satisfy the Kraft equality $\sum 2^{-\ell_i} = 2^{-2}+2^{-4}+2^{-3}+2^{-2}+2^{-5}+2^{-3}+2^{-3}+2^{-5} = 1$, which every complete binary prefix code must.
4. Part (b) — Compute the source entropy. For a memoryless source, $$H(X) = -\sum_i p_i \log_2 p_i = \sum_i p_i \log_2\frac{1}{p_i}.$$ Term by term (bits): $0.5000$ (A), $0.2915$ (B), $0.3503$ (C), $0.5053$ (D), $0.2686$ (E), $0.3671$ (F), $0.3322$ (G), $0.0664$ (H). Adding, $$\boxed{H(X) = 2.681\ \text{bits/symbol}}$$ The Huffman code therefore runs at an efficiency of $\eta = H/\bar{L} = 2.681/2.73 = 98.2\%$, with a redundancy of only $\bar{L} - H = 0.049$ bits per symbol — comfortably inside the theorem's guarantee that $H \le \bar{L} < H + 1$.
5. Part (c) — Test the vendor's claim against the source-coding theorem. Shannon's source-coding theorem states that for a memoryless source no uniquely-decodable code can achieve an average length below the entropy: $\bar{L} \ge H(X)$, here 2.681 bits per symbol. A vendor offering lossless compression of this source below 2.681 bits/symbol on average is therefore promising something provably impossible, and the product should not be bought on that claim.

   Two qualifications are worth stating, because they are what separates a considered answer from a reflex one. First, the bound applies to lossless coding — a lossy scheme may go arbitrarily low, at a cost in fidelity, and that is a legitimate product provided the distortion is acceptable. Second, the bound is set by the entropy rate of the actual source, not by the first-order symbol statistics: if the real data stream has memory (correlation between successive letters), its entropy rate is strictly less than 2.681 bits/symbol, and a context-modelling or dictionary coder could beat 2.681 while remaining perfectly lossless. So the correct response to the vendor is a question, not a flat refusal: is the scheme lossless, and does it exploit inter-symbol dependence? If the answer is “lossless, memoryless, and below the entropy”, the claim is false.