Example Shannon-Fano Coding

To create a code tree according to Shannon and Fano an ordered table is required providing the frequency of any symbol. Each part of the table will be divided into two segments. The algorithm has to ensure that either the upper and the lower part of the segment have nearly the same sum of frequencies. This procedure will be repeated until only single symbols are left.

Symbol  Frequency Code   Code   Total
                  Length        Length
------------------------------------------
   A       24       2     00     48
   B       12       2     01     24
   C       10       2     10     20
   D        8       3     110    24
   E        8       3     111    24
------------------------------------------
  total: 62 symbols   SF coded: 140 Bit
         linear (3 Bit/Symbol): 186 Bit

Example Shannon-Fanocode tree

The original data can be coded with an average length of 2.26 bit. Linear coding of 5 symbols would require 3 bit per symbol. But, before generating a Shannon-Fano code tree the table must be known or it must be derived from preceding data.

< ^ >