Hamming Bound , Hamming Bound , in information theory , liner block code whose generator matrix is given by

By   January 19, 2020

liner block code whose generator matrix is given by , Hamming Bound , Hamming Bound , in information theory :-
Hamming Bound
(i)         The number of non-zero distinct syndromes for an (a, k) block codes is (2n-k -1). If we substitute (n – k) = q, then the number of non-zero distinct syndromes will be 2q – 1.
(ii)        The number of single error patterns will be nC1 = n.
Number of double error patterns will be nC2
Number of triple error patterns will be nC3
Therefore, the corrections of t number of errors is possible if and only if the following expression is satisfied :
2q – 1 ≥ nC1 + nC2 + nC3 + …nCt
or                                 2qnC1 + 1 + nC2 + …nCt
or                                                  equation
But, q = n – k. Hence,      equation
Taking log2 of both the sides, we obtain
equation
Dividing both the sides of above expression by n, we obtain
equation
But,   = r, i.e., the code rate.
Therefore,                                    equation
NOTE Above expression gives the relation between the code rate r, number of correctable errors t, number of bits per word n. As the number of correctable errors is related to the Hamming distance, the expression is called as the Hamming Bound.
EXAMPLE 10.11. Given a (7, 4) liner block code whose generator matrix is given by :
G = 
            (i) Find all the code words.   (ii) Find the parity check matrix.
Solution :
(i)         First, we obtain the P matrix from the generator matrix.
(ii)        Then, we obtain the parity bits for each message vector using the expression,
C = MP
(iii)       Next, we obtain all the possible code words as
X=[M : C]
(iv)       Lastly, we obtain the transpose of P matrix i.e. PT and obtain the                             parity check matrix as :
[H] = [M : C]
(i)        First, let us obtain the P matrix.
Given generator matrix G = equation
Therefore, the P matrix is given by
P =                                                        …(i)
(ii)        Next, we obtain the parity (i.e., check) bits
The parity bits can be obtained by using the following expression :
C = MP
or                                 [c0 c1 c2]1×3 = [m0 m1 m2 m3]
Solving, we obtain
c0 = m0 Å m1 Å m2
we                                           c1 = m1 Å m2 Å m3
c2 = m0 Å m1 Å m3
Using these equations, we can obtain the parity bits for each message vector. For example, let the message word be
m0 m1 m2 m3= 0 1 0 1
Therefore, we write     c0 = 0 Å 1 Å 0 = 1
c1 = 1 Å 0 Å 1 = 0
c2 = 0 Å 1 Å 1 = 0
Hence, the corresponding parity bits are c0, c1 c2 = 1 0 0
Therefore, the complete codeword for the message word 0 1 0 1 is given by
diagram
Similarly, we can obtain the codewords for the remaining message words. All the message vectors, the corresponding parity bits and codewords are given in table 10.9. The code weights are also given in the table 10.9.
Table 10.9. Code vectors for all the message vectors

S.N. Message vector, M Parity bits, C Code words, X
  m3 m2 m1 m0 c2 c1 c0 X6 X5 X4 X3 X2 X1 X0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 0 0 0 1 1 0 1 0 0 0 1 1 0 1
3 0 0 1 0 0 1 1 0 0 1 0 0 1 1
4 0 0 1 1 0 1 0 0 0 1 1 0 1 0
5 0 1 0 0 0 1 1 0 1 0 0 0 1 1
6 0 1 0 1 1 1 0 0 1 0 1 1 1 0
7 0 1 1 0 1 0 0 0 1 1 0 1 0 0
8 0 1 1 1 0 0 1 0 1 1 1 0 0 1
9 1 0 0 0 1 1 0 1 0 0 0 1 1 0
10 1 0 0 1 0 1 1 1 0 0 1 0 1 1
11 1 0 1 0 0 0 1 1 0 1 0 0 0 1
12 1 0 1 1 1 0 0 1 0 1 1 1 0 0
13 1 1 0 0 1 0 1 1 1 0 0 1 0 1
14 1 1 0 1 0 0 0 1 1 0 1 0 0 0
15 1 1 1 0 0 1 0 1 1 1 0 0 1 0
16 1 1 1 1 1 1 1 1 1 1 1 1 1 1

 
(iv)       Lastly, let us obtain the parity check matrix.
The parity check matrix [H] is a 3 x 7 matrix, i.e.,
H = [PT : In – k]
The transpose matrix PT is given by
PT =
Therefore, we have     H = [PT : I3 x3] =                       equation  Ans.
This is the required parity check matrix.
EXAMPLE 10.12. A (7, 4) linear block code of which generator matrix is given by
G = 
            (i)         Find code vector for any six messages
            (ii)        Write the parity check matrix of this code.
Solution : The generator matrix G is a k x n matrix. So, here it will be a 4 x 7 matrix in the followinv format
Therefore, we have                 G = [Ik | P]
where Ik is a k x k , i.e., 4 x 4 matrix.
Hence, we have
G =
Now, let us obtain the parity bits for each message
The parity bits can be obtained by using the following expression:
C = MP
or                                 [c0, c1, c2] = [m0, m1, m2, m3]1×4 [P]4×3
Substituting the P matrix from equation (i), we can obtain the parity bits.
Hence,             [c0, c1, c2] = [m0, m1, m2, m3]
Solving, we obtain
c0 = m0 Å m1 Å m2
c0 = m1 Å m2 Å m3
c2 = m0 Å m1 Å m3
Using these equations, we can obtain the parity bits for each message vector. For example, let the message word be
m0 m1 m2 m3 = 0 1 01
Therefore, we have
c0 = m0 Å m1 Å m2 = 0 Å 1 Å 0 = 1
c1 = m1 Å m2 Å m3 = 1 Å 0 Å 1 = 0
c2 = m0 Å m1 Å m3 = 0 Å 1 Å 0 = 1
Hence, the parity bits are c0 c1 c2 = 1 0 0
Therefore, the complete codeword for the message word 0 1 0 0 is
equation
Similarly, we can obtain the codewords for other message vectors shown in table 10.10.
Table 10.10

S.N. Message vector Parity bits Code words
  m0 m1 m2 m3 c0 c1 c2 X0 X1 X2 X3 X4 X5 X6
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 1 0 0 0 1 0 1 1 0 0 0 1 0 1
3 0 1 0 0 1 1 1 0 1 0 0 1 1 1
4 0 0 1 0 1 1 0 0 0 1 0 1 1 0
5 0 0 0 1 0 1 1 0 0 0 1 0 1 1
6 0 1 0 1 1 0 0 0 1 0 1 1 0 0

 
Now, the parity check matrix is given by
[H]3×7 = [PT | In-k]
where PT is the transpose of P and In-k is I3×3 matrix.
We can obtain the transpose of P by interchanging the row and columns of P matrix in equation (i) i.e.,
PT =
Therefore, the parity check matrix is given by
H =                 Ans.
This is the required parity check matrix.

Leave a Reply

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