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

Question 3: 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.

The probabilities sum to $0.11 + 0.05 + 0.28 + 0.17 + 0.25 + 0.14 = 1.00$, so the description is complete and the source is memoryless.

Find. A Huffman code for the six letters and its average codeword length; the entropy of the source; a definition of a prefix code with a justification of whether Huffman codes qualify; and one genuine advantage and one genuine disadvantage of Huffman coding.

(a) Constructing the Huffman code (10 marks)

Approach. Repeatedly merge the two least probable symbols into a composite node until one node of probability 1 remains, then read the codewords off the resulting binary tree by labelling each branch 0 or 1.

1. Part (a) — order the symbols and merge the two smallest. Sorting by probability gives C (0.28), E (0.25), D (0.17), F (0.14), A (0.11), B (0.05). The two least likely are B and A, so they are merged into a node of probability $$P(\text{AB}) = 0.11 + 0.05 = 0.16 .$$ The list is now C 0.28, E 0.25, D 0.17, AB 0.16, F 0.14.
2. Part (a) — second merge. The two smallest are now F (0.14) and AB (0.16): $$P(\text{FAB}) = 0.14 + 0.16 = 0.30 ,$$ leaving FAB 0.30, C 0.28, E 0.25, D 0.17.
3. Part (a) — third merge. The two smallest are D (0.17) and E (0.25): $$P(\text{DE}) = 0.17 + 0.25 = 0.42 ,$$ leaving DE 0.42, FAB 0.30, C 0.28.
4. Part (a) — fourth merge. The two smallest are C (0.28) and FAB (0.30): $$P(\text{C-FAB}) = 0.28 + 0.30 = 0.58 ,$$ leaving DE 0.42 and C-FAB 0.58.
5. Part (a) — final merge and root. The last two nodes combine to $$0.42 + 0.58 = 1.00 ,$$ which closes the tree. Five merges were required, as expected for six symbols.
6. Part (a) — read the codewords off the tree. Labelling the upper branch of every node 0 and the lower branch 1 and tracing root to leaf gives the code below. (The assignment of 0 and 1 at each node is arbitrary, so many equally optimal codes exist; only the multiset of codeword lengths is determined.)

   Letter	Probability $p_i$	Codeword	Length $\ell_i$	$p_i \ell_i$
   D	0.17	00	2	0.34
   E	0.25	01	2	0.50
   C	0.28	10	2	0.56
   F	0.14	110	3	0.42
   A	0.11	1110	4	0.44
   B	0.05	1111	4	0.20

   Notice the ordering property that confirms the construction: the more probable a letter, the shorter its codeword.
7. Part (a) — compute the average codeword length and check the tree is complete. Summing the last column, $$\bar{L} = \sum_i p_i \ell_i = 0.34 + 0.50 + 0.56 + 0.42 + 0.44 + 0.20,$$ $$\boxed{\bar{L} = 2.46\ \text{bits/letter}}$$ As an independent check, the Kraft sum for these lengths is $$\sum_i 2^{-\ell_i} = 3(2^{-2}) + 2^{-3} + 2(2^{-4}) = 0.75 + 0.125 + 0.125 = 1.00 ,$$ and equality (rather than inequality) confirms the tree has no unused branches — the hallmark of an optimal prefix code.

(b) Entropy of the source (5 marks)

Approach. Evaluate $H = -\sum p_i \log_2 p_i$ term by term and compare with the average codeword length found in part (a).

1. Part (b) — evaluate the entropy sum. For a discrete memoryless source the entropy in bits per letter is $$H(X) = -\sum_{i} p_i \log_2 p_i .$$ Taking the six terms in turn:

   $p_i$	$-\log_2 p_i$	$-p_i\log_2 p_i$
   0.28	1.8365	0.5142
   0.25	2.0000	0.5000
   0.17	2.5564	0.4346
   0.14	2.8365	0.3971
   0.11	3.1844	0.3503
   0.05	4.3219	0.2161

   Summing the last column, $$\boxed{H(X) = 2.412\ \text{bits/letter}}$$
2. Part (b) — check the result against the source-coding theorem. Shannon’s source-coding theorem requires $$H(X) \le \bar{L} < H(X) + 1 ,$$ and indeed $2.412 \le 2.46 < 3.412$. The code’s efficiency and redundancy are $$\eta = \frac{H}{\bar{L}} = \frac{2.412}{2.46} = 98.06\,\% , \qquad \bar{L} - H = 0.048\ \text{bit/letter}.$$ Fixed-length coding of six letters would need $\lceil \log_2 6 \rceil = 3$ bits each, so the Huffman code saves 0.54 bit per letter, about 18 per cent of the transmitted volume.

(c) Prefix codes (5 marks)

A code is a prefix code (also called prefix-free, or an instantaneous code) when no codeword is a prefix of any other codeword — that is, no codeword can be obtained by truncating a different, longer codeword. In the code of part (a), for example, 110 is a codeword while 11 is not, and although 1110 and 1111 share the leading three bits neither is a prefix of the other because they have equal length and differ in the last bit. A quick check confirms the property holds for all thirty ordered pairs of codewords.

The practical importance of the property is that it makes the code uniquely and instantaneously decodable. A receiver reading a concatenated bit stream such as 10 01 1111 00 110 can accumulate bits until the accumulated string matches a codeword and emit that letter immediately, with no need to look ahead, no need for inter-symbol markers, and no ambiguity about where one codeword ends and the next begins. A non-prefix code can be uniquely decodable but may require unbounded look-ahead, and a code in which one codeword prefixes another may be ambiguous outright.

A Huffman code is always a prefix code. The reason is structural rather than coincidental: the construction places every source letter at a leaf of a binary tree, and a codeword is the sequence of branch labels on the path from the root to that leaf. For one codeword to prefix another, the first letter’s node would have to lie on the path to the second, meaning it would be an internal node with descendants — which no leaf is. Since merging always creates a new internal node above two existing nodes and never places a symbol above another symbol, the prefix-free property is guaranteed by construction. Equivalently, the Kraft equality $\sum 2^{-\ell_i} = 1$ verified in part (a) confirms that the codeword lengths correspond to a full binary tree with all symbols at leaves.

(d) One advantage and one disadvantage (5 marks)

Advantage — it is provably optimal, and instantaneously decodable. For a given set of symbol probabilities, no other uniquely decodable symbol-by-symbol code achieves a smaller average codeword length than Huffman’s: the greedy bottom-up merge is not a heuristic but an exact solution to the minimum-average-length problem over prefix codes. Here that optimum is 2.46 bits per letter, within 0.05 bit of the 2.412-bit entropy floor and 0.54 bit better than the 3-bit fixed-length alternative — a lossless reduction of roughly 18 per cent in stored or transmitted volume, obtained with a small lookup table and no arithmetic at run time. The prefix property further means decoding needs no synchronisation markers and adds no latency beyond one codeword.

Disadvantage — it needs the statistics in advance, and integer codeword lengths cost efficiency. The encoder and decoder must agree on the probability model before any data flows, so either the source statistics are known a priori or the table has to be measured and transmitted as overhead, and performance degrades whenever the real source drifts away from the assumed distribution. Because codeword lengths are whole numbers of bits, a Huffman code can only approach the entropy in steps: the residual redundancy here is 0.048 bit per letter, and in the pathological case of a highly skewed binary source the overhead approaches a full bit per symbol, which arithmetic coding avoids by allowing fractional-bit effective lengths. Two further practical weaknesses are worth stating: because the code is variable-length, a single channel bit error can shift the decoder’s codeword boundaries and corrupt an indefinite run of following letters until it accidentally resynchronises; and because the code treats letters independently it captures none of the correlation in a source with memory, where modelling the dependence — by coding blocks of letters, or by predictive or dictionary methods such as Lempel–Ziv — recovers far more than optimising the symbol code ever can.