Shannon–Fano code

Shannon–Fano coding is one type of data compression technique. Data compression is accomplished by reducing redundancy. This technique is used for constructing a prefix code based on a set of symbols and their probabilities (estimated or measured).

Procedure:

1. Arrange probabilities in descending order.

2. Divide the probable set into two most equiprobable subset. Assign top set with a ”0”’ and bottom set with a ”1”’.

3. Continue using step 2 over and over.

Example: Find the code words occurring in the probability {1/2, 1/4, 1/8, 1/8} for symbol S1, S2, S3 & S4.

Solution: