---
title: "Coding efficiency: binary, Shannon-Fano and Huffman"
subject: "Communication Systems"
chapter: 6
key: "semester_6/communication_systems:coding-efficiency-binary-sf-huffman"
source: https://www.bctengineer.com/q/semester_6/communication_systems/coding-efficiency-binary-sf-huffman
site: BCT Engineering
---

# Coding efficiency: binary, Shannon-Fano and Huffman

Communication Systems · Chapter 6: Baseband Digital Data Transmission

- Asked in: 2076 Asoj (CS II), 2+2+2 marks
- Video: [1 Shannon Fano Encoding (Algorithm, Procedure & Example) Explained in Digital Communication](https://www.youtube.com/watch?v=g2UlDNamG84) — Engineering Funda
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_6/communication_systems/coding-efficiency-binary-sf-huffman
- Whole chapter: https://www.bctengineer.com/md/semester_6/communication_systems/chapter-6

## Question

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

## 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.

## Answer

**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.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. How many bits per symbol does binary (fixed-length) coding need for 5 symbols?
   A. 2
   B. 3
   C. 4
   D. 5
   Answer: B. ceil(log2 5) = 3, giving efficiency 2.0087/3 = 66.96%. (Key point: Fixed-length code)

2. Coding efficiency is computed as:
   A. L / H
   B. H / L
   C. H x L
   D. 1 - H
   Answer: B. eta = H / L-bar, with L-bar the average code length. (Key point: Efficiency formula)

3. For {0.4, 0.3, 0.15, 0.1, 0.05}, why is the first split {0.4} vs the rest?
   A. It gives 0.4 vs 0.6, closer to equal than 0.7 vs 0.3
   B. Because 0.4 is largest
   C. Because the rest have four symbols
   D. Because the total is 1
   Answer: A. Shannon-Fano chooses the split whose group probabilities are most nearly equal. (Key point: Shannon-Fano first split)

4. What are the efficiencies for fixed length, Shannon-Fano and Huffman?
   A. 66.96%, 97.99%, 97.99%
   B. 66.96%, 66.96%, 97.99%
   C. 97.99%, 97.99%, 100%
   D. 100%, 97.99%, 97.99%
   Answer: A. SF and Huffman both give lengths 1,2,3,4,4 so L = 2.05 and eta = 2.0087/2.05 = 97.99%. (Key point: Result)

## Related in Communication Systems

- [Importance of source coding; fixed vs Shannon-Fano (five symbols)](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Asource-coding-fixed-sf-five) — Communication Systems, chapter 6
- [Importance of source coding; Shannon-Fano vs BCD (four symbols)](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Asource-coding-sf-bcd-four) — Communication Systems, chapter 6
- [Importance of source coding; Shannon-Fano vs fixed length (seven symbols)](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Asource-coding-sf-fixed-seven) — Communication Systems, chapter 6
- [Types of noise; Shannon-Fano and Huffman coding efficiency](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Anoise-types-shannon-fano-huffman) — Communication Systems, chapter 6
- [Huffman and Shannon-Fano coding of A0–A4](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Ahuffman-sf-a0-a4-compare) — Communication Systems, chapter 6
- [Source coding; Huffman for five symbols (0.3, 0.25, 0.2, 0.15, 0.1)](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Asource-coding-huffman-five-s0) — Communication Systems, chapter 6

## Related in other subjects

- [Shannon-Fano code for eight symbols](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Ashannon-fano-eight-symbols) — Data Communication, chapter 8
- [Shannon-Fano code for six symbols](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Ashannon-fano-six-symbols) — Data Communication, chapter 8
- [Huffman code for symbols A0 to A4](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Ahuffman-a0-a4) — Data Communication, chapter 8
- [Huffman code for symbols A to E (0.4, 0.3, ...)](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Ahuffman-table-abcde) — Data Communication, chapter 8