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:
- 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 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
| xi | P(xi) | Step 1 | Step 2 | Step 3 | Step 4 | Code |
| x1 x2 x3 x4 x5 x6 |
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, 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:
- 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 x1, x2, x3, and x4 with P(x1) = , P(x2) = , and P(x3) = P(x4) = . Construct a Shannon-Fano code for X ; show that this code has the optimum property that ni = I(xi) 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.
| xi | P(xi) | Step 1 | Step 2 | Step 3 | Code | |
| x1 x2 x3 x4 |
1/2 1/4 1/8 1/8 |
0 | 0 |
0 10 110 111 |
||
| 1 | 0 | |||||
| 1 1 |
1 1 |
|||||
| 1 |
I(x1) = -log2 = 1 = n1
I(x2) = -log2 = 2 = n2
I(x3) = -log2 = 3 = n3
I(x4) = -log2 = 3 = n4
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.
| xi | P(xi) | Step 1 | Step 2 | Step 3 | Code |
| x1 x2 x3 x4 x5 |
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 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.
| xi | P(xi) | Step 1 | Step 2 | Step 3 | Code |
| x1 x2 x3 x4 x5 |
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 Shannon-Fano code, the efficiency is also the same.
Table 9.11.
table with diagram
EXAMPLE 9.46 A DMS X has five symbols x1, x2, x3, x4, and x5 with P(x1) = 0.4, P(x2) = 0.19, P(x3) = 0.16, P(x4) = 0.15, and P(x5) = 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.
| xi | P(xi) | Step 1 | Step 2 | Step 3 | Code |
| x1 x2 x3 x4 x5 |
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 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
x1 x2 x3 x4 x5 x6 x7
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 |
| x1 x2 x3 x4 x5 x6 x7 |
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 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(xi/yj) is the conditional probability of xi ; provided yj. occurs.
p(xi) is the probability of xi.
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 :
| 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 (1-2.6)2 + 0.4 (2-2.6)2 + 0.2 (3-2.6)2 + 0.08 (4-2.6)2+ 0.02 (4-2.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
P1 = , P2 = , P3 = , P4 = , P5 = , and P6 =
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
P1 = , P2 = , P3 = , P4 = , P5 = , and P6 =
r = 16 outcomes/sec.
We know that the entropy is given by
equation
Substituting all the given values, we get
H = , log2 2 + , log2 4 + , log2 8 + , log2 16 + , log2 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 x1, x2 and x3 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(x1) = 0.3, P(x2) = 0.4 and P(x3) = 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(y1) (y2) and (y3) are obtained by adding column of P(X,Y).
Therefore, we have
P(y1) = 0.24 + 0 + 0 24
P(y2) = 0.06+0.4+0.09 = 0.55
P(y3) = 0+0+0.21 = 0.21
Now, the value of H(Y) can be obtained as under :
equation
or H(Y) = – [0.24 log2 0.24 + 0.55 log2 0.55 + 0.21 log2 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 = {S0, S1, S2} 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(Xn) = nH(X)
For second order, we have
H(X2) = 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 log2 bits/sec
where, B = channel bandwidth
P = signal power
| DO YOU KNOW? |
| The shannon-Hartley 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= N0B
Using equations (i) and (ii), we obtain
C= B log2
EXAMPLE 9.54. A source emits one of four symbols S0, S1, S2 and S3 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 :
| Symbol | S0 | S1 | S2 | S3 |
| 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 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 x1, x2, x3, x4 and x5.
With the help of given probabilities, we can develop Shannon-Fano code in the form of a table as follows:
Shannon-Fano Coding
| Message | Corresponding Probability | Step I | Step II | Step III | Step IV | Code Word | Length ni |
| x1 | 1/2 | 0 | Stop | 0 | 1 | ||
| x2 | 1/4 | 1 | 0 | Stop | 10 | 2 | |
| x3 | 1/8 | 1 | 1 | 0 | Stop | 110 | 3 |
| x4 | 1/16 | 1 | 1 | 1 | 0 | 1110 | 4 |
| x5 | 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.