Question

Example: Consider a discrete memoryless source X which has six symbols x1, X2, Xg, X4 X5 and Xg With probabilities 0.45, 0.20, 0.12, 0.10, 0.09 and 0.04, respectively 1. Construct the Huffman code for X 2. Calculate the efficiency of the code.

Answer 1

Huffman coding p(x_1) = 0. 45 p(x_2) = 0. 20 p(x_3) = 0. 12 p(x_4) = 0. 10 p(x_5) = 0. 09 p(x_6) = 0. 04. Efficiency (eta) eta = H/L, L = sigma^n_i = 1 p_i n_i: H = sigma^n_i = 1 p_i log_2 1/p_i H = sigma^6_i = 1 p_i log_2 1/p_i = -sigma^6_i = 1 p_i log_2 p_i H = -[0. 045 log_2 0. 45 + 0. 2 log_2 0. 2 + 0. 12 log_2 0. 12 + 0. 10 log_2 0. 10 + 0. 09 log_2 0. 09 + 0. 04 log_2 0. 04] = -[(- 0. 51) + (- 0. 96) + (- 0. 36) + (- 0. 33)(- 0. 31) + (- 0. 185)] H = [2. 155] L = 0. 45 + 0. 6 + 0. 36 + 0. 3 + 0. 36 + 0. 16 L = 2. 23