Information Theory and Coding > Data Compression > Explain Shannon – Fano Binary Encoding Method

What is Shannon-Fano Coding?

Shannon-Fano Algorithm is an entropy encoding technique for lossless data compression of message, Named after Claude Shannon and Robert Fano. It assigns a code to each symbol based on their probabilities of occurrence. It is a variable-length encoding scheme, that is, the codes assigned to the symbols will be of varying lengths. 

Shannon – Fano Binary Encoding Method:

Shannon – Fano procedure is the simplest available. Shannon- Fano algorithm provides us a means for constructing optimum, instantaneous codes. The procedure is as follows:

1. Create a list of probabilities for the given set of symbols.
2. List the source symbols in the order of decreasing probabilities.
3. Split the list into two parts, with the total probability of both parts being as close to each other as possible.
4. Assign a ‘ 0’ to one group and a ‘ 1’ to the other group. These form the starting code symbols of the codes.
5. Repeat steps 3 and 4 on each of the subgroups until the subgroups contain only one source symbol, to determine the succeeding code symbols of the code words.

 

Example:

Consider the message ensemble S = {s1, s2, s3, s4, s5, s6, s7, s8} with probabilities {1/4, 1/4., 1/16, 18, 1/16, 1/8, 1/16,1/16} X={0,1}

Tree diagram are as follows:

It can be seen that codes originate from the same source and diverge into different tree branches and hence it is clear that no complete code can be a prefix of any other code word. Thus the Shannon- Fano algorithm provides us a means for constructing optimum, instantaneous codes.

Prev

State Kraft Inequality with example

Next

What is Huffman Coding?

Feedback

Submit