GATE 2016 EC (EC2) – Question 31
A discrete memoryless source has alphabet $\{a_1,a_2,a_3,a_4\}$ with probabilities $\{1/2,1/4,1/8,1/8\}$. The minimum average codeword length in bits for error-free reconstruction is ________.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 1.74 to 1.76
Explanation
All probabilities are negative powers of two, so code lengths $\ell_i=-\log_2p_i$ are the integers 1,2,3,3. They satisfy Kraft equality and can be realized by a prefix code, for example 0,10,110,111.
The average is $\tfrac12(1)+\tfrac14(2)+\tfrac18(3)+\tfrac18(3)=1.75$ bits. It equals the entropy lower bound, so **1.75 bits** is minimal.