SHANNON-FANO CODING:
This is a
basic information theoretic algorithm. A simple example will be used to illustrate
the algorithm:
Encoding
for the Shannon-Fano Algorithm:
A
top-down approach
1. Sort
symbols according to their frequencies/probabilities, e.g., ABCDE.
2. Recursively
divide into two parts, each with approx. same number of counts.
ü Procedure for shannon fano algorithm:
A
Shannon–Fano tree is built according to a specification designed to define an
effective code table. The actual algorithm is simple:
1. For a given
list of symbols, develop a corresponding list of probabilities or frequency
counts so that each symbol‘s relative frequency of occurrence is known.
2. Sort the
lists of symbols according to frequency, with the most frequently occurring
symbols at the left and the least common at the right.
3. Divide
the list into two parts, with the total frequency counts of the left part being
as close to the total of the right as possible.
4. The left
part of the list is assigned the binary digit 0, and the right part is assigned
the digit 1. This means that the codes for the symbols in the first part will
all start with 0, and the codes in the second part will all start with 1.
5. Recursively
apply the steps 3 and 4 to each of the two halves, subdividing groups and
adding bits to the codes until each symbol has become a corresponding code leaf
on the tree.
ü Tree diagram:
ü Table For Shannon Fano Coding:
Related Topics
Privacy Policy, Terms and Conditions, DMCA Policy and Compliant
Copyright © 2018-2023 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.