ENTROPY CODING , shannon fano coding example and huffman coding entropy formula

shannon fano coding example and huffman coding entropy formula :-
ENTROPY CODING
The design of a variable-length 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)         Shanon-fano coding
(ii)        Huffman coding
9.20.1. Shannon-Fano Coding
An efficient code can be obtained by the following simple procedure, known as Shannon-Fano algorithm:

1. List the source symbols in order of decreasing probability.
2. 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.
3. Continue this process, each time partitioning the sets with as nearly equal probabilities as possible until further partitioning is not possible.

An example of Shannon-Fano encoding is shown in Table 9.6. Note in Shannon-Fano encoding the ambiguity may arise in the choice of approximately equiprobable sets.
Table 9.6. Shannon-Fano Encoding

 
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, 2003-04.2006-07) (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:

1. List the source symbols in order of decreasing probability.
2. 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.
3. 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.
4. 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.
5. 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₁, x₂, x₃, and x₄ with P(x₁) = , P(x₂) = , and P(x₃) = P(x₄) =  .  Construct a Shannon-Fano 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 Shannon-Fano code is constructed as follows (see Table 9.8).
*          Explain Huffman coding with the help of an example.
(U.P. Tech, Sem. Exam; 2006-07) (05 marks)
Table 9.8.

 
I(x₁) = -log₂ = 1 = n₁
I(x₂) = -log₂ = 2 = n₂
I(x₃) = -log₂ = 3 = n₃
I(x₄) = -log₂ = 3 = n₄
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 Shannon-Fano code for X, and calculate the efficiency of the code.
            (ii)        Construct another Shannon-Fano code and compare the results.
            (iii)       Repeat for the Huffman code and compare the results.
(Madras University, 1998)
Solution: A Shannon-Fano code [by choosing two approximately equiprobable (0.4 versus 0.6) sets] is constructed as follows (see Table 9.9)
Table 9.9.

 
equation
equation
The efficiency Ƞ is      Ƞ =  = 0.967 = 96.7%        Ans.
(ii)        Another Shannon-Fano code [by choosing another two approximately equiprobable (0.6 versus 0.4) sets] is constructed as follows (see Table 9.10)
Table 9.10.

 
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 Shannon-Fano code, the efficiency is also the same.
Table 9.11.
table with diagram
EXAMPLE 9.46 A DMS X has five symbols x₁, x₂, x₃, x₄, and x₅ with P(x₁) = 0.4, P(x₂) = 0.19, P(x₃) = 0.16, P(x₄) = 0.15, and P(x₅) = 0.1.
            (i)         Construct a Shannon-Fano code for X, and calculate the efficiency                   of the code.
            (ii)        Repeat for the Huffman code and compare the results.
Solution: The Shannon-Fano 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.

 
(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 Shannon-Fanco code, and thus the efficiency is higher than that of the Shannon-Fano code.                        Ans.
EXAMPLE 9.47. Determine the Huffman code for the following messages with their probabilities given
x₁         x₂         x₃         x₄         x₅         x₆         x₇
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

 
⸫.        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 non-negative
(U.P. Tech, Sem. Exam, 2003-04) (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 code-word lengths is minimum.
(U.P. Tech, Sem. Exam, 2003-04) (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 :

 
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         σ² = 0.8 (1-2.6)² + 0.4 (2-2.6)² + 0.2 (3-2.6)² + 0.08 (4-2.6)²+ 0.02 (4-2.6)²
or         σ² = 2.04 + 0.144 + 0.032 + 0.156 + 0.0392
or         σ² = 2.4112.                Ans.
EXAMPLE 9.50. An event has six possible outocomes with probabilities
P₁ = , P₂ = , P₃ = , P₄ = , P₅ = , and P₆ =
Find the entropy of the system. Also find the rate of information if there are 16 outcomes per second.                                       (U.P. Tech, Sem. Exam, 2002-03) (05 Mark)
Solution : Given that
P₁ = , P₂ = , P₃ = , P₄ = , P₅ = , and P₆ =
r = 16 outcomes/sec.
We know that the entropy is given by
equation
Substituting all the given values, we get
H = , log₂ 2 + , log₂ 4 + , log₂ 8 + , log₂ 16 + , log₂ 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₁, x₂ and x₃ 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, 2002-03) (05 Marks)
Solution : Given that
P(x₁) = 0.3, P(x₂) = 0.4 and P(x₃) = 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(Y|X) =
or                     P(X) = [0.3   0.4    0.3]
The P(X, Y) is obtained by multiplying P(Y|X) and P(X) as under:
P(X,Y) =
P(y₁) (y₂) and (y₃) are obtained by adding column of P(X,Y).
Therefore, we have
P(y₁) = 0.24 + 0 + 0 24
P(y₂) = 0.06+0.4+0.09 = 0.55
P(y₃) = 0+0+0.21 = 0.21
Now, the value of H(Y) can be obtained as under :
equation
or                     H(Y) =  – [0.24 log₂ 0.24 + 0.55 log₂ 0.55 + 0.21 log₂ 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₀, S₁, S₂} 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, 2002-03) (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ⁿ) = nH(X)
For second order, we have
H(X²) = 2 x H(X) = 2 x 1.1805 = 2.361bits/symbol.  Ans.
EXAMPLE 9.53. State Hartley-Shannon Law.
Solution : The Hartely-Shannon law states that the channel capacity of a white, bandlimited Gaussain channel is given by
C = B log₂  bits/sec
where,             B = channel bandwidth
P = signal power

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₀B
Using equations (i) and (ii), we obtain
C= B log₂
EXAMPLE 9.54. A source emits one of four symbols S₀, S₁, S₂ and S₃ with probabilities , ,  and  respectively. The successive symbols emitted by the source are independent. Calculate the entropy of source.
(U.P. Tech, Sem. Exam, 2005-06) (05 Marks)
Solution : The given probabilities of the symbols are as under :

 
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 Shannon-Fano code for five messages given by probabilities , ,   . Calculate the average number of bits/message.
(U.P. Tech, Sem. Exam, 2005-06) (05 Marks)
Solution : Let the given messages be represented by x₁, x₂, x₃, x₄ and x₅.
With the help of given probabilities, we can develop Shannon-Fano code in the form of a table as follows:
Shannon-Fano Coding

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.