22-Elec-B3 Digital Communications Systems · Undated paper
Question 2 of 5: Source Coding
Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Notes on this paper
Paper format. National Examinations, May 2019 — 16-Elec-B3 Digital Communications Systems. Closed book, 3 hours; one approved Casio or Sharp calculator. Five questions of 25 marks each; the cover page states that any four constitute a complete paper worth 100 marks, and that only the first four appearing in the answer book are marked. All five are solved here, because this set is a study resource rather than a sitting.
Reference texts. S. Haykin, Communication Systems, 5th ed. (Wiley) — noise, link budgets, digital detection; B. P. Lathi & Z. Ding, Modern Digital and Analog Communication Systems, 4th ed. (Oxford) — sampling, PCM, source and channel coding, spread spectrum; A. V. Oppenheim & A. S. Willsky, Signals and Systems, 2nd ed. (Pearson) — the sampling theorem and aliasing; J. G. Proakis & D. G. Manolakis, Digital Signal Processing, 4th ed. (Pearson) — quantization and A/D conversion. Canadian spectrum practice for the spread-spectrum question follows ISED Canada RSS-247 (digital transmission systems, frequency-hopping systems and licence-exempt local area network devices).
Source note. The tiles were reassembled from the PDF's own image objects, which recovers a clean full-resolution raster of all three pages. Where a printed phrase admits more than one engineering reading, the reading used is stated explicitly in a check callout.
Given. A memoryless source over the eight-letter alphabet {A, …, H} with the probability mass function below (the probabilities sum to 1.00, which is worth checking before any coding work begins).
Letter
A
B
C
D
E
F
G
H
Probability
0.02
0.13
0.24
0.21
0.07
0.18
0.10
0.05
Find. A Huffman code for the source, the source entropy in bits per symbol, the average length of the constructed code, and the general ordering between those last two quantities with a one-sentence justification.
Figure 2.1 — Huffman tree. Each merge joins the two smallest remaining probabilities; the code word for a letter is read off the branch labels from the root down to that leaf.
Approach. Build the Huffman tree bottom-up by repeatedly merging the two least likely symbols, read the code words off the completed tree, then compute the entropy and the average length and compare them against the source-coding theorem.
Part (a) — sort the alphabet and perform the merges. Huffman's algorithm is greedy: at every stage the two smallest probabilities in the working list are combined into one composite symbol, and the process repeats until a single symbol of probability 1 remains. Starting from the sorted list 0.02 (A), 0.05 (H), 0.07 (E), 0.10 (G), 0.13 (B), 0.18 (F), 0.21 (D), 0.24 (C), the seven merges are:
Merge
Combined
New probability
Working list afterwards
1
A + H
0.07
0.07, 0.07, 0.10, 0.13, 0.18, 0.21, 0.24
2
E + (AH)
0.14
0.10, 0.13, 0.14, 0.18, 0.21, 0.24
3
G + B
0.23
0.14, 0.18, 0.21, 0.23, 0.24
4
(EAH) + F
0.32
0.21, 0.23, 0.24, 0.32
5
D + (GB)
0.44
0.24, 0.32, 0.44
6
C + (EAHF)
0.56
0.44, 0.56
7
root
1.00
—
Read the code words off the tree. Labelling the upper branch of every node 0 and the lower branch 1, as drawn in Figure 2.1, gives
Letter
Probability
Code word
Length $\ell_i$
C
0.24
10
2
D
0.21
00
2
F
0.18
111
3
B
0.13
011
3
G
0.10
010
3
E
0.07
1100
4
H
0.05
11011
5
A
0.02
11010
5
No code word is a prefix of another, so the code is uniquely and instantaneously decodable. The Kraft sum confirms the tree is complete:
$$\sum_i 2^{-\ell_i} = 2\!\left(\tfrac{1}{4}\right) + 3\!\left(\tfrac{1}{8}\right) + \tfrac{1}{16} + 2\!\left(\tfrac{1}{32}\right) = 1 .$$
Note that the assignment is not unique — swapping the 0 and 1 labels at any node, or breaking a tie between equal probabilities the other way, yields a different code with exactly the same average length. Any such code is a correct answer.
Part (b) — compute the source entropy. For a memoryless source,
$$H(X) = -\sum_{i} p_i \log_2 p_i \quad \text{bits per symbol}.$$
Term by term:
$p_i$
0.02
0.13
0.24
0.21
0.07
0.18
0.10
0.05
$-p_i\log_2 p_i$
0.1129
0.3826
0.4941
0.4728
0.2686
0.4453
0.3322
0.2161
Summing the eight contributions,
$$\boxed{H(X) = 2.7246\ \text{bits/symbol}}$$
Part (c) — compute the average code length. Weighting each code-word length by the probability of the letter it encodes,
$$\bar{L} = \sum_i p_i \ell_i = (0.02)(5) + (0.13)(3) + (0.24)(2) + (0.21)(2) + (0.07)(4) + (0.18)(3) + (0.10)(3) + (0.05)(5),$$
which evaluates to $0.10 + 0.39 + 0.48 + 0.42 + 0.28 + 0.54 + 0.30 + 0.25$, so
$$\boxed{\bar{L} = 2.76\ \text{bits/symbol}}$$
Part (d) — compare, and say why. The average length is greater than or equal to the entropy, never less: the source-coding theorem states
$$H(X) \le \bar{L} < H(X) + 1 .$$
Here $2.7246 \le 2.76 < 3.7246$, so both bounds hold with room to spare. Equality is achieved only when every probability is a negative power of two, so that $\ell_i = -\log_2 p_i$ is an integer for every letter; this source is not dyadic (0.02 and 0.13 are not powers of one half), so the code must round some lengths up and $\bar{L}$ sits slightly above $H$. The gap is the coding redundancy,
$$\bar{L} - H(X) = 2.76 - 2.7246 = 0.0354\ \text{bits/symbol},$$
an efficiency of $H/\bar{L} = 98.7\%$. In one sentence: entropy is the theoretical floor on the average number of binary digits per symbol, and a Huffman code is the best integer-length prefix code, so it can approach that floor but can never go below it.
Final Results
Part
Quantity
Result
(a)
Huffman code
A 11010, B 011, C 10, D 00, E 1100, F 111, G 010, H 11011
