Huffman-Coding
Question 1 |
A message is made up entirely of characters from the set X = {P, Q, R, S, T}. The table of probabilities for each of the characters is shown below:
If a message of 100 characters over X is encoded using Huffman coding, then the expected length of the encoded message in bits is __________.
225 | |
226 | |
227 | |
228 |
Question 1 Explanation:
General procedure to solve Huffman coding problem
Step-1: Arrange into either descending/ ascending order according to that profits.
Step-2: Apply optimal merge pattern procedure.
Step-3: Make left sub-tree value either 0 or 1, for right sub-tree, vice-versa.
= 2 × 0.34 + 2 × 0.22 + 2 × 0.19 + 3 × 0.17 + 3 × 0.08
= 2.25
∴ So, for 100 characters, 2.25 * 100 = 225
Question 2 |
Suppose the letters a, b, c, d, e, f have probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. Which of the following is the Huffman code for the letter a, b, c, d, e, f?
0, 10, 110, 1110, 11110, 11111
| |
11, 10, 011, 010, 001, 000
| |
11, 10, 01, 001, 0001, 0000
| |
110, 100, 010, 000, 001, 111
|
Question 2 Explanation:
→ 0, 10, 110, 1110, 11110, 11111
Question 3 |
Suppose the letters a, b, c, d, e, f have probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. What is the average length of Huffman codes?
3 | |
2.1875
| |
2.25 | |
1.9375
|
Question 3 Explanation:
The Average length =(1*1/2+2*1/4+3*1/8+4*1/16+5*1/32+5*1/32)=1.9375
There are 3 questions to complete.