Question 1 of 5: Source coding

Question 1: 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 discrete memoryless source emitting one of six letters per symbol interval, with the probabilities listed below.

Find. (a) a Huffman code and its average length; (b) the source entropy; (c) a modification that narrows the gap between the two; (d) a defensible engineering verdict on a vendor's claim of halving the rate.

Approach. Build the code bottom-up by repeatedly merging the two least probable nodes, read the codewords off the resulting binary tree, then compare the average codeword length with the entropy and use the source coding theorem to test the vendor's claim.

1. Part (a) — confirm the probability model is complete. A Huffman construction is only meaningful on a normalised distribution, so add the six letter probabilities first: $0.05+0.11+0.17+0.28+0.23+0.16=1.00$. The model is complete and no residual "other" symbol has to be carried.
2. First merge: combine the two rarest letters. Ordering the alphabet by probability gives A (0.05), B (0.11), F (0.16), C (0.17), E (0.23), D (0.28). Huffman's rule assigns the two least likely symbols the two longest codewords, differing only in their last bit, so A and B become siblings under a node of weight $$w_{AB}=0.05+0.11=0.16$$
3. Second merge: resolve the tie at 0.16. The reduced list is now $\{AB, F\}$ at 0.16 each, then C (0.17), E (0.23), D (0.28). The two smallest are the tied pair, so they merge into $w_{FAB}=0.16+0.16=0.32$. The tie is genuinely arbitrary — either choice yields a different-looking tree with an identical set of codeword lengths, hence the same average length, which is why Huffman codes are "an" optimal code rather than "the" optimal code.
4. Third merge. The list is C (0.17), E (0.23), D (0.28), FAB (0.32); the two smallest are C and E, giving $w_{CE}=0.17+0.23=0.40$.
5. Fourth merge. Only D (0.28), FAB (0.32) and CE (0.40) remain, so D joins FAB: $w_{DFAB}=0.28+0.32=0.60$.
6. Close the tree. The last two nodes merge to the root, $0.40+0.60=1.00$, confirming the construction consumed every symbol exactly once.
7. Read the codewords root-to-leaf, labelling the upper branch 0 and the lower branch 1 at every node. Walking the tree in the figure gives the code tabulated below, and because every symbol sits at a leaf the code is automatically prefix-free (no codeword is the start of another), so it is instantaneously decodable with no comma or marker between symbols.

   Huffman code and Kraft check

   Letter	Probability $p_i$	Codeword	Length $l_i$	$2^{-l_i}$	$p_i l_i$
   D	0.28	10	2	0.2500	0.56
   E	0.23	01	2	0.2500	0.46
   C	0.17	00	2	0.2500	0.34
   F	0.16	110	3	0.1250	0.48
   B	0.11	1111	4	0.0625	0.44
   A	0.05	1110	4	0.0625	0.20
   Total	1.00	—	—	1.0000	2.48

   The Kraft sum equals exactly 1, the signature of a complete (unextendable) binary tree, which is a useful independent check that no branch was lost during the merges.
8. Average codeword length. Weighting each length by its probability, $$\bar{L}=\sum_{i} p_i l_i = 2(0.17)+2(0.23)+2(0.28)+3(0.16)+4(0.05)+4(0.11)$$ $$\boxed{\bar{L}=2.48\ \text{bits per source letter}}$$
9. Part (b) — entropy of the source. For a memoryless source the entropy is the probability-weighted average self-information, $H(X)=-\sum_i p_i \log_2 p_i$. Term by term:

   Entropy contributions

   $p_i$	0.05	0.11	0.17	0.28	0.23	0.16
   $-\log_2 p_i$	4.3219	3.1844	2.5564	1.8365	2.1203	2.6439
   $-p_i\log_2 p_i$	0.2161	0.3503	0.4346	0.5142	0.4877	0.4230

   Summing the bottom row, $$\boxed{H(X)=2.426\ \text{bits per source letter}}$$ This sits inside the bracket the source coding theorem guarantees for a Huffman code, $H \le \bar{L} \lt H+1$, which is the first thing to check for an arithmetic slip: $2.426 \le 2.48 \lt 3.426$.
10. Part (c) — quantify the gap before proposing a remedy. The code wastes $$\bar{L}-H = 2.48-2.426 = 0.054\ \text{bit per letter},$$ an efficiency of $\eta = H/\bar{L} = 2.426/2.48 = 97.8\%$. The waste is structural, not a fault in the construction: Huffman codes must spend a whole number of bits per letter, whereas the ideal length $-\log_2 p_i$ is generally fractional (letter D "deserves" 1.84 bits but is charged 2).
11. Part (c) — the three standard remedies. The most direct is to Huffman-code the n-th extension of the source, treating blocks of n letters as single super-symbols drawn from an alphabet of $6^n$. The rounding loss is then shared across n letters, so the per-letter rate obeys $$H \le \frac{\bar{L}_n}{n} \lt H + \frac{1}{n},$$ and coding pairs ($n=2$) already caps the loss at 0.5 bit per letter, with the achieved figure typically an order of magnitude below the present 0.054. The cost is a codebook of $6^n$ entries and a coding delay of n letters. The second remedy is arithmetic coding, which represents the whole message as one number in $[0,1)$ and therefore charges an effectively fractional length per letter, reaching within about 2 bits of $nH$ for the entire message. The third applies only if the letters are not truly independent: real sources have memory, and conditioning the code on the previous letter (or running a context model) lowers the entropy rate $H(X_k \mid X_{k-1})$ below the 2.426 bits computed from the marginals, so the target itself moves down.
12. Part (d) — test the vendor's claim against the entropy bound. Half the rate found in part (a) is $$\tfrac{1}{2}\bar{L} = \tfrac{1}{2}(2.48) = 1.24\ \text{bits per letter},$$ which is well below the entropy of 2.426 bits per letter. The source coding theorem states that no uniquely decodable lossless code can average fewer than $H(X)$ bits per symbol; a scheme claiming 1.24 bits per letter would compress a long message to roughly half the number of distinct messages that actually need distinct representations, so decoding could not be unique. $$\boxed{\text{Decline: } 1.24 \lt H = 2.426\ \text{bits/letter is impossible losslessly}}$$
13. State the caveats that would change the verdict, since a professional answer should say what the vendor could legitimately have meant. The claim becomes achievable only if (i) the compression is lossy, which is acceptable for imagery or audio but not for the arbitrary symbol stream described here; or (ii) the real source has strong memory, so that its true entropy rate is at or below 1.24 bits per letter even though the marginal entropy is 2.426 — in which case the honest comparison is against that rate, and the vendor should be asked to demonstrate it on the actual data. Absent either qualification, the offer violates a theorem and should be refused.