- 2074 Bhadra · 5+5 marks
Huffman code for symbols A to E
Short answer
The Huffman tree merges C+A=0.08, then +D=0.28, then +E=0.52, then +B=1.00. Codes are B=0, E=10, D=111, A=1101, C=1100, giving an average length of 1.88 bits/symbol.
A certain source emits symbols {A, B, C, D, E} with corresponding probabilities P(A)=0.06, P(B)=0.48, P(C)=0.02, P(D)=0.20, P(E)=0.24. Create a Huffman code tree and also derive the Huffman code for each symbol.
Given: P(A) = 0.06, P(B) = 0.48, P(C) = 0.02, P(D) = 0.20, P(E) = 0.24 (sum = 1.00).
Part 1: Huffman code tree
Sort ascending: C (0.02), A (0.06), D (0.20), E (0.24), B (0.48).
| Step | Two smallest | Merged node |
|---|---|---|
| 1 | C (0.02) + A (0.06) | CA = 0.08 |
| 2 | CA (0.08) + D (0.20) | CAD = 0.28 |
| 3 | E (0.24) + CAD (0.28) | ECAD = 0.52 |
| 4 | B (0.48) + ECAD (0.52) | Root = 1.00 |
Lists after each step: (0.08, 0.20, 0.24, 0.48), then (0.24, 0.28, 0.48), then (0.48, 0.52), then (1.00).
Root(1.00)
0/ \1
B(.48) ECAD(.52)
0/ \1
E(.24) CAD(.28)
0/ \1
CA(.08) D(.20)
0/ \1
C(.02) A(.06)
Labelling: at every node the left branch is 0 and the right branch is 1.
Part 2: Huffman codes
Follow the path from the root to each leaf:
| Symbol | Probability | Path | Code | Length |
|---|---|---|---|---|
| B | 0.48 | 0 | 0 | 1 |
| E | 0.24 | 1, 0 | 10 | 2 |
| D | 0.20 | 1, 1, 1 | 111 | 3 |
| A | 0.06 | 1, 1, 0, 1 | 1101 | 4 |
| C | 0.02 | 1, 1, 0, 0 | 1100 | 4 |
Check - prefix property: none of 0, 10, 111, 1101, 1100 is a prefix of another.
Average length = 0.48(1) + 0.24(2) + 0.20(3) + 0.06(4) + 0.02(4) = 0.48 + 0.48 + 0.60 + 0.24 + 0.08 = 1.88 bits/symbol.
A fixed code needs 3 bits, so Huffman saves (3 - 1.88)/3 = 37.3%. The source entropy is H = 1.823 bits, so the code is close to the theoretical minimum.
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- Huffman code tree steps with example · Multimedia System, chapter 5 · asked 7×
- How Huffman code reduces file size · Multimedia System, chapter 5
- Huffman code for seven-symbol source · Communication Systems, chapter 6
- Importance of source coding; Huffman for eight symbols at 1000 symbols/s · Communication Systems, chapter 6
- Source vs channel coding; Huffman for five symbols · Communication Systems, chapter 6
- Huffman code for symbols A to E (0.4, 0.3, ...) · Data Communication, chapter 8