# GATE2007-77

3.1k views

Suppose the letters $a, \,b, \,c, \,d, \,e, \,f$ have probabilities $\dfrac{1}{2}, \dfrac{1}{4}, \dfrac{1}{8}, \dfrac{1}{16}, \dfrac{1}{32}, \dfrac{1}{32}$, respectively.

What is the average length of the Huffman code for the letters $a, \,b, \,c, \,d, \,e, \,f$?

1. $3$
2. $2.1875$
3. $2.25$
4. $1.9375$

edited
0
And what is Q.76?
0

$$\begin{array}{|c|c|} \hline \textbf{Letter} & \textbf{Probability} \\\hline a & 1/2 \\\hline b & 1/4 \\\hline c & 1/8 \\\hline d & 1/16 \\\hline e & 1/32 \\\hline f & 1/32 \\\hline \end{array}$$

$\begin{array}{cc} \textbf{Prefix Code} & \textbf{Code Length} \\ a = 0 & 1 \\ b =10 & 2 \\ c = 110 & 3 \\ d = 1110 & 4 \\ e = 11110 & 5 \\ f = 11111 & 5 \end{array}$

Avg length $= \dfrac{1}{2} \times 1 + \dfrac{1}{4} \times 2+ \dfrac{1}{8} \times 3+ \dfrac{1}{16} \times 4+ \dfrac{1}{32} \times 5+ \dfrac{1}{32} \times 5 \\ = \dfrac{16 + 16 + 12 + 8 + 5 + 5}{32} \\ = 1.9375$

Correct Answer: $D$

edited
0
If multiplied with probability directly then don't divide by $\mathbf{100}$

Based on the probabilities, we can say the probable frequency of the letters will be

16, 8, 4, 2, 1, 1

Now, the Huffman tree can be constructed as follows:

Average length will be 1/2 * 1 + 1/4 * 2 + 1/8 * 3 + 1/16 * 4 + 1/32 * 5 + 1/32 * 5

= 62/32 = 1.9375

https://www.siggraph.org/education/materials/HyperGraph/video/mpeg/mpegfaq/huffman_tutorial.html

3
Why isn't average length (sum of lenghts of a,b,c,d,e,f)$/6$ ?
0
Because not all the letters occur with same frequency or probability. Purpose of Huffman encoding is to represent the most occurring character with least number of bits. As u can see a has been represented with only 1 bit because it occurs the most with probability 1/2. So we need to multiply length of bits with the probability with which they occur.
0
After calculating like arjun sir, we can even multiply with probably frequencies like this: 16*1 + 8*1 + 4*3 + 2*4 +1*5*2 / 16+ 8+4+2+1+1 = 1.9375
1

@ sir,

for such huffman coding question sometimes sees confusong, Sir can you please check this is right or wrong

1) Expected Length of Huffman Code for N chars (Frequencies given ) =

$\sum$(Bits needed for char * its frequency)

2) Average Length Of Huffman Code for N characters OR Average Bits needed for N characeters = (Assuming average over N characters)

[ $\sum$(Bits needed for char * its frequency) ] / Total characters

1 vote
The letters a, b, c, d, e, f have probabilities
1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively.

1
/   \
/     \
1/2    a(1/2)
/  \
/    \
1/4  b(1/4)
/   \
/     \
1/8   c(1/8)
/  \
/    \
1/16  d(1/16)
/  \
e    f
The average length = (1*1/2 + 2*1/4 + 3*1/8 + 4*1/16 + 5*1/32 + 5*1/32)
= 1.9375 

## Related questions

Suppose the letters $a, \,b, \,c, \,d, \,e, \,f$ have probabilities $\frac{1}{2}, \frac{1}{4}, \frac{1}{8}, \frac{1}{16}, \frac{1}{32}, \frac{1}{32}$, respectively. Which of the following is the Huffman code for the letter $a, \,b, \,c, \,d, \,e, \,f$? $0$, $10$, $110$ ... $11$, $10$, $011$, $010$, $001$, $000$ $11$, $10$, $01$, $001$, $0001$, $0000$ $110$, $100$, $010$, $000$, $001$, $111$
in Huffman Code, we get extract the minimum at each time, but my minimum is creating duplicate, then which one i choose? i am getting the same avg.no.of bits for every Huffman tree, but the problem is my tree is changing therefore representing the character also changed, if some one asks convert the message ... $\frac{12}{30}$