For a systematic linear block code, the three parity check digits, c4, c5 and c6 are given by

EXAMPLE 10.13. For a systematic linear block code, the three parity check digits, c₄, c₅ and c₆ are given by
                                                C₄ = m₁ Å m₂ Å m₃
                                                c₅ = m₁ Å m₂
                                                c₆= m₁ Å m₃
             (i)        Construct generator matrix.
            (ii)        Construct code generated by this matrix.
            (iii)       Determine error correcting capability.
            (iv)       Prepare a suitable decoding table.
            (v)        Decode the received words 101100 and 000110.
Solution : (i) First, we parity matrix P and using it, obtain the generator matrix G.
(ii)        Then, we obtain the values of c₄, c₅, c₆ for various combinations of m_l, m₂, m₃ and obtain all the possible codewords.
(iii)       Next, we obtain d_min and from the value of d_min, we calculate the error detecting and correcting capability.
(iv)       After that, we obtain the decoding table by following the steps given below :
(a)        We, obtain the transpose of the parity check matrix H^T
(b)        We, calculate Syndrome S = EH^T
(c)        We, write the decoding table.
(v)        Lastly, we decode the received words with the help of syndromes listed in the decoding table.
(i)         First, let us obtain the parity matrix P and generator matrix G.
We know that the relation between the check (parity) bits, message bits and the parity matrix P is given by :
[c₄ c₅ c₆]_1×3 = [m₁, m₂, m₃]_1×3 [P]_3×3
[c₄ c₅ c₆] = [m₁, m₂, m₃]
Therefore, we have     C₄ = P₁₁ m₁ Å P₂₁ m₂  P₃₁ m₃
C₅ = P₁₂ m₁ Å P₂₂ m₂  P₃₂ m₃
C₆ = P₁₃ m₁ Å P₂₃ m₂  P₃₃ m₃
Comparing equation (iii) with the given equations for c₄, c₅, c₆, we obtain
P₁₁ = 1 P₁₂ = 1             P₁₃ = 1
P₂₁ = 1 P₂₂ = 1             P₂₃ = 1
P₃₁ = 1 P₃₂ = 1             P₃₃ = 1
Hence, the parity matrix is as shown below :
P =
This is the required parity matrix. The generator matrix is given by :
G = [I_k : P] = [I₃ : P_3×3]
Equation
(ii)       Now, let us obtain the codewords
It is given that,
c₄ = m₁ Å m₂ Å m₃
c₅ = m₁ Å m₂
c₆ = m₁ Å m₃
Using the equations, we can obtain the check bits for various combinations of the bits m_l, m₂ and m₃. After that the corresponding codewords are obtained as shown in table 10.10.
For, m₁ m₂ m₃ = 0 0 1, we have
c₄ = m₁ Å m₂ Å m₃ = 0 Å 0 Å 1 = 1
c₅ = m₁ Å m₂  = 0 Å 0 = 0
c₆ = m₁ Å m₃ = 0 Å 1 = 1
Therefore,                    c₄ c₅ c₆ = 101 and the codeword is given by :

 
 
 
Similarly, the other codewords are obtained. They are listed in table 10.11.
Table 10.11. Codewords

 
(iii)       Now, let find the error correcting capacity.
The error correcting capacity depends on the mimumum distance d_min. From table 10.10, d_min = 3.
Therefore, number of errors detectable is d_min > s + 1
or                                                         3 ≥ s + 1          or x ≤ 2.
So, at the most, two errors can be detected.
and                                                      d_min ≥ 2t + 1
or                                                         3 > 2t + 1,                   or t ≤ 1.
Thus, at the most one error can be corrected.
(iv)       Now, let us find the decoding table.
To write the decoding table, we have to calculate the syndrome (S) i.e.,
S = EH^T
where E = Error vector and H^T = transpose of parity check matrix.
So, let us first obtain the transpose of matrix H.
H = [P^T : I_n-k]_n-k,n
Therefore, the transpose of parity check matrix is given by
H^T =
Substituting the P matrix and the identity matrix, we obtain
H^T =
The error vector E is a 1 x 6 size vector. Assuming the second bit in error, we can get the error vector as under:
E = [0 ① 0 0 0 0]
where the encircled bit shows the bit in error
Hence, the syndrome is given by,
S = EH^T = [0 ① 0 0 0 0]
Therefore,
S = [0 Å 1 Å 0 Å 0 Å 0 Å 0, 0 Å 1 Å 0 Å 0 Å 0 Å 0, 0 Å 0 Å 0 Å 0 Å 0 Å 0]
or                                 S = [1 1 0]
This is the syndrome corresponding to second bit in error. Observe carefully that it is same as ‘the second row of the H^T matrix. The other syndromes can be obtained directly from the rows of H^T. The decoding table consisting of the error patterns and corresponding syndrome vectors is shown in Table 10.12.
Table 10.12. Decoding Table

 
(v)        Let us obtain the decoding of the received words.
The first given codeword is 101100. But, this codeword does not exist in the codeword table. This shows that the error must be present in the received code vector. Let us represent the received code word as under :
Y₁ = [1 0 1 1 0 0]
The syndrome for this codeword is given by,
S = Y₁ H^T
or                     S = [1 0 1 1 0 0]
S = [1 Å 0 Å 1 Å 1 Å 0 Å 0, 1 Å 0 Å 0 Å 0 Å 0 Å 0, 1 Å 0 Å 1 Å 0 Å 0 Å 0]
or                     S = [1 1 0]
Thus, the syndrome of the received word is [1 1 0] which is same as the second syndrome in the decoding table. Hence, the corresponding error pattern is given by
E = [0 j 0 0 0 0]
And the correct word can be obtained as under
X₁ = Y₁ Å E = [1 0 1 1 0 0] Å [0 1 0 0 0]
or                        X₁ = [1 1 1 1 0 0]
This is the correct transmitted word.
Similarly, we can perform the decoding of 000110.
Let X₂ = 000110 ………..  is the second received codeword. Even this is not the valid codeword listed in codeword table (Table 10.10). The syndrome for this can be obtained as under :
S= Y₂ H^T
or                                 S = [1 0 1 1 0 0]
or                                 S = [1 1 0]
The error pattern corresponding to this syndrome is obtained from the decoding table as under :
E=[0 j 0 0 0 0]
Therefore, the correct codeword is given by,
X₂= Y₂ Å E=[0 0 0 1 1 0] Å [0 1 0 0 0 0]
or                     X₂ = [0 1 0 1 1 0]
This is the correct transmitted word.              Ans.
EXAMPLE 10.14. The generator polynomial of a (15, 11) Hammind code is given by :
                                                            g(x) = 1 + x + x⁴
            Develop encoder and syndrome calculator for this code using systematic form.
Solution : Encoder
The given code is (15, 11) Hamming code. With the generator polynomial g(x) =1 + x + x⁴. As this is a (n, k) block code, we have
n = 15,                        k = 11
so                                 n – k = 4
The given generator polynomial can be expressed as
g(D) = 1 + D + D⁴ = D⁴ + 0D³ + 0D² + D + 1            …(i)
Generally, the generator polynomial is given by
g(D) = D⁴ + g³ D³ + g₂ D² + g₁ D + 1                      …(ii)
Comparing equations (i) and (ii), we obtain
g₃ = 0, g₂ = 0 and        g₁ = 1.
Therefore, the block diagram of (15, 11) Hamming encoder is shown in figure 10.27. Here, g₂ and g₃ are multiplying coefficients. As g₃ = g₂ = 0, the corresponding links are open while g₁= 1 represents a short link.
diagram
FIGURE 10.27 Encoder for the (15, 11) Hamming code.
Syndrome Calculator
The syndrome calculator for the (15, 11) Hamming code is shown in figure 10.28.
diagram
FIGURE 10.28 Syndrome calculator for (15, 11) Hamming code.
The flip-flops connected in figure 10.28 contain the four bit syndrome vector. The switch on the output side is kept in position 1 initially and all the bits of the received codeword Y are shifted into the shift register. Then shift the output switch to position 2 to output the syndromes.
EXAMPLE 10.15. The parity check matrix of a (7, 4) linear block code is given by
H =
            (i)         Find the generator matrix
            (ii)        List all code words
            (iii)       For the received codeword, R = 1011110, find the syndrome.
Solution : Solve yourself.
EXAMPLE 10.16. The parity check bits of a (8, 4) block code are generated by :
c₅ = m₁ + m₂ + m₄
c₆ = m₁ + m₂ + m₃
c₇ = m₁ + m₃ + m₄
c₈ = m₂ + m₃ + m₄
            where m₁, m₂, m₃ and m₄ are the message digits.
            (i)         Find the generator matrix and the parity check matrix for this code.
            (ii)        Find the minimum weight of this code.
            (iii)       Find the error detecting capabilities of this code.
            (iv)       Show through an example that this code can detect three errors.
Solution : (i)   First, we obtain the coefficient matrix P.
(ii)        Then, we obtain the generator matrix G and parity check matrix H.
(iii)       Next, we obtain the values of c₅, c₈, c₇ and c₈ for various values of m₁ m₂, m₃, m₄.
(iv)       We obtain all the possible codewords and then calculate the minimum weight.
(v)        We obtain d_min and calculate the error detecting and correcting capacity.
(vi)       Lastly, we shall show that 3 errors can be detected.
(i)         First, let us obtain the coefficient matrix P.
The relation between the check (parity) bits, message bits and coefficient matrix P is given by :
[c₅ c₆ c₇ c₈]_1×4 = [m₁ m₂ m₃ m₄]_1×4 [P]_4×4                              …(i)
or                     [c₅ c₆ c₇ c₈] = [m₁ m₂ m₃ m₄]
or                                 c₅ = P₁₁ m₁ Å P₂₁ m₂ Å P₃₁ m₃  Å P₄₁ m₄
c₆ = P₁₂ m₁ Å P₂₂ m₂ Å P₃₂ m₃  Å P₄₂ m₄                       …(ii)
c₇ = P₁₃ m₁ Å P₂₃ m₂ Å P₃₃ m₃  Å P₄₄ m₄
c₈ = P₁₄ m₁ Å P₂₄ m₂ Å P₃₄ m₃  Å P₄₄ m₄
Comparing equation (ii) with the given equations for c₅, c₆, c₇ and c₈, we obtain
P₁₁ = 1             P₁₂ = 1 P₁₃ = 0 P₁₄ = 1
P₂₁ = 1             P₂₂ = 1 P₂₃ = 0 P₂₄ = 1
P₃₁ = 1             P₃₂ = 1 P₃₃ = 0 P₃₄ = 1
P₄₁ = 1             P₄₂ = 1 P₄₃ = 0 P₄₄ = 1
Hence, the coefficient matrix is given by :
P =
(ii)        Next, we obtain the generator matrix G and parity check matrix H.
The generator matrix is given by :
G = [I_k : P]
But, k = 4, therefore, we have
equation
Now, the parity check matrix is given by :
H = [P^T : I_n-k]
But                                          P^T =
Therefore, we have
equation
(iii)       Next, we obtain the values of c₅, c₆, c₇, c₈ for different values of m₁ m₂ m₃ m₄ :
It is given that,
c₅ = m₁ Å m₂ Å m₄
c₆ = m₁ Å m₂ Å m₃
c₇ = m₁ Å m₃ Å m₄
c₈ = m₁ Å m₃ Å m₄
(iv)       Next, let us obtain all the codewords.
The remaining codewords are listed in table 10.13.
Table 10.13. Codewords

 
From Table 10.13, the minimum weight of this code is 4.
⸫                                 S = [0, 0, 1, 0]
(v)        Now, let us obtain d_min and calculate error detecting and correcting capacity.
The minimum distance d_min is equal to the minimum weight of any non-zero code vector. Looking at table 10.13, we obtain
d_min = 4.                       Ans.
Therefore, number of errors dectable is given by
d_min ≥ s + 1
or                                                    4 ≥ s + 1
or                                                     s ≤ 3.                   Ans.
Hence, at the most three errors can be detected.
Number of errros that can be corrected is given by
d_min ≥ (2t + 1)
or                                             4 ≥ (2t + 1)
or                                             t  ≤ 3/2            Ans.
Therefore, at the most 1 error can be corrected.         Ans
(vi)       Now, let us show that 3 errors can be detected.
A non-zero syndrome indicates the presence of errors. Hence, let us show that if upto three errros are introduced, then the syndrome is non-zero.
Let the transmitted code word be X= (0 0 1 0 0 1 1 1)
Let there be three errors introduced. Hence, the error vector E is given by
diagram
The required signal Y = X Å E
diagram
The corresponding syndrome is given by S = YH^T
or                                             S = [1 0 1 1 0 0 1 1]
or                                             S = [1 Å 0 Å 1 Å 0 Å 0 Å 0 Å 0 Å 0,
1 Å 0 Å 0 Å 1 Å 0 Å 0 Å 0 Å 0,
0 Å 0 Å 1 Å 1 Å 0 Å 0 Å 1 Å 0,
1 Å 0 Å 1 Å 1 Å 0 Å 0 Å 0 Å 1
Substituting the values of m_l, m₂, m₃ and m₄, we obtain the various codewords as under.
If                     m₁ m₂ m₃ m₄ = 0 0 0 1
Then                                        c₅ =  0 Å 0 Å 1 = 1
c₆ =  0 Å 0 Å 0 = 0
c₇ =  0 Å 0 Å 1 = 1
c₈ =  0 Å 0 Å 1 = 1
Hence the codeword is           X = m₁ m₂ m₃ m₄                     c₅ c₆ c₇ c₈
Therefore                                             diagram
Thus, the syndrome is non-zero indicating the presence of errors even when            three errros introduced. Therefore, it is possible to detect three errors.
EXAMPLE 10.17. Given a systematic block code whose parity check equations are :
c₁ = m₁ + m₂ + m₄
c₂ = m₁ + m₃ + m₄
c₃ = m₁ + m₂ + m₃
c₄ = m₂ + m₃ + m₄
            where m_i are the message digits and c_i are the parity digits.
            (i)         Find the generator matrix and the parity check matrix for this                           code
            (ii)        How many errors can be detected and corrected ?
            (iii)       If the received code word is 10101010, find the syndrome.
Solution : (i) The relation between the parity (check) bits, message bits and coefficient matrix P is given by
[c₁ c₂ c₃ c₄]_1×4 =  [m₁ m₂ m₃ m₄]_1×4 = [P]_4×4
or                     [c₁ c₂ c₃ c₄] = [m₁ m₂ m₃ m₄]
or                                 c₁ = P₁₁ m₁ Å P₂₁ m₂ Å P₃₁ m₃  Å P₄₁ m₄
c₂ = P₁₂ m₁ Å P₂₂ m₂ Å P₃₂ m₃  Å P₄₂ m₄                       …(ii)
c₃ = P₁₃ m₁ Å P₂₃ m₂ Å P₃₃ m₃  Å P₄₄ m₄
c₃ = P₁₄ m₁ Å P₂₄ m₂ Å P₃₄ m₃  Å P₄₄ m₄
Comparing equation (ii) with the given equations we obtain
P₁₁ = 1             P₁₂ = 1 P₁₃ = 0 P₁₄ = 1
P₂₁ = 1             P₂₂ = 0 P₂₃ = 1 P₂₄ = 1
P₃₁ = 1             P₃₂ = 1 P₃₃ = 1 P₃₄ = 0
P₄₁ = 0             P₄₂ = 1 P₄₃ = 1 P₄₄ = 1
Hence, the coefficient matrix is given by :
P =
Now, the generator matrix is given by
G = [I_k : P]
But,     k = 4    and      Ik = Identity matrix
Therefore, we have                 equation
This is required generator matrix.
The parity check matrix is given by,
H = [P^T :I_n-k]
But                              P^T =
and                              I_n-k = I₄ =
Hence, the parity check matrix is given by
equation
(iii)       Now, let us find the number of errros detectable and correctable.
It can be shown that the mimumum weight of this code is 4. The minimum distance d_min is equal to the minimum weight of any non-zero code vector.
⸫                                             d_min = 4
Number of errros dectable is given by
d_min > s + 1
or                                             4 ≥ s + 1
or                                             s < 3.               Ans.
Hence, at the most 3 errors can be detected.
Also, number of errros that can be corrected is given by
d_min > (2t + 1)
or                                 4 ≥ (2t + 1)
or                                 t ≤ 3/2.                         Ans.
Hence at the most 1 error can be corrected.
(iii)       Lastly, let us obtain the syndrome.
The syndrome is given by,
S = YH^T
where Y= Received codeword = 10 10 10 10
We have                      S = [1 0 1 0 1 0 1 0]
S = [1 Å 0 Å 1 Å 0 Å 1 Å 0 Å 0 Å 0,
1 Å 0 Å 1 Å 0 Å 0 Å 0 Å 0 Å 0,
0 Å 0 Å 1 Å 0 Å 0 Å 0 Å 1 Å 0,
1 Å 0 Å 0 Å 0 Å 0 Å 0 Å 0 Å 0]
or                                                         S = [1, 0, 0, 1] Ans.
This is the required syndrome.
EXAMPLE 10.18. For a (6, 3) code, the generator matrix G is given by :
G =
            (i)         Realize an encoder for this code.
            (ii)        Verify that this code is a single error-correcting code.
            (iii)       If the received codeword is 100 011, find the syndrome.
Solution :        (i) First, we obtain the expressions for the parity bits.
The parity bits can be obtained by using the expression :
C = MP
or                                             [c₀, c₁, c₂]_1×3 = [m₀ m₁ m₂]_1×3 [P]_3×3
The parity matrix can be obtained from the generator matrix as under :
equation
Therefore,                    [P] =
Also,                            [c₀, c₁, c₂] = [m₀, m₁, m₂]
From above, we get
c₀ = m₀ Å m₂
c₁ = m₁ Å m₂
c₂ = m₀ Å m₁
Now, let us draw the encoder.
The encoder is obtained to implement the expressions given in equation (i) as shown in Figure 10.29.
diagram
FIGURE 10.29 Encoder block diagram.
(ii)        It can be proved that the minimum distance for the (6, 3) code is given by
d_min = 3
Therefore, number of errros can be corrected will be
d_min ≥ 2t + 1
or                                                  3 ≥ 2t + 1
or                                                   t ≤ 1
Thus, at the most one error can be corrected.
(iii)       To obtain the syndrome, let us obtain the transpose matrix H^T.
Again, first we have to obtain the parity check matrix H as under :
H= [P^T : I_n-k]
Here, n – k = 3 and let us obtain P^T from generator matrix.
equation
Hence, we know the P matrix.
Thus, we have                                     PT =
Hence, the parity check matrix H will be
equation
Now, let us obtain the transpose matrix H^T as under :
H^T =
We know that the syndrome is given by
Syndrome S = Y H^T
or                                 S = [1 0 0 0 11]  = [1 1 1]              Ans.