Question 2 of 5: Source Coding

Question 2: Source Coding (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 source over the eight-letter alphabet $\{A,\dots,H\}$ with

The probabilities sum to 1.00, as they must.

Find. (a) a Huffman codebook and its average length; (b) the source entropy; (c) a reasoned judgement on a vendor's claim to compress below that entropy.

Approach. Build the code bottom-up by repeatedly merging the two least probable symbols — this is Huffman's algorithm and it is provably optimal among prefix-free codes — then read the codewords off the tree, weight the lengths by probability to get $\bar{L}$, compute the entropy $H(X) = -\sum p_i\log_2 p_i$ independently, and compare the two against the source coding theorem.

1. Part (a) — Sort the alphabet by probability. In descending order: A (0.29), D (0.25), F (0.12), C (0.11), G (0.10), E (0.08), B (0.04), H (0.01). Huffman's algorithm only ever needs the two smallest entries of the current list, so keeping the list sorted makes each merge a constant-time step.
2. Merge the two least probable nodes, repeatedly. Each merge creates a parent whose probability is the sum of its children; the parent re-enters the list and the process repeats until one node of probability 1.00 remains. Seven merges are needed for eight letters:

   Merge	Nodes combined	New node	Remaining list (probabilities)
   1	H (0.01) + B (0.04)	0.05	0.29, 0.25, 0.12, 0.11, 0.10, 0.08, 0.05
   2	0.05 + E (0.08)	0.13	0.29, 0.25, 0.13, 0.12, 0.11, 0.10
   3	G (0.10) + C (0.11)	0.21	0.29, 0.25, 0.21, 0.13, 0.12
   4	F (0.12) + 0.13	0.25	0.29, 0.25, 0.25, 0.21
   5	0.21 + D (0.25)	0.46	0.46, 0.29, 0.25
   6	0.25 + A (0.29)	0.54	0.54, 0.46
   7	0.46 + 0.54	1.00	root

   Ties (merge 4 and merge 5 both face two nodes of equal weight) may be broken either way; a different choice yields a different codebook with the same average length, so any consistent convention is acceptable.
3. Read the codewords off the tree. Labelling the lower-probability branch of every merge ‘0’ and the other ‘1’, and walking root-to-leaf:

   Letter	$p_i$	Codeword	$\ell_i$	$p_i\ell_i$
   A	0.29	11	2	0.58
   D	0.25	01	2	0.50
   F	0.12	100	3	0.36
   C	0.11	001	3	0.33
   G	0.10	000	3	0.30
   E	0.08	1011	4	0.32
   B	0.04	10101	5	0.20
   H	0.01	10100	5	0.05

   No codeword is a prefix of another, so the stream decodes uniquely without markers between symbols; the Kraft sum $\sum 2^{-\ell_i}$ equals exactly 1, confirming the tree is complete.
4. Compute the average codeword length. Summing the last column, $$\bar{L} = \sum_i p_i \ell_i = 0.58+0.50+0.36+0.33+0.30+0.32+0.20+0.05$$ $$\boxed{\bar{L} = 2.64\ \text{bits/letter}}$$ A fixed-length code over eight letters would need $\log_2 8 = 3$ bits each, so the Huffman code saves 12% on average.
5. Part (b) — Compute the entropy. For a memoryless source, $H(X) = -\sum_i p_i\log_2 p_i$; term by term (bits):

   Letter	A	B	C	D	E	F	G	H
   $-p_i\log_2 p_i$	0.5179	0.1858	0.3503	0.5000	0.2915	0.3671	0.3322	0.0664

   Adding these, $$\boxed{H(X) = 2.6112\ \text{bits/letter}}$$
6. Check the result against the source coding theorem. The theorem guarantees $H(X) \le \bar{L} < H(X) + 1$, and here $2.6112 \le 2.64 < 3.6112$, so the code is admissible. Its efficiency is $\eta = H/\bar{L} = 2.6112/2.64 = 98.9\%$ and its redundancy is only 0.029 bits per letter — about as close to the bound as a symbol-by-symbol code can come on this distribution.

Part (c) — would you buy the vendor's product? No, not as described. Shannon's source coding theorem makes the entropy of 2.611 bits per letter a hard lower bound on the average rate of any uniquely decodable lossless code for this source, so a vendor promising a smaller average rate on the same memoryless statistics is claiming something provably impossible. There are only three honest ways the claim could be true, and each is a different product from the one advertised: the scheme is lossy, so it is not reproducing the letters exactly; the real source has memory or context that the given single-letter probabilities do not capture, in which case the relevant bound is the lower entropy rate of the true source rather than 2.611 bits per letter; or the quoted figure is a best case on favourable data rather than an average. The right response is therefore to ask which of these applies and to demand a rate measured over representative traffic, rather than to reject the vendor outright — a context-modelling coder beating 2.611 bits per letter on real text is entirely plausible and would simply mean the memoryless model was the wrong yardstick.