---
title: "Huffman code for eight symbols (1/2 ... 1/128)"
subject: "Data Communication"
chapter: 8
key: "semester_5/data_communication:huffman-eight-symbols"
source: https://www.bctengineer.com/q/semester_5/data_communication/huffman-eight-symbols
site: BCT Engineering
---

# Huffman code for eight symbols (1/2 ... 1/128)

Data Communication · Chapter 8: Information Theory and Coding

- Asked in: 2072 Chaitra, 6 marks
- Video: [Huffman Coding |  Lecture 6| Information Theory & Coding Technique| ITCCN](https://www.youtube.com/watch?v=yVG4FnH3Rc8) — Dr. Sarika Panwar
- Answer checked by Claude Sonnet 5.5 on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_5/data_communication/huffman-eight-symbols
- Whole chapter: https://www.bctengineer.com/md/semester_5/data_communication/chapter-8

## Question

A message source generates 8 symbols with the following probabilities: P(X1)=1/2, P(X2)=1/4, P(X3)=1/8, P(X4)=1/16, P(X5)=1/32, P(X6)=1/64, P(X7)=1/128 and P(X8)=1/128. Encode the message using Huffman code.

## Short answer

Huffman codes: X1=0, X2=10, X3=110, X4=1110, X5=11110, X6=111110, X7=1111110, X8=1111111. Average length L = 1.9844 bits/symbol, efficiency 100%.

## Answer

#### Huffman algorithm
1. Arrange the symbols in decreasing order of probability.
2. Combine the two least probable symbols into one with the sum of their probabilities.
3. Repeat (re-sorting) until only one symbol of probability 1 remains.
4. Assign 0 and 1 to the two branches at every merge.
5. The code of a symbol is the sequence of bits read from the root back to that symbol.

The probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/64, 1/128, 1/128 sum to 1.

#### Merging steps
At every step the two smallest probabilities are combined (N1, N2, ... are the new nodes):

```text
1. X7(0.007812) + X8(0.007812) = 0.01562
2. X6(0.01562) + N1(0.01562) = 0.03125
3. X5(0.03125) + N2(0.03125) = 0.0625
4. X4(0.0625) + N3(0.0625) = 0.125
5. X3(0.125) + N4(0.125) = 0.25
6. X2(0.25) + N5(0.25) = 0.5
7. X1(0.5) + N6(0.5) = 1
```

#### Code table

| Symbol | p | Code | Length l | p·l |
|---|---|---|---|---|
| X1 | 1/2 | 0 | 1 | 0.5000 |
| X2 | 1/4 | 10 | 2 | 0.5000 |
| X3 | 1/8 | 110 | 3 | 0.3750 |
| X4 | 1/16 | 1110 | 4 | 0.2500 |
| X5 | 1/32 | 11110 | 5 | 0.1562 |
| X6 | 1/64 | 111110 | 6 | 0.0938 |
| X7 | 1/128 | 1111110 | 7 | 0.0547 |
| X8 | 1/128 | 1111111 | 7 | 0.0547 |

#### Entropy, average length, efficiency
- H = −Σ p log₂ p = **1.9844 bits/symbol**
- L = Σ p·l = **1.9844 bits/symbol**
- Efficiency η = H/L = 1.9844/1.9844 = **100.00 %**   (redundancy = 0.00 %)

Huffman codes are not unique when probabilities tie, but L and η are the same for every valid choice.

**Answer: L = 1.9844 bits/symbol, η = 100.00 %**

## Check yourself

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

1. At each Huffman step, which symbols are combined?
   A. The two most probable symbols
   B. The two least probable symbols
   C. The most and least probable symbols
   D. Any two symbols with equal length
   Answer: B. Huffman repeatedly merges the two least probable entries into one with the summed probability. (Key point: Huffman merging rule)

2. What are the code lengths of X1 to X8?
   A. 3 for all
   B. 1,2,3,4,5,6,7,7
   C. 1,2,3,4,5,6,7,8
   D. 2,2,2,2,3,3,3,3
   Answer: B. The merge chain is lopsided, giving X1 = 0, X2 = 10, ..., and X7, X8 both 7 bits. (Key point: Code lengths)

3. Why is Huffman efficiency 100 % here?
   A. Because all probabilities are equal
   B. Because all probabilities are negative powers of 2, so L = H = 1.9844 bits/symbol
   C. Because Huffman codes are always 100 % efficient
   D. Because L is less than H
   Answer: B. With dyadic probabilities each length equals log2(1/p), so average length equals entropy. (Key point: Efficiency)

## Related in Data Communication

- [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 five symbols (0.2, 0.35, ...)](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Ahuffman-five-symbols-02-035) — Data Communication, chapter 8
- [Huffman code for p = 0.6, 0.2, 0.1, 0.05, 0.05](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Ahuffman-p06-02-01) — 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
- [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
- [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

## Related in other subjects

- [Importance of source coding; Huffman for eight symbols at 1000 symbols/s](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Asource-coding-huffman-eight-1000) — Communication Systems, chapter 6
- [Find x3[n] from X3=X1X2, x1 5-point, x2 4-point](https://www.bctengineer.com/question.md?key=semester_7%2Fdigital_signal_analysis_and_processing%3Adft-product-x3-73s) — Digital Signal Analysis and Processing, chapter 7, asked 3×
- [Source vs channel coding; Huffman for five symbols](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Asource-channel-huffman-five) — Communication Systems, chapter 6
- [Huffman code for symbols A to E](https://www.bctengineer.com/question.md?key=semester_8%2Fmultimedia_system%3Ahuffman-numerical-abcde) — Multimedia System, chapter 5