2072 Chaitra (CS II) · 5 marks

Information rate and coding efficiency: BCD vs Huffman

Short answer

Entropy H = 2.0572 bits/symbol. Information rate = 14400 × 2.0572 ≈ 29.62 kbps. BCD uses 4 bits per symbol, efficiency = 2.0572/4 = 51.43%. Huffman coding yields average length 2.10 bits/symbol, efficiency = 2.0572/2.10 = 97.96%.

If a source emits symbols Xi = {A, B, C, D, E, F} in the BCD format with probabilities P(Xi) = {0.3, 0.1, 0.02, 0.15, 0.4, 0.03} at a rate Rs = 14.4 kbaud, find the following: i) Information rate ii) Coding efficiency both with BCD and Huffman coded signal

Given: six symbols A–F with $P = \{0.3, 0.1, 0.02, 0.15, 0.4, 0.03\}$ (sum = 1); symbol rate $r_s = 14.4$ kbaud = 14 400 symbols/s; BCD format = 4 bits per symbol.

Entropy:

Symbol	$p_i$	$\log_2(1/p_i)$	$p_i\log_2(1/p_i)$
A	0.3	1.7370	0.5211
B	0.1	3.3219	0.3322
C	0.02	5.6439	0.1129
D	0.15	2.7370	0.4105
E	0.4	1.3219	0.5288
F	0.03	5.0589	0.1518
Total	1		2.0572

H = 2.0572\ \text{bits/symbol}

i) Information rate

R = r_s H = 14\ 400 \times 2.0572 = 29\ 624.29\ \text{bits/s} \approx 29.62\ \text{kbps}

ii) Coding efficiency

BCD coding: each symbol uses 4 bits, $\bar L = 4$ .

\eta_{BCD} = \frac{2.0572}{4} = 51.43\%

(The line bit rate would be $14\ 400 \times 4 = 57.6$ kbps.)

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.03, 0.02	0.03 + 0.02 = 0.05
2	0.4, 0.3, 0.15, 0.1, 0.05	0.1 + 0.05 = 0.15
3	0.4, 0.3, 0.15, 0.15	0.15 + 0.15 = 0.3
4	0.4, 0.3, 0.3	0.3 + 0.3 = 0.6
5	0.6, 0.4	0.6 + 0.4 = 1

Symbol	$p_i$	Huffman code	$l_i$
E	0.4	1	1
A	0.3	01	2
D	0.15	001	3
B	0.1	0000	4
F	0.03	00010	5
C	0.02	00011	5

\begin{aligned} \bar L_H &= 0.4(1)+0.3(2)+0.15(3)+0.1(4)+0.03(5)+0.02(5) \\ &= 0.4+0.6+0.45+0.4+0.15+0.1 = 2.10\ \text{bits/symbol} \\ \eta_H &= \frac{2.0572}{2.10} = 97.96\% \end{aligned}

Bit rate with Huffman coding: $14\ 400 \times 2.1 = 30.24$ kbps.

Answer: $R \approx 29.62$ kbps; efficiency with BCD = 51.43 %, with Huffman = 97.96 %.

✓ Answer checked by Claude Opus 5.5 (high effort)

Importance of source coding; Huffman for eight symbols at 1000 symbols/s · Communication Systems, chapter 6
Importance of source coding; Shannon-Fano vs BCD (four symbols) · Communication Systems, chapter 6
Source vs channel coding; Huffman for five 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; Shannon-Fano vs fixed length (seven symbols) · Communication Systems, chapter 6
Importance of source coding; fixed vs Shannon-Fano (five symbols) · Communication Systems, chapter 6
Huffman code for symbols A to E · Multimedia System, chapter 5
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
Huffman code for five symbols (0.2, 0.35, ...) · Data Communication, chapter 8

All Communication Systems chapter 6 questions →

Information rate and coding efficiency: BCD vs Huffman

i) Information rate

ii) Coding efficiency

Related questions