Shannon-Fano coding

Juan Francisco Rodríguez Herrera
Vicente González Ruiz

September 12, 2016

Contents

1 History
2 Algorithm

1 History

2 Algorithm

  1. Sort the symbols using their probabilities.
  2. Split the set of symbols into two subsets in a way in which the each subset have the same total probability.
  3. Assign a different bit to each set.
  4. Repeat the previous procedure to each subset until the size of each subset is equal to 1.

Example

Let’s use the next probabilistic model:

Symbol Count
A 15
B 7
C 6
D 6
E 5

First iteration:

Symbol Count Bits
A 15 0
B 7 0
C 6 1
D 6 1
E 5 1

Second iteration:

Symbol Count Bits
A 15 00
B 7 01
C 6 10
D 6 11
E 5 11

Third iteration:

Symbol Count Bits
A 15 00
B 7 01
C 6 10
D 6 110
E 5 111