Gate2017 ss Q51

0. 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:
Character Probability
P 0.22
Q 0.34
R 0.17
S 0.19
T 0.08
Total 1.00

If a message of 100 characters over X is encoded using Huffman coding, then the expected length of the encoded message in bits is_____.

Note – Numerical Type question

Answer
Comment
Array

Option : A
Explanation :
By using haffman tree :

So, number of bit required for each alphabet:
T = 3 bit, R = 3 bit, Q = 2 bit, S = 2 bit, P = 2 bit
Then, average length per character is = (number of bits * frequency of occurance of each alphabets)
= 3 * 0.08 + 3 * 0.17 + 2 * 0.34 + 2 * 0.19 + 2 * 0.22 = 2.25 bits
And, average length for 100 character = 2.25 * 100 = 225 bits.
Hence, 225 bits is correct answer

Forgot your password?

I agree with the Terms.