2081 Baisakh (CS II) · 4 marks

Huffman code for five-symbol DMS vs fixed length

Short answer

Huffman codes: x1: 1, x2: 000, x3: 001, x4: 010, x5: 011. Average length L = 2.20 bits/symbol, entropy H = 2.1498 bits/symbol. Efficiency η = H/L = 97.72%. Fixed-length (3 bits) efficiency is 71.66%; Huffman saves 0.8 bits/symbol.

A DMS has five symbols with probability of p(x₁) = 0.4, p(x₂) = 0.19, p(x₃) = 0.16, p(x₄) = 0.15 and p(x₅) = 0.1. Construct the Huffman code for X and calculate its efficiency and compare with fixed length coding.

Huffman code construction

Arrange the symbols by probability and repeatedly combine the two smallest. In each merge, the first group gets bit 0 and the second gets bit 1.

$x_4$ (0.15) + $x_5$ (0.10) → 0.25
$x_2$ (0.19) + $x_3$ (0.16) → 0.35
{x2,x3} (0.35) + {x4,x5} (0.25) → 0.60
{x2..x5} (0.60) + $x_1$ (0.40) → 1.00

              (1.00)
           0 /      \ 1
        (0.60)      x1 (0.40)
       0/    \1
   (0.35)    (0.25)
   0/  \1    0/  \1
  x2   x3   x4   x5

Symbol	$p_i$	Code	$l_i$	$p_i l_i$
$x_1$	0.40	1	1	0.40
$x_2$	0.19	000	3	0.57
$x_3$	0.16	001	3	0.48
$x_4$	0.15	010	3	0.45
$x_5$	0.10	011	3	0.30

Efficiency

\begin{aligned} \bar L &= \sum p_i l_i = 0.40 + 0.57 + 0.48 + 0.45 + 0.30 = 2.20\ \text{bits/symbol} \\ H &= -\sum p_i \log_2 p_i \\ &= 0.4(1.3219) + 0.19(2.3959) + 0.16(2.6439) \\ &\quad + 0.15(2.7370) + 0.1(3.3219) \\ &= 2.1498\ \text{bits/symbol} \\ \eta &= \frac{H}{\bar L} = \frac{2.1498}{2.20} = 0.9772 = 97.72\% \end{aligned}

Comparison with fixed-length coding

Five symbols need $\lceil \log_2 5 \rceil = 3$ bits each:

\eta_{fixed} = \frac{H}{3} = \frac{2.1498}{3} = 0.7166 = 71.66\%

Code	Avg. length	Efficiency
Fixed length	3 bits	71.66%
Huffman	2.20 bits	97.72%

Huffman coding saves $3 - 2.2 = 0.8$ bits/symbol (about 26.7%). Its efficiency is close to the entropy limit.

✓ Answer checked by Claude Opus 5.5 (high effort)

Source vs channel coding; Huffman for five symbols · Communication Systems, chapter 6
Importance of source coding; Shannon-Fano vs fixed length (seven symbols) · Communication Systems, chapter 6
Source coding; Huffman for five symbols (0.3, 0.25, 0.2, 0.15, 0.1) · Communication Systems, chapter 6
Importance of source coding; fixed vs Shannon-Fano (five symbols) · Communication Systems, chapter 6
Variable length coding; entropy and fixed code efficiency · Communication Systems, chapter 6
Importance of source coding; Huffman for eight symbols at 1000 symbols/s · Communication Systems, chapter 6
Huffman code for five symbols (0.2, 0.35, ...) · Data Communication, chapter 8
Huffman code for symbols A to E (0.4, 0.3, ...) · Data Communication, chapter 8
Source coding; fixed vs variable length codes · Data Communication, chapter 8
Huffman code for symbols A to E · Multimedia System, chapter 5

All Communication Systems chapter 6 questions →

Huffman code for five-symbol DMS vs fixed length

Huffman code construction

Efficiency

Comparison with fixed-length coding

Related questions