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 (2^{n-k} -1). If we substitute (n – k) = q, then the number of non-zero distinct syndromes will be 2^{q} – 1.
(ii) The number of single error patterns will be ^{n}C_{1} = n.
Number of double error patterns will be ^{n}C_{2}
Number of triple error patterns will be ^{n}C_{3} …
Therefore, the corrections of t number of errors is possible if and only if the following expression is satisfied :
2^{q} – 1 ≥ ^{n}C_{1} + ^{n}C_{2} + ^{n}C_{3} + …^{n}C_{t}
or 2^{q} ≥ ^{n}C_{1} + 1 + ^{n}C_{2} + …^{n}C_{t}
or equation
But, q = n – k. Hence, equation
Taking log_{2} 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. P^{T} 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 [c_{0} c_{1} c_{2}]_{1×3} = [m_{0} m_{1} m_{2} m_{3}]
Solving, we obtain
c_{0} = m_{0} Å m_{1} Å m_{2 }
we c_{1} = m_{1} Å m_{2} Å m_{3}
c_{2} = m_{0} Å m_{1} Å m_{3 }
Using these equations, we can obtain the parity bits for each message vector. For example, let the message word be
m_{0} m_{1} m_{2} m_{3}= 0 1 0 1
Therefore, we write c_{0} = 0 Å 1 Å 0 = 1
c_{1} = 1 Å 0 Å 1 = 0
c_{2} = 0 Å 1 Å 1 = 0
Hence, the corresponding parity bits are c_{0}, c_{1} c_{2} = 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 | |||||||||||
m_{3} | m_{2} | m_{1} | m_{0} | c_{2} | c_{1} | c_{0} | X_{6} | X_{5} | X_{4} | X_{3} | X_{2} | X_{1} | X_{0} | |
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 = [P^{T} : I_{n – k}]
The transpose matrix P^{T} is given by
PT =
Therefore, we have H = [P^{T} : I_{3 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 = [I_{k} | P]
where I_{k} 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 [c_{0}, c_{1}, c_{2}] = [m_{0}, m_{1}, m_{2}, m_{3}]_{1×4 }[P]_{4×3}
Substituting the P matrix from equation (i), we can obtain the parity bits.
Hence, [c_{0}, c_{1}, c_{2}] = [m_{0}, m_{1}, m_{2}, m_{3}]
Solving, we obtain
c_{0} = m_{0} Å m_{1} Å m_{2}
c_{0} = m_{1} Å m_{2} Å m_{3}
c_{2} = m_{0} Å m_{1} Å m_{3}
Using these equations, we can obtain the parity bits for each message vector. For example, let the message word be
m_{0} m_{1} m_{2} m_{3 }= 0 1 01
Therefore, we have
c_{0} = m_{0} Å m_{1} Å m_{2} = 0 Å 1 Å 0 = 1
c_{1} = m_{1} Å m_{2} Å m_{3} = 1 Å 0 Å 1 = 0
c_{2} = m_{0} Å m_{1} Å m_{3} = 0 Å 1 Å 0 = 1
Hence, the parity bits are c_{0} c_{1} c_{2} = 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 | |||||||||||
m_{0} | m_{1} | m_{2} | m_{3} | c_{0} | c_{1} | c_{2} | X_{0} | X_{1} | X_{2} | X_{3} | X_{4} | X_{5} | X_{6} | |
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 | I_{n-k}]
where P^{T} is the transpose of P and I_{n-k} is I_{3×3 }matrix.
We can obtain the transpose of P by interchanging the row and columns of P matrix in equation (i) i.e.,
P^{T} =
Therefore, the parity check matrix is given by
H = Ans.
This is the required parity check matrix.