Past exam question: 2075 Chaitra, Q8
Open in the Padhaiko appDefine entropy in information theory. Find the efficient code word and efficiency using Hoffman algorithm using probabilities .
Solution
Definition of Entropy in Information Theory: In information theory (formulated by Claude Shannon in 1948), entropy is the mathematical measure of the average information content, uncertainty, or surprise produced by a discrete memoryless information source :
where is the probability of occurrence of source symbol , and is the self-information of symbol . Entropy establishes the fundamental lower bound on the average codeword length required for lossless source compression (Shannon's Source Coding Theorem: ).
Huffman Tree Construction for the Given Probabilities: Source symbols arranged in descending order:
Merging stages:
- Merge lowest two: . New sorted list: .
- Merge lowest two: . New sorted list: .
- Merge lowest two: . New sorted list: .
- Merge final two: .
Assigning binary digits (0 to top/higher, 1 to bottom/lower branch):
- receives:
0(length ) - receives:
1- receives:
10(length ) - receives:
11- receives:
110(length ) - receives:
111- receives:
1110(length ) - receives:
1111(length )
- receives:
- receives:
- receives:
Codeword Table and Performance Calculations:
| Symbol | Probability | Codeword | Length | ||
|---|---|---|---|---|---|
0 | 1 | ||||
10 | 2 | ||||
110 | 3 | ||||
1110 | 4 | ||||
1111 | 4 | ||||
| Total | 1.00 | — | — |
- Average Codeword Length:
- Entropy:
- Coding Efficiency ():
- Entropy: measures the average uncertainty or information content of a source.
- Huffman Codewords: :
0, :10, :110, :1110, :1111. - Average Length: .
- Entropy: .
- Efficiency: .