Question

A message is sent across a network which is too big and needs compressing.
The message occurs with the following frequency:- m1 = 30, m2 = 25, m3 =
15, m4 = 12, m5 = 10 and m6 = 8. Using the Huffman Coding data
compression algorithm, calculate the average code length in bits and explain how many bits are required to send the same information using a fixed
length code.

Answer 1

Answer :

Given, the occurrence frequency of the source message.
Convert it into probability ( dividing the frequency by 100 as shown in the table below)

Step 1 : construct the Huffman tree.

0.45 0,18 O.27 O.55 0.10 0,12 O.08 O,25 0.30 m4 m3

Step 2 : Traverse the tree and generate the codewords for each source of message.  

Codeword frequency Probability (f/160) 8/100 = 0.08 Codeword Source length Message 3 m6 i0/i00 = 0.10 3 m5 12 O10 12/100 - 0-12 m3 15 15/100 = 0.15 25/100 = 0.25 30/100 = 0.30 10 30 %3D

Step 3 : compute average code length

(It is given by $\sum$ probability * codeword length)

Avg. Code length = 3*0.08 + 3*0.10 + 3*0.12+ 3*0.15 + 2*0.25 + 2*0.30

= 2.45 bits.

Huffman coding uses the greedy method for the purpose of implementation. It only supports variable length coding.

Huffman coding does not support fixed length codewords for each source letter. It only allocates codewords to the source letters based on its frequency / probability of occurrence.
This algorithm allocates shorter length codeword for a source letters which has a high frequency and a longer length codeword for a source letters which has less frequency of occurrence.