A message is made up entirely of characters from the set \(X=\{P, Q, R, S,…
2017
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:
\(\begin{array}{|c|c|}\hline \textbf{Character} & \textbf{Probability } \\\hline \text{$P$} & \text{$0.22$} \\ \text{$Q$} & \text{$0.34$} \\ \text{$R$} & \text{$0.17$} \\ \text{$S$} & \text{$0.19$} \\ \text{$T$} & \text{$0.08$} \\ \hline\text{Total} & \text{$1.00$} \\\hline \end{array}\)
If a message of 100 characters over \(X\) is encoded using Huffman coding, then the expected length of the encoded message in bits is ______.
Attempted by 117 students.
Show answer & explanation
Correct answer: 225
Key idea: build the Huffman tree and compute the weighted average code length L = Σ p(i)·l(i).
Build the Huffman tree by repeatedly combining the two smallest probabilities: T(0.08)+R(0.17)=0.25, S(0.19)+P(0.22)=0.41, then 0.25+Q(0.34)=0.59, and finally 0.41+0.59=1.00.
From the tree, the code lengths are: P → 2 bits, Q → 2 bits, S → 2 bits, R → 3 bits, T → 3 bits.
Compute the expected code length per character:
L = 0.22·2 + 0.34·2 + 0.17·3 + 0.19·2 + 0.08·3 = 2.25 bits per character.
For a 100-character message the expected encoded length is 100 × 2.25 = 225 bits.
A video solution is available for this question — log in and enroll to watch it.