By

Unit 2: Source Coding Dr. Shashibhushan Sharma

JK Institute of Applied Physics and
Technology
University of Allahabad,
Prayagraj
Content
• Coding for discrete memory-less source
• Fixed length code words
• Source coding theorem
• Variable length code-words
• Unique decodability and prefix conditions
• Kraft inequality
• Significance of prefix condition
• Shannon-Fano coding
• Huffmann Coding Technique
Coding for discrete memory-less source
• The source alphabet is S  s1 , s2 ,...sq  .
• The code alphabet is X   x1 , x2 ,...xr  .
• Block code: A block code is a code which maps each of the symbols of the source
alphabet s into affixed sequence of symbols of the code alphabet (sequences of x j ) are
called code words. We denote the codeword corresponding to the source symbol si by X i .
Note that X i denotes the sequence of x j 's .
• A example of binary block code is given in Table 1. Table 1 . A Binary Block Code
Coding for discrete memory-less source
• Uniquely Decodable Codes:
• A block code is nonsingular if all of words of the code are
distinct.
• The code given in Table 2 is nonsingular in small block code Table 2. A nonsingular Block Code
but it is singular in large block code, because the sequence
0011 might represent either s3 s2 or s1s1s2.
• The block code must define in some more restrictive
condition than nonsingularity if we re to obtain the usefull
codes.
•
Coding for discrete memory-less source
• Consider a second extension of block code of Table 2 Table 3. The second extension of Block Code
given in Table 3.
• A block code is uniquely decodable if, and only if, the nth
extension of code is nonsingular for every finite n. In this
block code, we have seen that the sequence of code
words of the s1s3 and s3 s1 lead the other source symbols.
This code does not satisfy the condition of uniquely
decodable.
• Sardinas and Patterson (1953) have found the necessary
and sufficient condition for unique decodability.
•
Coding for discrete memory-less source
• Two example of unique decodable codes are given in
Table 4.
Table 4. Two Uniquely Decodable Code
• The code A is nonsingular and of same length.
• The code B is also nonsingular and of different
length. The code B is called the comma code because
the 0 acts as a comma to separate one word from the
next word.
Coding for discrete memory-less source
• A unique decodable code is said to be instantaneous if it is possible to decode each word
in a sequence without reference to succeeding code symbols.
• In Table 5, the uniquely decodable code is given but that is not instantaneous, the code
word 0111 has four prefixes 0111, 011, 01, and 0.

Table 5. A uniquely decodable code

Figure 1. Subclasses of code

Coding for discrete memory-less source
• Two other method of instantaneous uniquely decodable code is here

Table 6. One Method of instantaneous code Table 7. The Second Method of instantaneous code
s1 0 s1 00
s2 10 s2 01
s3 110 s3 10
s4 1110 s4 110
s5 1111 s5 111
Kraft inequality
• A necessary and sufficient condition for the existence of an instantaneous code with word
lengths l1 , l2 ,..., lq is that
q

r
i 1
 li
1
where r is the number of different symbols in the code alphabet. For the binary case, li must
satisfy the equation
q

 1
2  li

i 1

where summation is over all the words of the block code.

Kraft inequality
• Let us take an information source with four possible symbols, s1 , s2 , s3 and s4. We have
listed five possible codes for encoding the symbols of this source into a binary alphabet.
Table 8. Five Binary Codes

4
• Now, we calculate 2
i 1
 li
for each of these codes.
Kraft inequality
• For code a we see that
4

 2  li

i 1
 2 2
 2 2
 2 2
 2 2

1
• The word lengths of the code are acceptable as the word length of an instantaneous code.
• Kraft inequality does not tell us code a is an instantaneous code. For particular this
example, the Kraft inequality tell that this is an instantaneous code each of length 2.
• For the code B 4

2
i 1
 li
 21  23  23  23

7
 1
8
• Again we see that the word lengths of this code are acceptable as the word length of an
instantaneous code.
Kraft inequality
• For the code C
4

 2  li

i 1
 2 1
 2 2
 2 3
 2 3

1
• By inspection, we find that the Code c is an instantaneous code.
• Code D also satisfy the Kraft inequality, but by inspection, we find that the fourth code
word is the prefix of the third code word. Thus, it is not an instantaneous code.
• Finally, for the code e, 4

2
i 1
 li
 21  22  23  22

1
1
8
• For this code, there is no further investigation is required.
Kraft inequality Table 9. Binary Code for the Decimal Digits

• We consider one more example with source

alphabet S  0,1, 2,...,9 into a binary instantaneous
code. Let us suppose, there is some reason for
encoding the 0 and the 1 symbols of decimal
source into relatively short binary code words.
There is realistic requirement for a source which
emits many more 0s and 1s than 2s, 3s, etc. if we
encode 0s and 1sfrom the source as
00
1  10
• And the rest of the decimal digits encoded with
equal length l, but we do not know what will be
the value of l. The Kraft inequality give the
answer.
Kraft inequality
• The Kraft inequality apply on the block code of decimal digits, we find that
9

 1
2  li

i 0

  8  2 l   1
1 1
2 4
l 5
• We can not find the instantaneous code if l < 5. The Kraft inequality only tells us that l =
5, but it does not describe that how we can construct this code.
Kraft inequality
• We are going to prove that inequality is sufficient for the existence of an instantaneous
code. The inequality is
q

 1
r  li

i 1
1

• Assume we are given word length l1 , l2 ,..., lq satisfying the above Equation, and we are
required to construct an instantaneous code with these word lengths. The required world
length may or may not be the distinct.
• Let us define n1 be the number of words in our code of length 1; n2 be the number of
words of length 2; etc. if the largest of li is equal to l , we have
l

n
i 1
i q 2
Kraft inequality
• We may use the n1 to rewrite the Eq. (1). The summation of Eq. (1) contains n1 terms of
the form r 1 , n2 terms of the form r 2 , etc. it may then be written as
l

• Multiplying r l
 i 1
n r
i 1
i
3

i
n r
i 1
l i
 r l
4

• Upon writing out this equation and rearranging terms, we get

nl  r l  n1r l 1  n2 r l  2  ...  nl 1r 5a
Kraft inequality
• We may obtain an interesting sequence of inequalities from Eq. (5a) by dropping the term
on left and dividing by r in both side.
nl 1  r l 1  n1r l  2  n2 r l 3  ...  nl  2 r 5b

........................................................
n3  r 3  n1r 2  n2 r 5c

n2  r 2  n1r 5d

n1  r 5e
• We are required to form n1 words of length 1. There are r possible such words that we
may form, using an r- symbol code alphabet.
• Since n1  r , we can select these n1code symbols arbitrarily. We are then left with r  n1
permissible prefixes of length 1-namely, just those prefixes which are not used as code
words.
Kraft inequality
• By adding one symbol at the end of each of these permissible prefixes, we may form as
many as
 r  n1  r  r 2  n1r
word of length 2. Eq. (5d) assures us that we shall need no more than this number of
words of length 2. As before, we choose our n2 words from among our r 2  n1r choices; we
are then left with
r 2  n1r  n2
unused prefixes of length 2, from which we may form
 1 2
r 2
 n r  n r  r 3
 n1r 2
 n2 r
In the same manner we choose n3 words from among our r 3  n1r 2  n2 r choices. We are
left with
r 3
 n1r 2  n2 r   n3
Unused prefixes of length 3 and so on.
 Kraft inequality
• We proceed in the same fashion until we have formed all the words our code. Eqs.5 assure
us at each stage that we have enough prefixes left. Thus, the Eq. (1) is sufficient for the
costruction of an instantaneous code with word length l1 , l2 ,..., lq .

Problem 1. A source has six possible

outputswith probabilities as shown in Table 10. Table 10
Code a,b,c,d,e and f, as given in the table are
considered.
(a)Which of these codes are uniquely
decodable?
(b) Which are instantaneous?
(c) Find the average length l for all the uniquely
decodable codes.
Source Coding
• It has been seen that source alphabet can be coded into a given set of code alphabet. There are several way
to decode the particular symbol of source alphabet into a given set of code alphabet. We have interested in
finding the uniquely decodable code with average length as small as possible.
• Definition: Let a block code transform the source symbols s1 , s2 ,..., sq into the code words X 1 , X 2 ,..., X q .
Let the probabilities of the source symbol be P1 , P2 ,..., Pq and let the lengths of the code words be l1 , l2 ,..., lq .
Then we define L, the average length of the code, by equation
q
L   pi li 1
i 1

• Consider a zero-memory source S, with symbols s1 , s2 ,..., sq and symbol probabilities P1 , P2 ,..., Pq ,
respectively. Let a block code encode these symbol into a code alphabet of r symbols, and let the length of
the word corresponding to si be li . Then the entropy
q
of this zero memory source is
H  s    Pi log Pi 2
q

Q
i 1
• Let Q1 , Q2 ,..., Qq be any q numbers such that Qi  0 for all i and i  1. By the inequality we know
that q q i 1
1 1
 P log P   P log Q
i 1
i
i 1
i 3
i i
Source Coding

with equality if and only if Pi  Qi for all i. Hence

q
H  s    Pi log Qi 4
i 1
with equality if and only if Pi  Qi for all i. Equation 4 is valid for any set of non-negative numbers Qi
which sum to 1. We may, therefore, choose
r li
Qi  q
5
 r  li

i 1

 q l j 
 
q q
and obtain H  S    Pi log r   Pi log   r 
 li

i 1 i 1  j 1 
q
 q l j 
 log r  Pli i  log   r  6
i 1  j 1 
 q l j 
 L log r  log   r 
 j 1 
Source Coding
• If we add the requirement that our code be instantaneous, the Kraft inequality tells us that the
argument of the second algorithm of the right of above Equation must be less than or equal to 1.
the logarithm is therefore, less than or equal to zero, and
H  S   L log r 7a
or,
H S 
L 7b
log r
H  S  in Equation 7 is measured in bits. Recall that L is the average number of r-ary symbols we use
to encode S. If, we measure the unit in r-ary units also, then Equation 7b may be written as
Hr  S   L 7c
For an instantaneous code and a zero memory source, L must be greater than or equal to H r  S  . This
Equation is constitute a milestone in our study of information theory. With this Equation, we have
started to present the justification for our information measure.
Source Coding

• A method of encoding for the special sources.

• On the surface, Equation 7 merely presents us with a bound on L, the average length of
instantaneous code. In certain cases, however, it is possible to much more insight from simple
arguments leading to that Equation. From Equation 6, we see that a necessary condition for the
equality rather than inequality of Equation 7 is
q

r
l j
1 8
j 1
• Then retracing our steps to Equation 4, we see that a necessary and sufficient condition for the
equality is
r li
Pi  Qi  q
 r li for all i. 9a
r
l j

j 1
or 1
log r  li for all i. 9b
Pi
Source Coding

• For an instantaneous code and a zero memory source, L must be greater than or equal to H r  S  .
Furthermore, L can achieve this lower bound if and only if we can choose the word lengths li equal
to log r 1 Pi  for all i. For the equality, therefore, log r 1 Pi  must be an integer for each i.
• We see that for equality the symbol probabilities Pi must allbe of the form 1 r  i , where  i is an


integer. As an additional, we note that if these conditions are met, we have derived the word
lengths of compact code. We simply choose li equal to  i .
Example 1. we can calculate the Entropy and Average length of zero-memory source, which source
alphabet and code alphabet are given in table 10.
Table 11
The Entropy of this source is q
1
H  s    Pi log  2 bits/symbol
i 1 Pi
It is impossible to code the symbols from this source into
an uniquely decodable binary code with average length L
less than 2 binits per symbol. Each symbol of the source
has a probability of 1 4   1 2 2 , and so by Equation 9b,
a compact code must have four words of length 2.
Source Coding
The symbols of the source are encoded with equal length Table 12
of 2 binary digits as given in Table 12.
• We define another zero-memory source with probability
of symbol of the source as given in Table 13.
The entropy of this source is
q
1 3
H  s    Pi log  1 bits/symbol
i 1 Pi 4
Table 13
All symbol probabilities of this source are of the form 1 r   1 2 
i i

with  i integer, however, and so it is possible to achieve

the lower bound of 1 34 bits/symbol . We observe from
Equation 9b that the word lengths are equal to 1, 2, 3, and
3, respectively. The code is
Source Coding Table 14

• As a check, we calculate L directly:

4
3
L   Pli i  1 bits/symbol
i 1 4
• Example 2. When the bound given in Equation 7 is acieved,
consider a zero-memory source with seven symbols shown in Table
14. Assume that we wish to construct an instantaneous trinary code
for this source. First we compute the entropy of the source. Table 15
q
1 13
H  s    Pi log  Trinary units/symbol
i 1 Pi 9

• After calculation of the code word length, The corresponding code of

the source symbols are given in Table 15. The average length of this
code words is q
13
L   Pli i  Trinary symbols/symbol
i 1 9
Source Coding

• Shannon’s First Theorem

• The Equation 9b again recall here
1
log r  li for all i. 1
Pi
• If this Equation 9b is an integer then we should choose the word length li equal to this integer. If
Equation 9b is not an integer then for the compact code li has been chosen first integer that is greater
than the calculative value of li . We select li , therefore, as the unique integer satisfying
1 1
log r  li  log r  1 2
Pi Pi
• First, we check to see that the word lengths chosen in this manner satisfy the Kraft inequality and are,
therefore, acceptable as the word length of an instantaneous code. Taking exponential of the left
inequality of equation 2 leads to
1
 r li
Pi 3
or, Pi  r li
Source Coding

• Shannon’s First Theorem contd…

• Summing Equation 3 over all i, we obtain
q q

i 
P 
i 1
r  li

i 1
q 4
1 r  li

i 1
• Equation 2, therefore, defines an acceptable set of li for an instantaneous code. If we multiply
Equation 2 by Pi and sum over all I, we find
q
1 q
 q 1 q 
 Pi log r   Pli i    Pi log r   Pi 
i 1 Pi i 1  i 1 Pi i 1  5
Hr  S   L  Hr  S  1
Source Coding

• Shannon’s First Theorem contd…

• We observe the difference between Equation 5 and lower bound of L. The lower bound of L is
independent of any particular coding scheme. The bound require only that our code be instantaneous.
• Equation 5 was derived by assuming coding method defined in Equation 2. It provides both the
lower and upper bound on L.
• Since Equation 5 is valid for any zero memory source, we may apply it to the nth extension of our
original source S.
H r  S n   Ln  H r  S n   1 6
where Ln represents the average length of code words corresponding to symbols from the nth extension
of the source S. If i is the length of code word corresponding to symbol  i , and P  i  is the
probability of  i , then qn
Ln   P  i i
i 1
7
Ln
n , therefore, is the average number of code symbol used per single symbol from S.
Source Coding

• Shannon’s First Theorem contd…

• We know that the entropy of S n is the n times the entropy of S. Equation 6 may be written as
Ln 1
Hr  S    Hr  S   8
n n
• And so it is possible to make Ln
n
as close to H r  S  as we wish by coding the nth extension of
S rather than S:
Ln
Lt  Hr  S 
n  n 9
• Equation 8 is known as the Shannon’s First Theorem or the noiseless coding theorem. It is
one of the two major theorems of information theory. Equation 8 tells us that we can make the
average number of r-ary code symbols per source symbol as small as, but no smaller than, the
entropy of the source measured in r-ary units. The price we pay for decreasing Ln is the
n n
increased coding complexity caused by the large number q source symbols with which we
must deal.
•
Source Coding

• Coding without extension.

• Our proof of Shannon’s theorem have been constructive. That is to say, Equation 2 in proof of
Shannon’s theorem provide us with a method of choosing the word length li . If we use this
method of to choose the word lengths of a block code for encoding the symbols from S n , and
take n sufficiently large. The quantity Lnn can be made as close to H r  S  as we wish.
• What if we do not want to make n sufficiently large? For a fixed n, all the theorem tells us is
that if we choose our word lengths according to Equation 2, the average length will be no
greater than the right side of Equation 8 (Shannon’s Theorem).
• The theorem does not tell us that what value of L we shall obtain. Even more important, it
does not guarantee that choosing the word lengths according to Equation 2 will give us the
smallest possible value of L.
• A simple example will serve to show that Equation 2 may indeed provide a poor way to
choose the word lengths.
 Table 16

Source Coding
• Coding without extension.
• We use Equation 2 to construct a binary instantaneous code for the zero memory source
defined in Table 16. Assume that we wish to encode this source directly without going to the
second or other higher extension. What is the smallest average length we can achieve without
extension?
• We first calculate the word length using Equation 2 as shown in the third column of Table 16.
The Equation 2 is 1 1
log r  li  log r 1
Pi Pi
• We have listed li in the fourth column. Code a shown in column 5 is then an acceptable
instantaneous code with these word lengths. The average length of code a is
q
2 2 1
La   Pli i  1   3   4  1.78 binits/source symbol
i 1 3 9 9
• The entropy of the source is
3
1
H  S    Pi log 2  1.22 bits/source symbol
i 1 Pi
Source Coding

• Note that La is indeed bounded by

H  S   La  H  S   1
• Estimated value of the code word length follow the Shannon’s theorem. However, this code word
length provide the poor code. It is easy to find an instantaneous code for this source which is better
than code a. Such a code is given in the last column of Table 16.
• For code B, we calculate the average length
q
2 2 1
La   Pli i  1   2   2  1.33 binits/source symbol
i 1 3 9 9
• This number is considerable improvement over the average length of code a.
Source Coding
• Huffman Codes
• A compact code for a source S is a code which has the smallest average length possible if we encode the
symbols from S one at a time. How we construct a compact code for affixed source?
• Consider the source S with symbols s1 , s2 ,..., sq and symbol probabilities P1 , P2 ,..., Pq . Let the
symbols be ordered so that P1  P2  ...  Pq . By regarding the last two symbols of S are combined into
one symbol, we obtain a new source from S containing onlyq  1 symbols. We refer to this new source
as a reduction of S. The symbols of this reduction of S may be reordered, and again we may combine the
two least probable symbols to form a reduction of this reduction of S. By proceeding in this manner, we
construct a sequence of sources, each containing one fewer symbol than the previous one, until we arrive
at a source with only two symbols.
Example 3.
Source Coding

Example 3. In Figure 1, we start with a source of six symbols and successively reduce this
source to a source of two symbols.

Figure 1. A source and its reductions

Source Coding

• The compact instantaneous code complete in three steps

1. Construction of a sequence of reduced source up to two symbols with decreasing order of
probabilities of source symbols.
2. the second step is merely the recognition that a binary compact instantaneous code for the
last two reduced source (a source with two symbols) is the trivial code with the two words 0
and 1.
3. We start at the last reduced source and its trivial compact instantaneous code and work
backward along the sequence of sources until we arrive at a compact instantaneous code for
the original source.
Source Coding

• Example 4. We illustrate the synthesis of a binary compact code for the source of Figure
1 in Figure 2.

Figure 2. Synthesis of a compact code

 Source Coding

• If we complement the j th digit of every word of the code and obtain another compact code.
• If we complement the first and last digits of the code obtained in Figure 2, we have the new
compact code.
• This method producing a new compact code.
• Example 5. we construct a different code for the source of example 4 in figure 3.

Figure 3. Synthesis of a compact code

Source Coding

• In Figure 2 and 3, we obtain the two compact codes. In the first compact code, the word lengths are
1, 2, 3, 4, 5, 5. In the second compact code, the word lengths are 1, 2, 4, 4, 4, 4. The average length
of these two compact codes are obtained identical.
q
La   Pli i  0.4 1  0.3  2  0.1 3  0.1 4  0.06  5  0.04  5  2.2 binits/source symbol
i 1
q
La   Pli i  0.4 1  0.3  2  0.1 4  0.1 4  0.06  4  0.04  4  2.2 binits/source symbol
i 1

• We cannot construct an instantaneous code for this source with a smaller average length.
Source Coding

• Example 6. This example illustrates that there is

no need of source reduction up to two symbols.
• If we find the compact code in the first reduction,
then no need to do further source reduction. In the
first reduction, we find that the we make the
compact code by calculating the code word lengths.
• Here, all probabilities can be formed into 1 r  .
i

So, we can reconstruct the code in the first

reduction only, and go backward to complete the
coding the coding of all symbols of the source.
Figure 4. Synthesis of a compact code
Source Coding

• r-ary Compact Codes

• The formation of reduced sources to the synthesis of a binary compact code proceeded by
combining the two least probable source symbols in order to form a single symbol. When we
wish to form an r-ary compact code, we shall combine the source symbols r at a time in order
to form one symbol in the reduced source.
• In the binary case, each source in the sequence of reduced sources contained one fewer symbol
than the source immediately preceding. In the r-ary case, we combine r symbols to form one
symbol, and thus each source in the sequence has r-1 fewer symbols than the preceding
source. We would like the last source in the sequence to have exactly r symbols. The last
source will have r symbols if and only if the original source has r+a(r-1) symbols, where a is
an integer. Therefore, if the original source does not have r+a(r-1) symbols, we add “dummy
symbols” to the source until this number is reached. The dummy symbols are assumed to have
probability 0, and so they may be ignored after a code is formed.
Source Coding
• Example 7. Consider the source with 11 symbols shown in Figure 5. We wish to form a sequence
of reduced sources from this source before encoding the source in a quaternary code- a code using
four code symbols. If the last source in the sequence is to have four symbols, S must have 4+3a
symbols, where ‘a’ is an integer. Since 11 is not of the form 4+3a, we add two dummy symbols to
S to bring the total number of symbols to 13. Now, reducing the four symbols of the source at a
time produces a source with exactly four symbols.

Figure 5. A source and its reductions.

Source Coding

• The compact code has been designed as shown in Figure 6.

Figure 6. Synthesis of a compact code.

Source Coding
• Code efficiency and redundancy
• The value of a symbol from an information source S may be measured in terms of an equivalent number of
binary digits needed to represent one symbol from that source. The Shannon’s theorem say that the average
value of a symbol from S is H(S). In more general, the average value of a symbol from S in terms of r-ary
digits is H r  S  .
• Let the average length of a uniquely decodable r-ary code for the source S be L. L can not be less than H r  S .
• Accordingly, we define  , the efficiency of the code, by
H S 
 r
L
• It is also possible to define the redundancy of the code is
Redundancy    1  
L  Hr  S 

L
Source Coding
Example 8. Consider a zero memory source S  s1 , s2 , with P  s1   3
4 and P  s2   14 . We calculate
Entropy, Average length, Efficiency, and Redundancy.
The Entropy is q
1 3 4 1
H  S    Pi log 2  log 2  log 2 4  0.811 bits A compact code for this source is as follows:
i 1 Pi 4 3 4
The average length of this code is
q
3 1
L   Pli i  1  1  1 bits
i 1 4 4
The Efficiency is
H S 
  0.811
L
The redundancy is
Rdundancy    1    1  0.811  0.189
Source Coding

• To improve the efficiency, we might code the second extension of S.

• The average length of this code is 27/16 binits. The entropy is 2H(s). So
H 2  S  2  0.81116
2    0.961
L2 27
Source Coding
• Coding the third and fourth extensions of S, we find efficiencies

3  0.985
and

4  0.991
As we encode higher and higher extensions of the original source S, the efficiency must approach 1.
Source Coding

Example 9. We are going to examine the efficiency with respect to r-ary form. We consider a zero-
memory source S with 13 symbols and symbol probabilities as shown in Table 17. In the same table,
we list the compact (Huffman) code for code alphabets comprised of 2 to 13 symbols.

Table 17. Compact Code for Different Code Alphabets

The entropy of the source is 3.125 bits per symbol.

Source Coding

• Using this fact of entropy and plot the efficiency versus

number of code symbol r.
• From Figure 7, we see that the efficiency tends to climb
as r decreases.
• Increases in efficiency is not monotonic. Efficiency of the
code at r=2 and r=4 are equal. The symbol probabilities
are all of the form 1 2 or 1 4 , where  is an integer. In
these cases, we know that we can find a compact code
with average length equal to the entropy.

Figure 7. code efficiency versus number of code symbols.

Source Coding
• What is Shannon Fano Coding?
Shannon Fano Algorithm is an entropy encoding technique for lossless data compression of
multimedia. Named after Claude Shannon and Robert Fano, it assigns a code to each symbol
based on their probabilities of occurrence. It is a variable-length encoding scheme, that is, the
codes assigned to the symbols will be of varying lengths.
• Working principle of Shannon Fano coding
• Create a list of probabilities or frequency counts for the given set of symbols so that the
relative frequency of occurrence of each symbol is known.
• Sort the list of symbols in decreasing order of probability, the most probable ones to the left
and the least probable ones to the right.
• Split the list into two parts, with the total probability of both parts being as close to each other
as possible.
• Assign the value 0 to the left part and 1 to the right part.
• Repeat steps 3 and 4 for each part until all the symbols are split into individual subgroups.
Source Coding

• Example: The given task is to construct Shannon codes for the given set of symbols
using the Shannon-Fano lossless compression technique.

• Solution: 1. Upon arranging the symbols in decreasing order of probability

P(D)+P(B)=0.30+0.28=0.58
P(A)+P(C)+P(E)=0.22+0.15+0.05=0.42

Notes. Figures and contents of Shannon-Fano coding are taken from the website:
https://www.geeksforgeeks.org/shannon-fano-algorithm-for-data-compression/
Source Coding
• Symbols are arranged in two parts in such a way that addition of probabilities of symbols in each
group are almost equal. We divide as {B, D} and {A, C, E} and assign them the values 0 and 1
respectively.

2. Now in {B, D} group P(D)=0.30, P(B)=0.28, which means that P(D) almost equal to P(B). So
divide D and B in two groups and assign 0 to D and 1 to B, respectively.

Notes. Figures and contents of Shannon-Fano coding are taken from the website:
https://www.geeksforgeeks.org/shannon-fano-algorithm-for-data-compression/
Source Coding
3. In {A, C, E} group.
P(A)=0.22, P(C)+P(E)=0.20
So the group is divided into {A} and {C, E}, and they are assigned values 0 and 1 respectively.
4. In {C, E} group
P(C)=0.15 and P(E)=0.05
So this group is divided into {C} and {E}, and assigned 0 to {C} and 1 to { E}, respectively.

Notes. Figures and contents of Shannon-Fano coding are taken from the website:
https://www.geeksforgeeks.org/shannon-fano-algorithm-for-data-compression/
 Source Coding

• The splitting is now stopped as each symbol is

separated now.
• The Shannon codes for the set of symbols are

Symbol A B C D E
Probability 0.22 0.28 0.15 0.30 0.05
Shannon Code 10 01 110 00 111

C E
0.15 0.05
Source Coding

• Code can designed by using another code tree, i.e., code tree
given by Fano in 1961. For example, consider the binary code
and its corresponding tree.
• How many different codes exist for a source with q symbols can
be phrased in term of a code trees.
• For q=2, there is only one possible tree corresponding to word Figure. 1
lengths.
• For q=3, there is again only one possible tree corresponding to
word lengths.
Figure. 2
Figure. 3

Figure. 4
Source Coding

• For q=5, there are three possible trees.

• For q=6 and 7 there are five and nine different trees,
respectively.

Figure. 5
Class Test
Answer the following questions