shannon fano coding example and huffman coding entropy formula :
ENTROPY CODING
The design of a variablelength code such that its average codeword length approaches the entropy of DMS is often referred to as entropy coding. In this section, we present two examples of entropy coding. These are as under :
(i) Shanonfano coding
(ii) Huffman coding
9.20.1. ShannonFano Coding
An efficient code can be obtained by the following simple procedure, known as ShannonFano algorithm:
 List the source symbols in order of decreasing probability.
 Partition the set into two sets that are as close to equiprobables as possible, and assign 0 to the upper set 1 to the lower set.
 Continue this process, each time partitioning the sets with as nearly equal probabilities as possible until further partitioning is not possible.
An example of ShannonFano encoding is shown in Table 9.6. Note in ShannonFano encoding the ambiguity may arise in the choice of approximately equiprobable sets.
Table 9.6. ShannonFano Encoding
x_{i}  P(x_{i})  Step 1  Step 2  Step 3  Step 4  Code 
x_{1} x_{2} x_{3} x_{4} x_{5} x_{6} 
0.30 0.25 0.20 0.12 0.08 0.05 
0 0 
0  

00 01 10 110 1110 1111 
1  
1 1 1 1 
0  
1 1 1 
0  
1 1 
0  
1 
H(X) = 2.36 b/symbol
L = 2.38 b/symbol
Ƞ = H(X)/L = 0.99
9.20.2. The Huffman Coding*
(UP. Tech., Sem. Examination, 200304.200607) (05 marks)
In general, Huffman encoding results in an optimum code. Thus, it is the code that has the highest efficiency. The Huffman encoding procedure is as follows:
 List the source symbols in order of decreasing probability.
 Combine the probabilities of the two symbols having the lowest probabilities, and reorder the resultant probabilities, this step is called rduction 1. The same procedure is repredure is repeated until there are two ordered probabilities remaining.
 Start encoding with the last reduction, which consist of exactly two ordered probabilities. Assign 0 as first digit in the codewords for all the source symbols associated with the first probability; assign 1 to the second probability.
 Now go back and assign 0 and 1 to the second digit for the two probabilities that were combined in the previous reduction step, retaining all assignment; made in Step 3.
 Keep regressing this way until the first column is reached.
An example of Huffman encoding is shown in Table 9.7
H(X) = 2.36 b/symbol
L = 2.38 b/symbol
Ƞ = 0.99
Table 9.7. Huffman Encoding
table
EXAMPLE 9.44 A DMS X has four symbols x_{1}, x_{2}, x_{3}, and x_{4} with P(x_{1}) = , P(x_{2}) = , and P(x_{3}) = P(x_{4}) = . Construct a ShannonFano code for X ; show that this code has the optimum property that n_{i} = I(x_{i}) and that the code efficiency is 100 percent.
Solution: The ShannonFano code is constructed as follows (see Table 9.8).
* Explain Huffman coding with the help of an example.
(U.P. Tech, Sem. Exam; 200607) (05 marks)
Table 9.8.
x_{i}  P(x_{i})  Step 1  Step 2  Step 3  Code  
x_{1} x_{2} x_{3} x_{4} 
1/2 1/4 1/8 1/8 
0  0 
0 10 110 111 

1  0  
1 1 
1 1 

1 
I(x_{1}) = log_{2} = 1 = n_{1}
I(x_{2}) = log_{2} = 2 = n_{2}
I(x_{3}) = log_{2} = 3 = n_{3}
I(x_{4}) = log_{2} = 3 = n_{4}
We know that, Equation
or H(X) = (1) + (2) + (3) + (3) = 1.75
Equation
Also Ƞ = = 1 = 100% Ans.
EXAMPLE 9.45. A DMS X has five equally likely symbols.
(i) Construct a ShannonFano code for X, and calculate the efficiency of the code.
(ii) Construct another ShannonFano code and compare the results.
(iii) Repeat for the Huffman code and compare the results.
(Madras University, 1998)
Solution: A ShannonFano code [by choosing two approximately equiprobable (0.4 versus 0.6) sets] is constructed as follows (see Table 9.9)
Table 9.9.
x_{i}  P(x_{i})  Step 1  Step 2  Step 3  Code 
x_{1} x_{2} x_{3} x_{4} x_{5} 
0.2 0.2 0.2 0.2 0.2 
0 0 
0  
00 01 10 110 111 
1  
1 1 1 
0  
1 1 
0  
1 
equation
equation
The efficiency Ƞ is Ƞ = = 0.967 = 96.7% Ans.
(ii) Another ShannonFano code [by choosing another two approximately equiprobable (0.6 versus 0.4) sets] is constructed as follows (see Table 9.10)
Table 9.10.
x_{i}  P(x_{i})  Step 1  Step 2  Step 3  Code 
x_{1} x_{2} x_{3} x_{4} x_{5} 
0.2 02 02 02 02 
0 1 1 
0 1 1 1 
1 
00 010 011 10 11 
equation
Since the average codeword length is the same as that for the code of part (a), the efficiency is the same. Ans.
(iii) The Huffman code is constructed as follows (see Table 9.11)
equation
Since the average code word length is the same as that for the ShannonFano code, the efficiency is also the same.
Table 9.11.
table with diagram
EXAMPLE 9.46 A DMS X has five symbols x_{1}, x_{2}, x_{3}, x_{4}, and x_{5} with P(x_{1}) = 0.4, P(x_{2}) = 0.19, P(x_{3}) = 0.16, P(x_{4}) = 0.15, and P(x_{5}) = 0.1.
(i) Construct a ShannonFano code for X, and calculate the efficiency of the code.
(ii) Repeat for the Huffman code and compare the results.
Solution: The ShannonFano code is constructed as follows (see Table 9.12)
(xi)ni = 0.4(1) + 0.19(2) + 0.16(2) + 0.15(3) + 0.1(3) = 2.25
Also, Ƞ = = 0.956 = 9.5.6% Ans.
Table 9.12.
x_{i}  P(x_{i})  Step 1  Step 2  Step 3  Code 
x_{1} x_{2} x_{3} x_{4} x_{5} 
0.4 0.19 0.16 0.15 0.1 
0 1 1 1 
0 1 1 1 
1 
00 01 10 110 111 
(ii) The Huffman code is constructed as follows (see Table 9.13):
equation
or L = 0.4(1) + (0.19 + 0.16 + 0.15 + 0.1)(3) = 2.2 Ans.
Table 9.13.
table with diagram
op Ƞ =
or Ƞ = 0.977 = 97.7%
The average codeword length of the Huffman code is shorter than that of the ShannonFanco code, and thus the efficiency is higher than that of the ShannonFano code. Ans.
EXAMPLE 9.47. Determine the Huffman code for the following messages with their probabilities given
x_{1} x_{2} x_{3} x_{4} x_{5} x_{6} x_{7}
0.05 0.15 0.2 0.05 0.15 0.3 0.1
Solution: Arranging and groping of messages is done as shown below:
table and diagram
Message  Prob.  Code  No. of bits in code 
x_{1} x_{2} x_{3} x_{4} x_{5} x_{6} x_{7} 
0.05 0.15 0.2 0.05 0.15 03. 0.1 
1110 010 10 1111 011 00 110 
4 3 2 4 3 2 3 
⸫. Average length L is given by
equation
or L = 4(0.05 + 0.05) + 3(0.15 + 0.15 + 0.1) + 2(0.2 + 0.3) = 2.6 bits
Entropy H(X) is given by
equation
equation
= 2.57 bits
EXAMPLE 9.48. Define Average Mutual Information between two discrete random variables a show that it is nonnegative
(U.P. Tech, Sem. Exam, 200304) (05 marks)
Solution: Average Mutual Information
The extreme values of mutual information are 0 and log . Most transmission channels fall somewhere between these extreme values. To analyze the general case, we define the average mutual information as under:
equation
where x and y are two random variables
P(x_{i}/y_{j}) is the conditional probability of x_{i} ; provided y_{j}. occurs.
p(x_{i}) is the probability of x_{i}.
EXAMPLE 9.49. Design binary Huffman code for a discrete source of five independent symbols A, B, C, D and E with probabilities 0.4, 0.2, 0.8, 0.08 and 0.02 respectively such that the variance of codeword lengths is minimum.
(U.P. Tech, Sem. Exam, 200304) (05 Marks)
Solution: Huffman coding procedure can be carried out in the form of a table as under :
table and diagram
Therefore, in compact form, Huffman coding can be represented as under :
Symbol  Probability  Code word 
C  0.8  0 
A  0.4  10 
B  0.2  110 
D  0.08  1110 
E  0.02  1111 
We know that the average code word length is given by
equation
or L = 0.8 x 1 + 0.4 x 2 + 0.2 x 3+0.08 x 4+ 0.02 x 4
or L = 2.6. Ans.
Now , variance is given by
equation
or σ^{2} = 0.8 (12.6)^{2} + 0.4 (22.6)^{2} + 0.2 (32.6)^{2} + 0.08 (42.6)^{2}+ 0.02 (42.6)^{2}
or σ^{2} = 2.04 + 0.144 + 0.032 + 0.156 + 0.0392
or σ^{2} = 2.4112. Ans.
EXAMPLE 9.50. An event has six possible outocomes with probabilities
P_{1} = , P_{2} = , P_{3} = , P_{4} = , P_{5} = , and P_{6} =
Find the entropy of the system. Also find the rate of information if there are 16 outcomes per second. (U.P. Tech, Sem. Exam, 200203) (05 Mark)
Solution : Given that
P_{1} = , P_{2} = , P_{3} = , P_{4} = , P_{5} = , and P_{6} =
r = 16 outcomes/sec.
We know that the entropy is given by
equation
Substituting all the given values, we get
H = , log_{2} 2 + , log_{2} 4 + , log_{2} 8 + , log_{2} 16 + , log_{2} 32
or H = –
or H = 1.9375 bits/message.
We also know that information rate is given by
R = Entropy x message rate = H x r = 1.9375 x 16
or R = 31 bits/sec. Ans.
EXAMPLE 9.51. A discrete source transmits messages x_{1}, x_{2} and x_{3} with probabilities 0.3, 0.4 and 0.3. The source is connected to the channel given in figure 9.16. Calculate H(X) and H(Y). (U.P. Tech, Sem. Exam, 200203) (05 Marks)
Solution : Given that
P(x_{1}) = 0.3, P(x_{2}) = 0.4 and P(x_{3}) = 0.3
We know that the value of H(X) can be found as under :
equation
Substituting values, we get
EQUATION
diagram
FIGURE 9.16.
or H(X) = 0.52 + 0.52 + 0.52 = 1.568 bits/symbol.
The given figure shows conditional probability matrix in the form P as
P(YX) =
or P(X) = [0.3 0.4 0.3]
The P(X, Y) is obtained by multiplying P(YX) and P(X) as under:
P(X,Y) =
P(y_{1}) (y_{2}) and (y_{3}) are obtained by adding column of P(X,Y).
Therefore, we have
P(y_{1}) = 0.24 + 0 + 0 24
P(y_{2}) = 0.06+0.4+0.09 = 0.55
P(y_{3}) = 0+0+0.21 = 0.21
Now, the value of H(Y) can be obtained as under :
equation
or H(Y) = – [0.24 log_{2} 0.24 + 0.55 log_{2} 0.55 + 0.21 log_{2} 0.21]
or H(Y) = – [ 0.49 – 0.47 – 0.47]
or H(Y) = – 1.43 bits/symbol Ans.
EXAMPLE 9.52. Consider a discrete memoryless source with source alphabet = {S_{0}, S_{1}, S_{2}} and source statistics {0.7, 0.15, 0.15}
(i) Calculate the entropy of the source
(ii) Calculate the entropy of second order extension of the source.
(U.P. Tech, Sem. Exam, 200203) (05 Marks)
Solution : (i) We know that the entropy of discrete memoryless source is given by
equation
Substituting all the values, we get
equation
or H(X) = 0.36 + 0.41 + 0.41 = 1.1805 bits/symbol. Ans.
(ii) Now, the entropy of second order extension of the source can be evaluated as under:
The entropy of extended source is given by
H(X^{n}) = nH(X)
For second order, we have
H(X^{2}) = 2 x H(X) = 2 x 1.1805 = 2.361bits/symbol. Ans.
EXAMPLE 9.53. State HartleyShannon Law.
Solution : The HartelyShannon law states that the channel capacity of a white, bandlimited Gaussain channel is given by
C = B log_{2} bits/sec
where, B = channel bandwidth
P = signal power
DO YOU KNOW? 
The shannonHartley theorem is of fundamental importance and has two important implications for communication system engineers. 
N = noise within the channel bandwidth
Power, P = spectral density
Using above expression, the noise power N is as under :
equation
where is the power spectral density (psd) of the white noise.
Therefore, we write
N= N_{0}B
Using equations (i) and (ii), we obtain
C= B log_{2}
EXAMPLE 9.54. A source emits one of four symbols S_{0}, S_{1}, S_{2} and S_{3} with probabilities , , and respectively. The successive symbols emitted by the source are independent. Calculate the entropy of source.
(U.P. Tech, Sem. Exam, 200506) (05 Marks)
Solution : The given probabilities of the symbols are as under :
Symbol  S_{0}  S_{1}  S_{2}  S_{3} 
Probability 
We know that the expression for source entropy H(X) is given by
equation
Substituting all the given values, we get
equation
equation
equation
equation Ans.
EXAMPLE 9.55. Develope ShannonFano code for five messages given by probabilities , , . Calculate the average number of bits/message.
(U.P. Tech, Sem. Exam, 200506) (05 Marks)
Solution : Let the given messages be represented by x_{1}, x_{2}, x_{3}, x_{4} and x_{5}.
With the help of given probabilities, we can develop ShannonFano code in the form of a table as follows:
ShannonFano Coding
Message  Corresponding Probability  Step I  Step II  Step III  Step IV  Code Word  Length n_{i} 
x_{1}  1/2  0  Stop  0  1  
x_{2}  1/4  1  0  Stop  10  2  
x_{3}  1/8  1  1  0  Stop  110  3 
x_{4}  1/16  1  1  1  0  1110  4 
x_{5}  1/16  1  1  1  1  1111  4 
We know that the average number of bits per message is given by
equation
Substituting all the values, we get
equation
or L = = 1.875 bits Ans.