---
title: "Shannon-Fano and Huffman codes for six messages"
subject: "Communication Systems"
chapter: 6
key: "semester_6/communication_systems:sf-huffman-six-messages"
source: https://www.bctengineer.com/q/semester_6/communication_systems/sf-huffman-six-messages
site: BCT Engineering
---

# Shannon-Fano and Huffman codes for six messages

Communication Systems · Chapter 6: Baseband Digital Data Transmission

- Asked in: 2075 Asoj (CS II), 8 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/sf-huffman-six-messages
- Whole chapter: https://www.bctengineer.com/md/semester_6/communication_systems/chapter-6

## Question

Six messages are transmitted with probabilities 0.3, 0.08, 0.1, 0.15, 0.25 and 0.12 respectively. Obtain their respective Shannon-Fano and Huffman's codes and code efficiencies.

## Short answer

For probabilities 0.3,0.08,0.1,0.15,0.25,0.12, Shannon-Fano and Huffman codes both give average length 2.45 bits/message and efficiency 98.87%.

## Answer

Messages $m_1 \dots m_6$ have $p = 0.3, 0.08, 0.1, 0.15, 0.25, 0.12$ (sum = 1). Arranged in decreasing order: $m_1$ 0.3, $m_5$ 0.25, $m_4$ 0.15, $m_6$ 0.12, $m_3$ 0.1, $m_2$ 0.08.

**Entropy:**

| Symbol | $p_i$ | $\log_2(1/p_i)$ | $p_i\log_2(1/p_i)$ |
|---|---|---|---|
| m1 | 0.3 | 1.7370 | 0.5211 |
| m2 | 0.08 | 3.6439 | 0.2915 |
| m3 | 0.1 | 3.3219 | 0.3322 |
| m4 | 0.15 | 2.7370 | 0.4105 |
| m5 | 0.25 | 2.0000 | 0.5000 |
| m6 | 0.12 | 3.0589 | 0.3671 |
| **Total** | 1 | | **2.4224** |

$$
H = 2.4224\ \text{bits/message}
$$

#### Shannon–Fano code

Split into equal-probability halves: {0.3, 0.25} = 0.55 vs {0.15, 0.12, 0.1, 0.08} = 0.45; then {0.15, 0.12} = 0.27 vs {0.1, 0.08} = 0.18, and so on.

| Symbol | $p_i$ | Step 1 | Step 2 | Step 3 | Code | $l_i$ |
|---|---|---|---|---|---|---|
| m1 | 0.3 | 0 | 0 |  | 00 | 2 |
| m5 | 0.25 | 0 | 1 |  | 01 | 2 |
| m4 | 0.15 | 1 | 0 | 0 | 100 | 3 |
| m6 | 0.12 | 1 | 0 | 1 | 101 | 3 |
| m3 | 0.1 | 1 | 1 | 0 | 110 | 3 |
| m2 | 0.08 | 1 | 1 | 1 | 111 | 3 |

$$
\begin{aligned}
\bar L_{SF} &= 0.3(2)+0.25(2)+0.15(3)+0.12(3)+0.1(3)+0.08(3) \\
&= 0.6+0.5+0.45+0.36+0.3+0.24 = 2.45\ \text{bits} \\
\eta_{SF} &= \frac{2.4224}{2.45} = 98.87\%
\end{aligned}
$$

#### Huffman code

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

| Stage | Probabilities (descending) | Combined |
|---|---|---|
| 1 | 0.3, 0.25, 0.15, 0.12, 0.1, 0.08 | 0.1 + 0.08 = 0.18 |
| 2 | 0.3, 0.25, 0.18, 0.15, 0.12 | 0.15 + 0.12 = 0.27 |
| 3 | 0.3, 0.27, 0.25, 0.18 | 0.25 + 0.18 = 0.43 |
| 4 | 0.43, 0.3, 0.27 | 0.3 + 0.27 = 0.57 |
| 5 | 0.57, 0.43 | 0.57 + 0.43 = 1 |

| Symbol | $p_i$ | Huffman code | $l_i$ |
|---|---|---|---|
| m1 | 0.3 | 00 | 2 |
| m5 | 0.25 | 10 | 2 |
| m4 | 0.15 | 010 | 3 |
| m6 | 0.12 | 011 | 3 |
| m3 | 0.1 | 110 | 3 |
| m2 | 0.08 | 111 | 3 |

$$
\begin{aligned}
\bar L_{H} &= 0.3(2)+0.25(2)+0.15(3)+0.12(3)+0.1(3)+0.08(3) = 2.45\ \text{bits} \\
\eta_{H} &= \frac{2.4224}{2.45} = 98.87\%
\end{aligned}
$$

| Method | $\bar L$ | Efficiency | Redundancy |
|---|---|---|---|
| Shannon–Fano | 2.45 | 98.87 % | 1.13 % |
| Huffman | 2.45 | 98.87 % | 1.13 % |

**Answer:** both codes give $\bar L = 2.45$ bits/message and efficiency **98.87 %**.

## Check yourself

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

1. What is the first step before applying Shannon-Fano or Huffman?
   A. Arrange probabilities in decreasing order
   B. Compute efficiency
   C. Assign 3-bit codes
   D. Add a parity bit
   Answer: A. Both methods start from the symbols sorted by probability: 0.3, 0.25, 0.15, 0.12, 0.1, 0.08. (Key point: Ordering)

2. What is the first Shannon-Fano split?
   A. {0.3} vs the rest
   B. {0.3, 0.25} = 0.55 vs {0.15, 0.12, 0.1, 0.08} = 0.45
   C. {0.3, 0.25, 0.15} vs the rest
   D. Pairs of symbols
   Answer: B. This gives the nearly equal split 0.55 vs 0.45. (Key point: Shannon-Fano first split)

3. What is the first Huffman combination?
   A. 0.3 + 0.25
   B. 0.1 + 0.08 = 0.18
   C. 0.15 + 0.12
   D. 0.3 + 0.08
   Answer: B. The two lowest probabilities, 0.1 and 0.08, are merged first. (Key point: Huffman first merge)

4. Both codes have lengths 2,2,3,3,3,3. The efficiency is:
   A. 100%
   B. 98.87%
   C. 90%
   D. 95.2%
   Answer: B. L = 2.45 bits and H = 2.4224, so eta = 2.4224/2.45 = 98.87%. (Key point: Efficiency)

## Related in Communication Systems

- [Digital communication system; Shannon-Fano for six symbols](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Adcs-block-shannon-fano-six) — 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
- [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
- [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
- [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
- [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

## Related in other subjects

- [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
- [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
- [Huffman code for six symbols (0.04, 0.1, ...)](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Ahuffman-six-symbols-004) — Data Communication, chapter 8
- [Huffman code for p = 0.5, 0.25, 0.125, 0.125](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Ahuffman-p05-025-0125) — Data Communication, chapter 8