---
title: "Weighted Huffman encoding and decoding"
subject: "Data Communication"
chapter: 8
key: "semester_5/data_communication:huffman-jasta-lai"
source: https://www.bctengineer.com/q/semester_5/data_communication/huffman-jasta-lai
site: BCT Engineering
---

# Weighted Huffman encoding and decoding

Data Communication · Chapter 8: Information Theory and Coding

- Asked in: 2078 Bhadra, 10 marks
- Video: [L-4.3: Huffman Coding Algorithm in Hindi with Example | Greedy Techniques(Algorithm)](https://www.youtube.com/watch?v=uDS8AkTAcIU) — Gate Smashers
- Answer checked by Claude Sonnet 5.5 on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_5/data_communication/huffman-jasta-lai
- Whole chapter: https://www.bctengineer.com/md/semester_5/data_communication/chapter-8

## Question

Encode "Jasta lai tastai dhido lai nistai" using weighted Huffman encoder. Also demonstrate how it is decoded.

## Short answer

Letter frequencies give Huffman codes (e.g., a=01, i=00). Encoding: replace letters to get 83-bit stream. Decoding: receiver uses same tree, reads bits sequentially; each leaf reached outputs a symbol, then restart. Prefix-free property ensures unique decoding. Efficiency ≈ 99.6%.

## Answer

**Assumptions:** spaces are ignored, upper and lower case letters are treated as the same symbol, and each letter is a source symbol. The sentence has **28 letters** and **10 distinct symbols**.

#### Step 1: frequencies
a=7, i=6, t=4, s=3, d=2, l=2, h=1, j=1, n=1, o=1

#### Step 2: build the Huffman tree
Repeatedly merge the two smallest weights (N1, N2, ... are the new nodes):

```text
 1. h(1) + j(1) = 2  -> N1
 2. n(1) + o(1) = 2  -> N2
 3. d(2) + l(2) = 4  -> N3
 4. N1(2) + N2(2) = 4  -> N4
 5. s(3) + t(4) = 7  -> N5
 6. N3(4) + N4(4) = 8  -> N6
 7. i(6) + a(7) = 13  -> N7
 8. N5(7) + N6(8) = 15  -> N8
 9. N7(13) + N8(15) = 28  -> N9
```

The branch to the smaller-weight node is labelled 0 and to the larger 1, and the codes are read from the root downwards.

#### Step 3: code table

| Symbol | Count | p | Code | Length |
|---|---|---|---|---|
| a | 7 | 7/28 | 01 | 2 |
| i | 6 | 6/28 | 00 | 2 |
| t | 4 | 4/28 | 101 | 3 |
| s | 3 | 3/28 | 100 | 3 |
| d | 2 | 2/28 | 1100 | 4 |
| l | 2 | 2/28 | 1101 | 4 |
| h | 1 | 1/28 | 11100 | 5 |
| j | 1 | 1/28 | 11101 | 5 |
| n | 1 | 1/28 | 11110 | 5 |
| o | 1 | 1/28 | 11111 | 5 |

#### Step 4: entropy, average length and efficiency
- Entropy H = −Σ p log₂ p = **2.9532 bits/symbol**
- Average length L = Σ p·l = 83/28 = **2.9643 bits/symbol**
- Efficiency η = H / L = 2.9532 / 2.9643 = **99.63 %**
- Total bits with Huffman = 83; with fixed-length codes (4 bits/symbol) = 112, so saving = 29 bits.

(Huffman codes are not unique when weights tie, but every choice gives the same average length and efficiency.)

**Answer: η ≈ 99.6 %**

#### Encoding the sentence
Replace each letter by its code (words shown separately; spaces are not coded):

```text
Jasta    111010110010101
lai      11010100
tastai   101011001010100
dhido    11001110000110011111
lai      11010100
nistai   11110001001010100
```
Total = 83 bits (against 112 bits with 4-bit fixed codes).

Complete stream:

```text
11101011001010111010100101011001010100110011100001100111111101010011110001001010100
```

#### Decoding
The receiver has the same code table (or the same frequencies to rebuild the tree). It reads bits from the left and walks down the tree (0 = left branch, 1 = right branch) until a leaf is reached, outputs that letter and restarts at the root. Because no code is a prefix of another, there is no ambiguity.

First bits: 11101 01 100 101 01 ...
- 1 → 11 → 111 → 1110 → 11101: leaf **j**
- 0 → 01: leaf **a**
- 1 → 10 → 100: leaf **s**
- 1 → 10 → 101: leaf **t**
- 0 → 01: leaf **a**

So "jasta" is recovered, and the same procedure over the whole stream gives "jastalaitastaidhidolainistai" (the original letters, without spaces).

## Check yourself

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

1. Which symbols receive the shortest codes (2 bits) and why?
   A. h, j, n, o, the rarest
   B. a and i, the most frequent (7 and 6)
   C. t and s
   D. d and l
   Answer: B. Huffman gives the shortest codes to the highest-frequency symbols: a=7 and i=6. (Key point: Code assignment)

2. How many bits does the encoded sentence need, against fixed 4-bit codes?
   A. 83 bits versus 112 bits
   B. 112 bits versus 83 bits
   C. 28 bits versus 83 bits
   D. 83 bits versus 28 bits
   Answer: A. Huffman uses 83 bits, while 28 letters at 4 bits would need 112. (Key point: Encoded length)

3. How does the receiver decode?
   A. Counts bits in blocks of 4
   B. Reads bits from the left, walks down the tree to a leaf, outputs the letter, and restarts at the root
   C. Searches for the longest code first
   D. Needs spaces marked in the stream
   Answer: B. Since no code is a prefix of another, walking the tree until a leaf identifies each symbol unambiguously. (Key point: Decoding procedure)

4. Decoding 11101 01 100 101 01 begins with which letters?
   A. j a s t a
   B. a j t s i
   C. h a s t a
   D. j i s t a
   Answer: A. 11101 = j, 01 = a, 100 = s, 101 = t, 01 = a, giving 'jasta'. (Key point: Decoding example)

## Related in Data Communication

- [Huffman code for a sentence (Phool ko)](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Ahuffman-phool-ko) — Data Communication, chapter 8
- [Encode 1101001 with polar NRZ, AMI, Manchester](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Aline-coding-1101001) — Data Communication, chapter 5, asked 3×
- [Encode 1001101110 with unipolar, polar, bipolar codes](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Aline-coding-1001101110) — Data Communication, chapter 5, asked 3×
- [Encode 10010110001 with NRZ-L, NRZ-I, diff. Manchester](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Aline-coding-10010110001) — Data Communication, chapter 5
- [Encode 1010011001 with five line codes](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Aline-coding-1010011001) — Data Communication, chapter 5
- [Line coding: properties; encode 01001100011](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Aline-coding-01001100011) — Data Communication, chapter 5

## Related in other subjects

- [CDMA encoding and decoding](https://www.bctengineer.com/question.md?key=semester_7%2Fwireless_communication%3Acdma-encoding-decoding) — Wireless Communication, chapter 7, asked 2×
- [Short note: Convolutional encoding and decoding](https://www.bctengineer.com/question.md?key=semester_7%2Fwireless_communication%3Aconvolutional-coding) — Wireless Communication, chapter 6
- [Huffman encoding of symbols A to F](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Ahuffman-encode-symbols) — Data Structure and Algorithm, chapter 6
- [Importance of source encoder; Huffman algorithm](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Asource-encoder-huffman-algorithm) — Communication Systems, chapter 6