Instantaneous Codes , Optimal Codes , The Kraft Inequality in digital communication

By   December 15, 2019

The Kraft Inequality in digital communication , Instantaneous Codes , Optimal Codes :-
9.19.3.6. Instantaneous Codes
            A uniquely decodable code is called an instantaneous code if the end of any codeword is recognizable without examining subsequent code symbols. The instantaneous codes have the property previously mentioned that no codeword is a prefix of another codeword. For this reason, prefix-free codes are sometimes known as instantaneous codes.
9.19.3.7. Optimal Codes
            A code is said to be optimal if it is instantaneous and has minimum average L for a given source with a given probability assuagement for the sourcesymbols.
9.19.4. The Kraft Inequality
            Let Xbe a DMS with alphabet {xi} (i = 1, 2, … m). Assume that the length of the assigned binary codeword corresponding to xi is ni.
A necessary and sufficient condition for the existence of an instantaneous binary code is
equation
which is known as the Kraft inequality.
NOTE: It may be noted that Kraft inequality assures us of the existence of an instantaneously decodable code with codeword lengths that satisfy the inequality. But it does not show us how to obtain these codewords, nor does it say any code satisfies the inequality is automatically uniquely decodable.
EXAMPLE 9.37. Given a DMS X with two symbols xl and x2 and P(xi) = 0.9, P(x2) = 0.1. Symbols x1, and x2 are encoded as follows (Table 9.3)
Table 9.3.

xi P(xi) Code
x1
x2
0.9
0.1
0
1

 
            Find the efficiency h and the redundancy γ of this code.
Solution: We know that the average code length L per symbol is
equaTion
We know that
equation
= -0.9 log2 0.9 – 0.1 log2 0.1 = 0.469 b/symbol
Also, the code efficiency h is
h =  = 0.469  = 46.9%
And, the code redundancy γ is given by
γ = 1 – h = 0.531 = 53.1%                   Ans.
EXAMPLE 9.38. The second-order extension of a DMS X, denoted by X2, is formed by taking the source symbols two at a time. The coding of this extension has been shown in Table 9.4. Find the efficiency h and the redundancy γ of this extension code.
Solution:                                                         Table 9.4.

ai P(ai) Code
a1 = x1x1
a2 = x1x2
a3 = x2x1
a4 = x2x2
0.81
0.09
0.09
0.01
0
10
110
111

 
We have  (ai)ni = 0.81(1) + 0.09(2) + 0.09(3) + 0.01(3) = 1.29 b/symbol
The entropy of the second-order extension of X, H(X2), is given by
equation
= – 0.81 log2 0.81 – 0.09 log2 0.09 – 0.09 log2 0.09- 0.01 log2 0.01
or         H(X2) = 0.938 b/symbol
Therefore, the code efficiency Ƞ is
Ƞ =  = 0.727 = 72.7%
Also, the code redundancy γ will be
γ = 1 – Ƞ = 0.273 = 27.3%       Ans.
EXAMPLE 9.39. Consider a DMS X with symbols xi, i = 1, 2, 3, 4. Table 9.5 lists four possible binary codes.
Table 9.5.

xi Code A Code B Code C Code D
x1
x2
x3
x4
00
01
10
11
0
00
11
110
0
10
11
110
0
100
110
111

 
            (i)         Show that all the codes except code B satisfy the Karft inequality.
            (ii)        Show that codes A and D are uniquely decodable but codes B and C are not uniquely decodable.
Solution: We have
(i)         For code A,                             n1 = n2 = n3 = n4 = 2
therefore,                                             Equation
For code B,                                         n1 = 1, n2 = n3 = 2, n4 = 3
therefore                                              Equation
For code C,                                         n1 = 1, n2 = 2, n3 = n4 = 3
therefore                                              Equation
For code D,                                         n1 = 1, n2 = n3 = n4 = 3
therefore,                                             equation
Thus, all codes except code B satisfy the Kraft inequality.
(ii)        Codes A and D are prefix-free codes. They are, therefore, uniquely decodable. Code B does not satisfy the Kraft inequality, and it is not uniquely decodable. Although code C does satisfy the Kraft inequality, but it is not uniquely decodable. This can be seen by the following example:
Given the binary sequence 0110110. This sequence may correspond to the source sequences x1x2x1x4 or x1x4x4.
EXAMPLE 9.40. Verify the following expression:
where L is the average codeword length per symbol and H(X) is the source entropy.                                                                                                  (Gate Examination-2000)
Solution: We know that
Equation
where the equality holds only if Qi = Pi.
Let                                                       Equation
where                                      Equation
Now, we have
            equation
and                                                      equation
            equation
= H(X) -L – log2 K < 0
From the Kraft inequlity (14.56), we have
log2 K < 0
Thus,                                       H(X) – L ≤  log2 K ≤ 0
or                                             L ≥ H(X)
The equality holds when K= 1 and Pi= Qi
EXAMPLE 9.41. Let X be a DMS with symbols xi and corresponding probabilities P(xi) = Pi, i = 1,2, …m. Show that for the optimum source encoding, we require that
Hence proved.
equation
            and                                          ni = log2  = Ii
            where ni is the length of the codeword corresponding to xi and Ii is the information content of xi.
Solution: From the result of last problem, the optimum source encoding with L = H(X) requires K = 1 and P = Qi. Thus, equations using (ii) and (i) of last problem, we have
equation
and                                          Pi = Qi = 2-ni
Hence                                      ni = -log2 Pi = log2
NOTE: Note that equation (ii) implies the following commonsense principle.
Symbols which occur with high probability should be assigned shorter codewords than symbols that occur with low probability.                                    Hence proved.
EXAMPLE 9.42. Consider a DMS X with symbols xi and corresponding probabilities P(xi) = Pi, i = 1, 2, … m. Let ni be the length of the codeword of xi such that
log2   ni ≤  log2
            Show that this relationship satisfies the Kraft inequality (9.56), and find the bound on K in equation (9.56).
Solution: Equation (i) can be rewritten as
– log2 Pi ≤ ni ≤ – log2 Pi +1
or                                 log2 Pi ≥ – ni ≥ log2 Pi – 1
Then                            2log2 Pi ≥ 2-ni ≥ 2log2 Pi 2-1
or                                 Pi ≥ 2-ni ≥  Pi
Thus                            Equation
or                                 equation
which indicates that the Kraft inequality (9.56) is satisfied, and the bound on K will be
≤ K ≤ 1                     Hence proved.
EXAMPLE 9.43. Consider a DMS X with symbols xi and corresponding probabilities P(xi) = Pi, i 1, 2, …,m. Show that a code constructed in agreement with equation (i) in last problem gill satisfy the following relation:
H(X) L H(X) + 1
            where H(X) is the source entropy and L is the average codeword length.
Solution: Multiplying equation (ii) in last problem by Pi and summing over i yields
equation
Now,                                           equation
Thus, equation (ii) reduces to
H(X) ≤ L ≤ H(X) + 1              Hence proved.

Leave a Reply

Your email address will not be published. Required fields are marked *