Design a minimum variance Huffman code for a source that put out letter from an alphabet $A={a_1, a_2, a_3, a_4, a_5, a_6 }$ with $P(a_1)= P(a_2)=0.2, P(a_3)=0.25, P(a_4)=0.05, P(a_5)=0.15, P(a_6)=0.15$. Find the entropy of the source, avg. length of the code and efficiency. Also comment on the difference between Huffman code and minimum variance Huffman code. -

Mumbai University > EXTC > Sem 7 > Data Compression and Encryption

Marks: 10 M

Year: DEC 2014

1.The probabilities for each character are arranged in descending order and by using Minimum variance Huffman coding, we obtained following Huffman tree.

2.Therefore, the codewords generated are as follows,

3.Entropy:

$$H=\sum^n_{n=1}pk. \log_2 \dfrac{1}{Pk}$$

$=0.25.\log_2 \dfrac{1}{0.2}+2*0.2 \log_2 \dfrac{1}{0.2}+2*0.15\log_2\dfrac{1}{0.15}+0.05\log_2\dfrac{1}{0.05} \\ =0.4695 bits/ symbol$

4.Average Lenght :

$$L=\sum ^n_{k=1} pk.l_k$$

Where, $l_k$= length of codeword.

$=0.25*2+2*0.2+3*0.2+3*0.15+3*0.15+3*0.05 \\ =2.55$

5.Coding efficiency $(η ) = H /L = 96.70 \%$