Huffman Coding
1. Sort the source alphabet in order of decreasing probability. These are
the leaves of the “coding tree.”
2. Merge the r source symbols with smallest probability into a new “source
symbol” with probability equal to the sum of the r smallest probabilities. This is an interior node of
the coding tree.
3. Repeat this process until only one source symbol (with probability one)
remains. This is the root of the coding tree. Huffman Coding (contd.)
4. To find the codeword for a given source symbol trace the coding tree
from the root to the source symbol (leaf), e.g., when r = 2, add a zero to the
codeword when traversing a left branch and a one when traversing a right
branch.
· If the number of symbols in the code alphabet is r, then there must be n = r+k(r?1) source alphabet symbols (k
integer) in the Huffman code.
· This is because each stage of the Huffman coding algorithm reduces the
size of the source alphabet by r?1 and there must be r symbols in the final stage
to merge to form the root of the coding tree.
· If there are less source alphabet symbols, then one must add source
symbols (with probability zero), until n= r+k(r?1) for some integer k.
Huffman coding example.
Fano Coding
1. Merge the source symbols
into r sets, so that the sums of the probabilities
in each set are as equal as possible.
2. Assign a unique code
alphabet symbol to the members of each set.
3. Repeat this process
until the sets are of size r or less.
Fano Coding example
Fixed-length source
codes
The simplest approach
to encoding a discrete source into binary digits is to convert each source
letter individually into a fixed-length block of L bits. There are (2L)different combinations of values for a block of L bits. Thus, if the
number of letters in the source alphabet, M = |X |, satisfies M 
2L,
then a different binary L-tuple may be assigned to each letter. Thus the
letters can be uniquely decoded from the binary blocks, and the code is
uniquely decodable.
For example, if the
alphabet X consists of the M = 7 letters {a; b; c; d; e; f; g}, then binary blocks
of length 3 are sufficient, and there exists an invertible mapping from X to a
subset of 7 binary 3-tuples; e.g.,