---
title: "Huffman and Shannon-Fano coding of A0–A4"
subject: "Communication Systems"
chapter: 6
key: "semester_6/communication_systems:huffman-sf-a0-a4-compare"
source: https://www.bctengineer.com/q/semester_6/communication_systems/huffman-sf-a0-a4-compare
site: BCT Engineering
---

# Huffman and Shannon-Fano coding of A0–A4

Communication Systems · Chapter 6: Baseband Digital Data Transmission

- Asked in: 2074 Chaitra (CS II), 8 marks
- Video: [Huffman Coding / Procedure / University Solved Problem](https://www.youtube.com/watch?v=7S5NyF3y9zM) — Sindhu's Learning Electronics 
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_6/communication_systems/huffman-sf-a0-a4-compare
- Whole chapter: https://www.bctengineer.com/md/semester_6/communication_systems/chapter-6

## Question

The source of information symbols {A0, A1, A2, A3 and A4} have corresponding probabilities {0.4, 0.3, 0.15, 0.1 and 0.05}. Encode the source symbols using Huffman encoder and Shannon-Fano encoder and compare their efficiency.

## Short answer

For symbols with probabilities 0.4,0.3,0.15,0.1,0.05, both Huffman and Shannon-Fano produce code lengths 1,2,3,4,4, average length 2.05 bits/symbol, efficiency 97.99%.

## Answer

**Entropy** of the source $\{0.4, 0.3, 0.15, 0.1, 0.05\}$:

| 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 = 2.0087\ \text{bits/symbol}
$$

#### Huffman encoder

Combine the two lowest probabilities at each stage, place the sum as high as possible, then read the code from the final stage back to each symbol (0 = upper, 1 = lower).

**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_H &= 0.4(1) + 0.3(2) + 0.15(3) + 0.1(4) + 0.05(4) \\
&= 0.4 + 0.6 + 0.45 + 0.4 + 0.2 = 2.05\ \text{bits/symbol} \\
\eta_H &= \frac{2.0087}{2.05} = 97.99\%
\end{aligned}
$$

#### Shannon–Fano encoder

Divide the ordered list into two groups of nearly equal probability, 0 to the upper and 1 to the lower group, and repeat:
- {A0} = 0.4 | {A1, A2, A3, A4} = 0.6
- {A1} = 0.3 | {A2, A3, A4} = 0.3
- {A2} = 0.15 | {A3, A4} = 0.15
- {A3} | {A4}

| 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_{SF} &= 0.4(1)+0.3(2)+0.15(3)+0.1(4)+0.05(4) = 2.05\ \text{bits/symbol} \\
\eta_{SF} &= \frac{2.0087}{2.05} = 97.99\%
\end{aligned}
$$

#### Comparison

| Item | Huffman | Shannon–Fano |
|---|---|---|
| Average length | 2.05 bits | 2.05 bits |
| Efficiency | 97.99 % | 97.99 % |
| Redundancy | 2.01 % | 2.01 % |
| Method | Bottom-up (merging) | Top-down (splitting) |
| Optimality | Always optimal | Not always optimal |

For this source both encoders give the same code lengths (1, 2, 3, 4, 4), so the efficiencies are equal at **97.99 %**. In general Huffman's efficiency is equal to or better than Shannon–Fano's. A fixed 3-bit code would give only 66.96 %.

## Check yourself

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

1. How do Huffman and Shannon-Fano differ in approach?
   A. Huffman is bottom-up merging; Shannon-Fano is top-down splitting
   B. Huffman splits; Shannon-Fano merges
   C. Both split
   D. Both use fixed length
   Answer: A. Huffman merges the two lowest probabilities repeatedly; Shannon-Fano divides the list into nearly equal groups. (Key point: Method direction)

2. Which statement about optimality is correct?
   A. Shannon-Fano is always optimal
   B. Huffman is always optimal; Shannon-Fano is not always
   C. Neither is optimal
   D. Both always give identical lengths
   Answer: B. Huffman gives the minimum average length, so its efficiency is equal to or better than Shannon-Fano's. (Key point: Optimality)

3. For {0.4, 0.3, 0.15, 0.1, 0.05} the code lengths in both methods are:
   A. 1, 2, 3, 4, 4
   B. 2, 2, 2, 3, 3
   C. 3, 3, 3, 3, 3
   D. 1, 2, 3, 3, 3
   Answer: A. Both give L = 0.4 + 0.6 + 0.45 + 0.4 + 0.2 = 2.05 bits. (Key point: Code lengths)

4. Their efficiency is 97.99%. How is it found?
   A. 2.05 / 2.0087
   B. 2.0087 / 2.05
   C. 2.0087 / 3
   D. 1 - 2.05
   Answer: B. eta = H / L = 2.0087/2.05 = 97.99%. (Key point: Efficiency)

## Related in Communication Systems

- [Coding efficiency: binary, Shannon-Fano and Huffman](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Acoding-efficiency-binary-sf-huffman) — Communication Systems, chapter 6
- [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
- [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

- [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
- [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