Source coding: 22-Elec-B3 Digital Communications Systems, December 2015, Q2

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 six-letter source whose letter probabilities sum to unity.

Given data
Letter	A	B	C	D	E	F
$\Pr(\cdot)$	0.11	0.05	0.28	0.17	0.25	0.14

Find. (a) an optimal prefix-free binary code and its average length, (b) the entropy of the source, and (c) a Shannon–Fano–Elias code, with its length compared against both the entropy and the Huffman result.

Approach. Build the Huffman code by repeatedly merging the two least likely symbols, read the codewords off the resulting tree and confirm optimality with the Kraft equality; compute the entropy directly from the definition; then construct the Shannon–Fano–Elias code from the cumulative distribution and compare the three lengths.

Part (a) — merge the two least likely symbols repeatedly. Huffman's algorithm builds the tree from the leaves upward, always combining the two smallest remaining probabilities:

Huffman merges
Step	Combined	New node
1	B (0.05) with A (0.11)	0.16
2	F (0.14) with 0.16	0.30
3	D (0.17) with E (0.25)	0.42
4	C (0.28) with 0.30	0.58
5	0.42 with 0.58	1.00 (root)

Notice that step 2 merges F with the node created in step 1 rather than with D, because 0.16 is smaller than 0.17 — the classic place to slip. Labelling the lower-probability branch of each merge 0 and the other 1 gives the tree drawn below, and the codewords are read from root to leaf.

Figure 2.1 — the Huffman tree. Each internal node is labelled with the combined probability produced by the corresponding merge, so the tree and the merge table are the same construction seen two ways.

Read off the codewords and confirm the code is complete. The assignment is D = 00, E = 01, C = 10, F = 110, B = 1110, A = 1111. No codeword is a prefix of another, and the Kraft sum $$\sum_{i} 2^{-l_{i}} = 3(2^{-2}) + 2^{-3} + 2(2^{-4}) = 1,$$ holds with equality, which is exactly the statement that the binary tree has no unused branches — a necessary condition for optimality.
Average codeword length. Weighting each length by its probability, $$\bar{L} = \sum_{i} p_{i} l_{i} = 2(0.28+0.25+0.17) + 3(0.14) + 4(0.11+0.05),$$ so that $$\boxed{\bar{L} = 2.46\ \text{bits/symbol}}.$$ Any other prefix-free code for this source is at least this long; a fixed 3-bit code, by contrast, would need 3 bits per symbol.
Part (b) — entropy of the source. The entropy is the probability-weighted average of the self-information $-\log_{2}p_{i}$: $$H(X) = -\sum_{i} p_{i}\log_{2}p_{i} = \boxed{2.412\ \text{bits/symbol}}.$$ The individual terms are tabulated below, and they explain the code lengths: C and E carry under 2.1 bits each and get 2-bit codewords, while B carries 4.32 bits and gets 4.

Self-information of each letter, $-\log_{2}p_{i}$ (bits)
Letter	A	B	C	D	E	F
$-\log_{2}p_{i}$	3.184	4.322	1.837	2.556	2.000	2.837

How close to the bound is the Huffman code? The source-coding theorem sandwiches the optimal length, $H(X)\le\bar{L}\lt H(X)+1$, and here $2.412\le 2.46\lt 3.412$. The efficiency is $$\eta = \frac{H(X)}{\bar{L}} = \frac{2.412}{2.46} = 98.06\%,$$ a redundancy of only 0.048 bit/symbol. Reaching the entropy exactly would require the probabilities to be negative powers of two, which they are not.
Part (c) — set up the Shannon–Fano–Elias construction. Fix the letters in the order given, form the cumulative distribution $F_{i}=\sum_{k\lt i}p_{k}$, and take the midpoint of each interval, $$\bar{F}_{i} = F_{i} + \tfrac{1}{2}p_{i}.$$ The codeword for letter $i$ is the binary expansion of $\bar{F}_{i}$ truncated to $$l_{i} = \left\lceil \log_{2}\frac{1}{p_{i}} \right\rceil + 1 \ \text{bits}.$$ The $+1$ is what makes the code prefix-free: it guarantees the interval of width $2^{-l_{i}}$ around the truncated value stays inside letter $i$'s own segment of the unit interval.

Figure 2.2 — the unit interval partitioned in the given letter order. The red tick on each segment is its midpoint, and the blue string below is that midpoint's binary expansion truncated to the required length.

Shannon–Fano–Elias construction
Letter	$p_{i}$	$F_{i}$	$\bar{F}_{i}$	$\lceil\log_{2}(1/p_{i})\rceil$	$l_{i}$	Codeword
A	0.11	0.000	0.055	4	5	00001
B	0.05	0.110	0.135	5	6	001000
C	0.28	0.160	0.300	2	3	010
D	0.17	0.440	0.525	3	4	1000
E	0.25	0.610	0.735	2	3	101
F	0.14	0.860	0.930	3	4	1110

As a worked instance, letter D has $\bar{F}=0.525$ and $l=\lceil\log_{2}(1/0.17)\rceil+1 = \lceil 2.556\rceil+1 = 4$. Doubling repeatedly, $0.525\to1.05$ (bit 1, keep 0.05), $0.05\to0.10$ (bit 0), $0.10\to0.20$ (bit 0), $0.20\to0.40$ (bit 0), so D is 1000.

Collect the code and check the prefix property. The resulting code is $$\boxed{\text{A}=00001,\ \text{B}=001000,\ \text{C}=010,\ \text{D}=1000,\ \text{E}=101,\ \text{F}=1110 }$$ and no codeword prefixes another, as the construction guarantees. The Kraft sum is only $0.4219$, well short of unity: unlike the Huffman tree this one has many unused branches, which is precisely where the extra length comes from.
Average length and the comparison. Weighting the lengths, $$\bar{L}_{SFE} = 5(0.11)+6(0.05)+3(0.28)+4(0.17)+3(0.25)+4(0.14) = \boxed{3.68\ \text{bits/symbol}}.$$ This obeys the Shannon–Fano–Elias bound $H(X)\le\bar{L}_{SFE}\lt H(X)+2$, i.e. $2.412\le 3.68\lt 4.412$, but it is 1.22 bit/symbol worse than the Huffman code and only 65.55 % efficient. The construction is valuable for the theory it supports — it proves a prefix code within 2 bits of the entropy always exists and it generalises directly to arithmetic coding — not for its compression.

Final results
Quantity	Result
(a) Huffman code	D = 00, E = 01, C = 10, F = 110, B = 1110, A = 1111
Huffman average length	2.46 bits/symbol
(b) Entropy $H(X)$	2.412 bits/symbol
Huffman efficiency and redundancy	98.06 %; 0.048 bit/symbol
(c) Shannon–Fano–Elias code	A = 00001, B = 001000, C = 010, D = 1000, E = 101, F = 1110
Shannon–Fano–Elias average length	3.68 bits/symbol (efficiency 65.55 %)
Bounds satisfied	$2.412 \le 2.46 \lt 3.412$ and $2.412 \le 3.68 \lt 4.412$

Topic. Entropy as the limit of lossless coding, and the two constructive codes that approach it.

Key relations. Entropy $H(X)=-\sum p_{i}\log_{2}p_{i}$; Kraft inequality $\sum 2^{-l_{i}}\le 1$, with equality for a complete tree; source-coding theorem $H(X)\le\bar{L}_{opt}\lt H(X)+1$; Shannon–Fano–Elias lengths $l_{i}=\lceil\log_{2}(1/p_{i})\rceil+1$ with $H(X)\le\bar{L}_{SFE}\lt H(X)+2$; efficiency $\eta=H(X)/\bar{L}$.

Why this works. Entropy measures the average surprise per symbol, and the Kraft inequality says how much codeword length a prefix-free tree can afford to hand out; putting the two together shows no lossless code can beat the entropy on average. Huffman's bottom-up merge is optimal because at every stage the two least likely symbols can be placed deepest without loss of generality, so the greedy choice never forecloses a better tree. The Shannon–Fano–Elias code instead addresses each symbol by its position in the cumulative distribution, which is why it needs no tree at all and why it extends to coding whole sequences — the idea behind arithmetic coding, where the per-symbol overhead is amortised away.

Common pitfall. The commonest slip in the Huffman merge is combining the wrong pair once a merged node becomes smaller than an unmerged symbol, as happens at step 2 here. In the Shannon–Fano–Elias construction the commonest error is dropping the $+1$ from the length rule, or truncating $F_{i}$ instead of the midpoint $\bar{F}_{i}$; either destroys the prefix property. It is also wrong to expect the two codes to agree — only Huffman is optimal, and a 1.22 bit/symbol gap here is normal, not a computational error.

Source. Cover and Thomas, Elements of Information Theory, 2nd ed., §5.4 (Kraft inequality), §5.6 (Huffman codes) and §5.9 (Shannon–Fano–Elias coding); Proakis and Salehi, Communication Systems Engineering, 2nd ed., §6.2.

Question 2 of 5: Source coding

Question 2: Source coding (25 marks)