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

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 ⁿC₁ = n.
Number of double error patterns will be ⁿC₂
Number of triple error patterns will be ⁿC₃ …
Therefore, the corrections of t number of errors is possible if and only if the following expression is satisfied :
2^q – 1 ≥ ⁿC₁ + ⁿC₂ + ⁿC₃ + …ⁿC_t
or                                 2^q ≥ ⁿC₁ + 1 + ⁿC₂ + …ⁿC_t
or                                                  equation
But, q = n – k. Hence,      equation
Taking log₂ 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₀ c₁ c₂]_1×3 = [m₀ m₁ m₂ m₃]
Solving, we obtain
c₀ = m₀ Å m₁ Å m₂
we                                           c₁ = m₁ Å m₂ Å m₃
c₂ = m₀ Å m₁ Å m₃
Using these equations, we can obtain the parity bits for each message vector. For example, let the message word be
m₀ m₁ m₂ m₃= 0 1 0 1
Therefore, we write     c₀ = 0 Å 1 Å 0 = 1
c₁ = 1 Å 0 Å 1 = 0
c₂ = 0 Å 1 Å 1 = 0
Hence, the corresponding parity bits are c₀, c₁ c₂ = 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

 
(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₀, c₁, c₂] = [m₀, m₁, m₂, m₃]_1×4 [P]_4×3
Substituting the P matrix from equation (i), we can obtain the parity bits.
Hence,             [c₀, c₁, c₂] = [m₀, m₁, m₂, m₃]
Solving, we obtain
c₀ = m₀ Å m₁ Å m₂
c₀ = m₁ Å m₂ Å m₃
c₂ = m₀ Å m₁ Å m₃
Using these equations, we can obtain the parity bits for each message vector. For example, let the message word be
m₀ m₁ m₂ m₃ = 0 1 01
Therefore, we have
c₀ = m₀ Å m₁ Å m₂ = 0 Å 1 Å 0 = 1
c₁ = m₁ Å m₂ Å m₃ = 1 Å 0 Å 1 = 0
c₂ = m₀ Å m₁ Å m₃ = 0 Å 1 Å 0 = 1
Hence, the parity bits are c₀ c₁ c₂ = 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

 
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.