Easy way to solve Shannon Fano Coding example?


Shannon Fano Coding: Shannon Fano Coding is used in the field of data compression, it was named after Robert Fano and Claude Shannon. In this techniques the prefix code is based on set of symbols and probabilities. It is having an advantage that it is very simple to solve. Shannon Fano coding is done for compression and to form the average length of encoding vector which should not be greater then the entropy. We have also discussed about the Binary Arithmetic Coding Technique in our previous post.

Simple trick to solve Shannon Fano Coding

The code word for the source message is constructed by arranging the probabilities of p(i) in order of decreasing order of probabilities of source messages a(i). Now the order of message sources are divided according to the value of “r” given. If the value is not given then we take value of “r” default as 2.  After dividing the source list in two parts, all symbols of one part are coded as 0 and the other part as 1 (If the value is more then two then the source sequence is divided into 0 to r-1 sequence). This is continued till only one of the symbol is left. Now all the symbols are written according to the codes generated by the process. Now write the length of each code generated like (0=1, 01=2).

Shannon-Fano Video is provided below.

Now to calculate the average length of symbol code we solve the summation of product of symbol length and its respective probability.

Average Length (L) = Summation(Limit i=0 to n){length of each code word * respective probability}

To calculate the Entropy of the source symbol we solve the summation of product of log of reciprocal of respective probability multiplied by the same probability.

Entropy (H) = Summation(i=0 to n){p * log(1/p)} where p is probability

Efficiency is calculated as Entropy divided by Length.

Efficiency = H/L

To learn all the process and easy way to solve Shannon Fano coding is provided in the video below.

So this was all about Easy way to solve Shannon Fano Coding example?. If you have any further information then you can share us by commenting in the comment box below. Stay tuned to us at EducationTimes.