For {0.4, 0.3, 0.15, 0.1, 0.05}, why is the first split {0.4} vs the rest?

It gives 0.4 vs 0.6, closer to equal than 0.7 vs 0.3

Because the rest have four symbols

2076 Asoj (CS II) · 2+2+2 marks

Coding efficiency: binary, Shannon-Fano and Huffman

Short answer

Entropy H = 2.0087 bits/symbol. Fixed-length (3 bits) efficiency is 66.96%. Shannon-Fano and Huffman both yield average length 2.05 bits/symbol, giving 97.99% efficiency.

Compute coding efficiency of a source with symbols {A₀, A₁, A₂, A₃, A₄} with corresponding probabilities {0.4, 0.3, 0.15, 0.1, 0.05} using (i) Binary coding (ii) Shannon-Fano Coding (iii) Binary Huffman Coding

Entropy of the source:

Symbol	$p_i$	$\log_2(1/p_i)$	$p_i\log_2(1/p_i)$
A0	0.4	1.3219	0.5288
A1	0.3	1.7370	0.5211
A2	0.15	2.7370	0.4105
A3	0.1	3.3219	0.3322
A4	0.05	4.3219	0.2161
Total	1		2.0087

H = \sum p_i\log_2\frac{1}{p_i} = 2.0087\ \text{bits/symbol}

Efficiency is $\eta = H/\bar L$ in each case.

(i) Binary (fixed-length) coding

Five symbols need $\lceil\log_2 5\rceil = 3$ bits each (000, 001, 010, 011, 100), so $\bar L = 3$ .

\eta = \frac{2.0087}{3} = 66.96\%

(ii) Shannon–Fano coding

First split: {0.4} vs {0.3, 0.15, 0.1, 0.05} (0.4 vs 0.6; the other split 0.7 vs 0.3 is worse).

Symbol	$p_i$	Step 1	Step 2	Step 3	Step 4	Code	$l_i$
A0	0.4	0				0	1
A1	0.3	1	0			10	2
A2	0.15	1	1	0		110	3
A3	0.1	1	1	1	0	1110	4
A4	0.05	1	1	1	1	1111	4

\begin{aligned} \bar L &= 0.4(1)+0.3(2)+0.15(3)+0.1(4)+0.05(4) = 2.05\ \text{bits/symbol} \\ \eta &= \frac{2.0087}{2.05} = 97.99\% \end{aligned}

(iii) Binary Huffman coding

Reduction (sum of two lowest moved up as high as possible):

Stage	Probabilities (descending)	Combined
1	0.4, 0.3, 0.15, 0.1, 0.05	0.1 + 0.05 = 0.15
2	0.4, 0.3, 0.15, 0.15	0.15 + 0.15 = 0.3
3	0.4, 0.3, 0.3	0.3 + 0.3 = 0.6
4	0.6, 0.4	0.6 + 0.4 = 1

Symbol	$p_i$	Huffman code	$l_i$
A0	0.4	1	1
A1	0.3	01	2
A2	0.15	001	3
A3	0.1	0000	4
A4	0.05	0001	4

\begin{aligned} \bar L &= 0.4(1)+0.3(2)+0.15(3)+0.1(4)+0.05(4) = 2.05\ \text{bits/symbol} \\ \eta &= \frac{2.0087}{2.05} = 97.99\% \end{aligned}

Coding	$\bar L$	Efficiency
Binary (fixed)	3	66.96 %
Shannon–Fano	2.05	97.99 %
Huffman	2.05	97.99 %

Answer: 66.96 %, 97.99 % and 97.99 % respectively.

✓ Answer checked by Claude Opus 5.5 (high effort)

Importance of source coding; fixed vs Shannon-Fano (five symbols) · Communication Systems, chapter 6
Importance of source coding; Shannon-Fano vs BCD (four symbols) · Communication Systems, chapter 6
Importance of source coding; Shannon-Fano vs fixed length (seven symbols) · Communication Systems, chapter 6
Types of noise; Shannon-Fano and Huffman coding efficiency · Communication Systems, chapter 6
Huffman and Shannon-Fano coding of A0–A4 · Communication Systems, chapter 6
Source coding; Huffman for five symbols (0.3, 0.25, 0.2, 0.15, 0.1) · Communication Systems, chapter 6
Shannon-Fano code for eight symbols · Data Communication, chapter 8
Shannon-Fano code for six symbols · Data Communication, chapter 8
Huffman code for symbols A0 to A4 · Data Communication, chapter 8
Huffman code for symbols A to E (0.4, 0.3, ...) · Data Communication, chapter 8

All Communication Systems chapter 6 questions →

Coding efficiency: binary, Shannon-Fano and Huffman

(i) Binary (fixed-length) coding

(ii) Shannon–Fano coding

(iii) Binary Huffman coding

Related questions