EXAMPLE 10.13. For a systematic linear block code, the three parity check digits, c4, c5 and c6 are given by
C4 = m1 Å m2 Å m3
c5 = m1 Å m2
c6= m1 Å m3
(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 c4, c5, c6 for various combinations of ml, m2, m3 and obtain all the possible codewords.
(iii) Next, we obtain dmin and from the value of dmin, 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 HT
(b) We, calculate Syndrome S = EHT
(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 :
[c4 c5 c6]1×3 = [m1, m2, m3]1×3 [P]3×3
[c4 c5 c6] = [m1, m2, m3]
Therefore, we have C4 = P11 m1 Å P21 m2 P31 m3
C5 = P12 m1 Å P22 m2 P32 m3
C6 = P13 m1 Å P23 m2 P33 m3
Comparing equation (iii) with the given equations for c4, c5, c6, we obtain
P11 = 1 P12 = 1 P13 = 1
P21 = 1 P22 = 1 P23 = 1
P31 = 1 P32 = 1 P33 = 1
Hence, the parity matrix is as shown below :
P =
This is the required parity matrix. The generator matrix is given by :
G = [Ik : P] = [I3 : P3×3]
Equation
(ii) Now, let us obtain the codewords
It is given that,
c4 = m1 Å m2 Å m3
c5 = m1 Å m2
c6 = m1 Å m3
Using the equations, we can obtain the check bits for various combinations of the bits ml, m2 and m3. After that the corresponding codewords are obtained as shown in table 10.10.
For, m1 m2 m3 = 0 0 1, we have
c4 = m1 Å m2 Å m3 = 0 Å 0 Å 1 = 1
c5 = m1 Å m2 = 0 Å 0 = 0
c6 = m1 Å m3 = 0 Å 1 = 1
Therefore, c4 c5 c6 = 101 and the codeword is given by :
| Codeword for m1 m2 m3 = 0 0 1 = | m1 | m2 | m3 | c4 | c5 | c6 |
| 0 | 0 | 1 | 1 | 0 | 1 |
Similarly, the other codewords are obtained. They are listed in table 10.11.
Table 10.11. Codewords
| S.N. | Message vector | Check bits | Code vectors or codewords | Code weight W(X) |
|||||||||
| m1 | m2 | m3 | c4 | c5 | c6 | m1 | m2 | m3 | c4 | c5 | c6 | ||
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 3 |
| 3 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 3 |
| 4 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 4 |
| 5 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 4 |
| 6 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 3 |
| 7 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 3 |
| 8 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 4 |
(iii) Now, let find the error correcting capacity.
The error correcting capacity depends on the mimumum distance dmin. From table 10.10, dmin = 3.
Therefore, number of errors detectable is dmin > s + 1
or 3 ≥ s + 1 or x ≤ 2.
So, at the most, two errors can be detected.
and dmin ≥ 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 = EHT
where E = Error vector and HT = transpose of parity check matrix.
So, let us first obtain the transpose of matrix H.
H = [PT : In-k]n-k,n
Therefore, the transpose of parity check matrix is given by
HT =
Substituting the P matrix and the identity matrix, we obtain
HT =
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 = EHT = [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 HT matrix. The other syndromes can be obtained directly from the rows of HT. The decoding table consisting of the error patterns and corresponding syndrome vectors is shown in Table 10.12.
Table 10.12. Decoding Table
| S. No. | Error vector E (with single bit error pattern) | Syndrome vectors | Relation with HT |
| 1 | 0 0 0 0 0 0 0 | 0 0 0 | |
| 2 | ① 0 0 0 0 0 0 | 1 1 1 | 1st Row of HT |
| 3 | 0 ① 0 0 0 0 0 | 1 1 0 | 2n Row of HT |
| 4 | 0 0 ① 0 0 0 0 | 1 0 1 | 3rd Row of HT |
| 5 | 0 0 0 ① 0 0 0 | 1 0 0 | 4th Row of HT |
| 6 | 0 0 0 0 ① 0 0 | 0 1 0 | 5th Row of HT |
| 7 | 0 0 0 0 0 ① 0 | 0 0 1 | 6th Row of HT |
(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 :
Y1 = [1 0 1 1 0 0]
The syndrome for this codeword is given by,
S = Y1 HT
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
X1 = Y1 Å E = [1 0 1 1 0 0] Å [0 1 0 0 0]
or X1 = [1 1 1 1 0 0]
This is the correct transmitted word.
Similarly, we can perform the decoding of 000110.
Let X2 = 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= Y2 HT
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,
X2= Y2 Å E=[0 0 0 1 1 0] Å [0 1 0 0 0 0]
or X2 = [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 + x4
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 + x4. 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 + D4 = D4 + 0D3 + 0D2 + D + 1 …(i)
Generally, the generator polynomial is given by
g(D) = D4 + g3 D3 + g2 D2 + g1 D + 1 …(ii)
Comparing equations (i) and (ii), we obtain
g3 = 0, g2 = 0 and g1 = 1.
Therefore, the block diagram of (15, 11) Hamming encoder is shown in figure 10.27. Here, g2 and g3 are multiplying coefficients. As g3 = g2 = 0, the corresponding links are open while g1= 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 :
c5 = m1 + m2 + m4
c6 = m1 + m2 + m3
c7 = m1 + m3 + m4
c8 = m2 + m3 + m4
where m1, m2, m3 and m4 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 c5, c8, c7 and c8 for various values of m1 m2, m3, m4.
(iv) We obtain all the possible codewords and then calculate the minimum weight.
(v) We obtain dmin 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 :
[c5 c6 c7 c8]1×4 = [m1 m2 m3 m4]1×4 [P]4×4 …(i)
or [c5 c6 c7 c8] = [m1 m2 m3 m4]
or c5 = P11 m1 Å P21 m2 Å P31 m3 Å P41 m4
c6 = P12 m1 Å P22 m2 Å P32 m3 Å P42 m4 …(ii)
c7 = P13 m1 Å P23 m2 Å P33 m3 Å P44 m4
c8 = P14 m1 Å P24 m2 Å P34 m3 Å P44 m4
Comparing equation (ii) with the given equations for c5, c6, c7 and c8, we obtain
P11 = 1 P12 = 1 P13 = 0 P14 = 1
P21 = 1 P22 = 1 P23 = 0 P24 = 1
P31 = 1 P32 = 1 P33 = 0 P34 = 1
P41 = 1 P42 = 1 P43 = 0 P44 = 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 = [Ik : P]
But, k = 4, therefore, we have
equation
Now, the parity check matrix is given by :
H = [PT : In-k]
But PT =
Therefore, we have
equation
(iii) Next, we obtain the values of c5, c6, c7, c8 for different values of m1 m2 m3 m4 :
It is given that,
c5 = m1 Å m2 Å m4
c6 = m1 Å m2 Å m3
c7 = m1 Å m3 Å m4
c8 = m1 Å m3 Å m4
(iv) Next, let us obtain all the codewords.
The remaining codewords are listed in table 10.13.
Table 10.13. Codewords
| S.N. | Message vector | Check bits | Code Vector or codeword | Code weight | |||||||||||||
| m1 | m2 | m3 | m4 | c5 | c6 | c7 | c8 | m1 | m2 | m3 | m4 | c5 | c6 | c7 | c8 | ||
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 4 |
| 2 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 4 |
| 3 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 4 |
| 4 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 4 |
| 5 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 4 |
| 6 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 4 |
| 7 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 4 |
| 8 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 4 |
| 9 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 4 |
| 10 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 4 |
| 11 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 4 |
| 12 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 4 |
| 13 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 4 |
| 14 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 4 |
| 15 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 8 |
From Table 10.13, the minimum weight of this code is 4.
⸫ S = [0, 0, 1, 0]
(v) Now, let us obtain dmin and calculate error detecting and correcting capacity.
The minimum distance dmin is equal to the minimum weight of any non-zero code vector. Looking at table 10.13, we obtain
dmin = 4. Ans.
Therefore, number of errors dectable is given by
dmin ≥ 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
dmin ≥ (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 = YHT
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 ml, m2, m3 and m4, we obtain the various codewords as under.
If m1 m2 m3 m4 = 0 0 0 1
Then c5 = 0 Å 0 Å 1 = 1
c6 = 0 Å 0 Å 0 = 0
c7 = 0 Å 0 Å 1 = 1
c8 = 0 Å 0 Å 1 = 1
Hence the codeword is X = m1 m2 m3 m4 c5 c6 c7 c8
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 :
c1 = m1 + m2 + m4
c2 = m1 + m3 + m4
c3 = m1 + m2 + m3
c4 = m2 + m3 + m4
where mi are the message digits and ci 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
[c1 c2 c3 c4]1×4 = [m1 m2 m3 m4]1×4 = [P]4×4
or [c1 c2 c3 c4] = [m1 m2 m3 m4]
or c1 = P11 m1 Å P21 m2 Å P31 m3 Å P41 m4
c2 = P12 m1 Å P22 m2 Å P32 m3 Å P42 m4 …(ii)
c3 = P13 m1 Å P23 m2 Å P33 m3 Å P44 m4
c3 = P14 m1 Å P24 m2 Å P34 m3 Å P44 m4
Comparing equation (ii) with the given equations we obtain
P11 = 1 P12 = 1 P13 = 0 P14 = 1
P21 = 1 P22 = 0 P23 = 1 P24 = 1
P31 = 1 P32 = 1 P33 = 1 P34 = 0
P41 = 0 P42 = 1 P43 = 1 P44 = 1
Hence, the coefficient matrix is given by :
P =
Now, the generator matrix is given by
G = [Ik : 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 = [PT :In-k]
But PT =
and In-k = I4 =
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 dmin is equal to the minimum weight of any non-zero code vector.
⸫ dmin = 4
Number of errros dectable is given by
dmin > 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
dmin > (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 = YHT
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 [c0, c1, c2]1×3 = [m0 m1 m2]1×3 [P]3×3
The parity matrix can be obtained from the generator matrix as under :
equation
Therefore, [P] =
Also, [c0, c1, c2] = [m0, m1, m2]
From above, we get
c0 = m0 Å m2
c1 = m1 Å m2
c2 = m0 Å m1
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
dmin = 3
Therefore, number of errros can be corrected will be
dmin ≥ 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 HT.
Again, first we have to obtain the parity check matrix H as under :
H= [PT : In-k]
Here, n – k = 3 and let us obtain PT 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 HT as under :
HT =
We know that the syndrome is given by
Syndrome S = Y HT
or S = [1 0 0 0 11] = [1 1 1] Ans.