edited by
14,050 views
29 votes
29 votes

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 by

2 Answers

Best answer
34 votes
34 votes

$$\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 by
15 votes
15 votes

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

Answer:

Related questions