---
title: "Huffman code for p = 0.5, 0.25, 0.125, 0.125"
subject: "Data Communication"
chapter: 8
key: "semester_5/data_communication:huffman-p05-025-0125"
source: https://www.bctengineer.com/q/semester_5/data_communication/huffman-p05-025-0125
site: BCT Engineering
---

# Huffman code for p = 0.5, 0.25, 0.125, 0.125

Data Communication · Chapter 8: Information Theory and Coding

- Asked in: 2074 Chaitra, 4+4 marks
- Answer checked by Claude Sonnet 5.5 on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_5/data_communication/huffman-p05-025-0125
- Whole chapter: https://www.bctengineer.com/md/semester_5/data_communication/chapter-8

## Question

Write down the Huffman Algorithm clearly. Find an efficient code word and calculate efficiency that can be assigned to the symbols using Huffman Algorithm using probabilities p(x1) = 0.5, p(x2) = 0.25, p(x3) = 0.125, p(x4) = 0.125.

## Short answer

Huffman coding gives average length 1.7500 bits/symbol and 100% efficiency because probabilities are powers of two.

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

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

```text
1. x3(0.125) + x4(0.125) = 0.25
2. x2(0.25) + N1(0.25) = 0.5
3. x1(0.5) + N2(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/8 | 111 | 3 | 0.3750 |

#### Entropy, average length, efficiency
- H = −Σ p log₂ p = **1.7500 bits/symbol**
- L = Σ p·l = **1.7500 bits/symbol**
- Efficiency η = H/L = 1.7500/1.7500 = **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.7500 bits/symbol, η = 100.00 %**

The probabilities are negative powers of two, so every code length equals −log₂ p, and the code is 100 % efficient (L = H).

## Check yourself

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

1. What is the first merge for 0.5, 0.25, 0.125, 0.125?
   A. x1 and x2
   B. x3 and x4 to give 0.25
   C. x2 and x3
   D. x1 and x4
   Answer: B. The two smallest, 0.125 each, merge to 0.25. (Key point: Merge steps)

2. What code lengths result?
   A. 2, 2, 2, 2
   B. 1, 2, 3, 3
   C. 1, 1, 2, 2
   D. 3, 3, 2, 1 for x1 to x4
   Answer: B. x1 = 0, x2 = 10, x3 = 110, x4 = 111. (Key point: Code lengths)

3. Why is the efficiency exactly 100%?
   A. Probabilities are negative powers of two, so each length = -log2 p and L = H
   B. The code is fixed length
   C. Because there are four symbols
   D. Because 0 is used
   Answer: A. Lengths equal -log2 p, so L = H = 1.75 bits. (Key point: 100% efficiency)

## Related in Data Communication

- [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 eight symbols (1/2 ... 1/128)](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Ahuffman-eight-symbols) — 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 a sentence (Kun Mandir)](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Ahuffman-kun-mandir) — 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

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