SYNDROME DECODING FOR BLOCK CODES , Basic Concept , Error detection in the received code word.

SYNDROME DECODING FOR BLOCK CODES

1. Basic Concept

            In previous article, we have discussed about the encoder for the linear block code. Now, let us learn about the decoder. The two important functions of the decoder are as under:
(i)         Error detection in the received code word.
(ii)        Error correction.
The decoding of linear block codes is done by using a special technique called syndrome decoding, which reduces the memory requirement of the decoder to a great extent. The syndrome decoding technique is explained in the following paragraph.

2. Practical Assumptions

(i)         Let X represent the transmitted code word and Y represent the received code word.
(ii)        Then, if X = Y, no errors in the received signal and
if X  Y , then some errors are present.

3. Detection of Error
4. For an (n, k) linear block code, there exists a parity check matrix H of size (n – k) x n. We know that,

Parity check matrix, H= [P^T : I_n-k]_{(n-k) x n}
where P^T represents the transpose of P matrix and I_n-k is the identity matrix.
*          Modulo-2 adders are nothing but EX-OR gates.

2. The transpose of the parity check matrix is given by,

HT =                                         …(10.19)
where P is the coefficient matrix.

3. The transpose of parity check. matrix (H^T) exhibits a very important property, i.e.

XH^T = (0, 0, …, 0)                                           … (10.20)
This means that the product of any code vector X and the transpose of the parity check matrix will always be 0.
We shall use this property for the detection of errors in the received code words as under :
At the receiver, we have
If                                 YH^T = (0, 0, …, 0), then Y = X i.e. there is no error.
But, if              YH^T  (0, 0, …, 0), Then Y  X i.e. error exists in the received code word

4. Syndrome and its use for error detection

            The syndrome is defined as the non-zero output of the product YH^T. Thus, the non-zero syndrome represents the presence of errors in the received code word. The syndrome is represented by S and is mathematically given as,
S = YH^T                                                          …(10.21)
or                                             [S]_1x(n-k)  = [Y]_1xn [H^T]_{n x (n-k)}                      …(10.22)
The all zero elements of syndrome represent that there is no error, and a non-zero value of an element in syndrome represents the presence of error. But sometimes, even if all the syndrome elements have zero value, the error exists. This has been shown in figure 10.21.
diagram
FIGURE 10.21 Two different possibilities for S = 0.

5. Error Vector (E)

1. For the n-bit transmitted and received code words X andY respectively, let us define an n-bit error vector E such that its non-zero elements represent the locations of errors in the received code vector Y as shown in figure 10.22.
2. The encircled entries in figure 10.22 indicate the presence of errors.

diagram
FIGURE 10.22 The non-zero elements of error vector represent the locations of errors in the received code vector Y.
The elements in the code word vector Y can be obtained by using the modulo-2 additions, as under:
Y = X Å E                                                      …(10.23)
From figure 10.22, we can write that,
Y = [0 Å 1, 0 Å 0, 1 Å 1, 1 Å 0, 1 Å 1, 1 Å 0, 0 Å 0]
of            Y = [1, 0 , 0, 1, 0, 1, 0]

3. The principle of modulo-2 addition can be applied in a slightly different way as under :

X = Y Å E                                                      …(10.24)
From figure 10.22, we can write that,
X = [1 Å 1, 0 Å 0, 0 Å 1, 1 Å 0, 0 Å 1, 1 Å 0, 0 Å 0] = [0, 0, 1, 1, 1, 1, 0]

6. Relation between syndrome and error vector

            From equation (10.20), the syndrome is given by,
S = YH^T
Substituting the value of Y from equation (10.23), we obtain
S = [X Å E] H^T = XH^T Å EH^T
But,                             XH^T = 0
Therefore                     S = 0 Å EH^T
or                                 S = EH^T                                                                                              …(10.25)
This is the relation between the syndrome S and the error vector E.
EXAMPLE 10.7. For a code vector X = (0 1 1 1 0 0 0) and the parity check matrix H given below, prove that
XH^T = (0, 0, …, 0)
H =
Solution: The transpose of the given parity matrix H, can be obtained by interchanging the rows and columns as under:
H^T=
Also, the product XH^T is given by,
XHT = [0 1 1 1 0 0 0] _1×7
= [(0 x1) Å (1 x 1) Å (1 x 1) Å (1 x 0) Å (0 x 1) Å (0 x 0) Å (0 x 0),
[(0 x1) Å (1 x 1) Å (1 x 0) Å (1 x 1) Å (0 x 0) Å (0 x 1) Å (0 x 1),
[(0 x1) Å (1 x 0) Å (1 x 1) Å (1 x 1) Å (0 x 0) Å (0 x 0) Å (0 x 1)],
or                     XH^T =  0 Å 1 Å 1 Å 0 Å 0 Å 0 Å 0, 0 Å 1 Å 0 Å 0 Å 0,
0 Å 0 Å 1 Å 1 Å 0 Å 0 Å 0
or                     HX^T = [0, 0, 0]_1×3
Thus, we have proved that for a valid code word, the product XH^T = (0, 0, 0) Ans.
EXAMPLE 10.8. The parity check matrix of a (7, 4) Hamming code is as Under:
H =
Calculate the syndrome vector for single bit errors.
Solution: We know that the syndrome vector is given by
S = EH^T = [E]_1×7 [H^T]_7×3
Therefore, syndrome vector will represented by a 1 x 3 matrix.
Thus,                                       [S]_1×3 = [E]_1×7 [H^T]_7×3
Now, let us write various error vectors.
Various error vectors with single bit errors are shown in table 10.6. The encircled bits represent the locations of errors.
Table 10.6.

 
Let us calculate the syndroms corresponding to each error vector.
(i)         We have [S]_1×3 = [E]_1×7 [H^T]_7×3
Substituting [E] = (1 0 0 0 0 0 0) and H^T, we obtain
[S] = [1 0 0 0 0 0 0]_1×7
Therefore,  [S] = [1 Å 0 Å 0 Å 0 Å 0 Å 0 Å 0, 1 Å 0 Å 0 Å 0 Å 0 Å 0 Å 0,
1 Å 0 Å 0 Å 0 Å 0 Å 0 Å 0 Å 0]
Here,               [S] = [1, 1, 1]
This is the syndrome for the first bit in error.
(ii)        For the second bit in error, we have
[S] = [0 1 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 Å 0 Å 0 Å 0 Å 0]
Here,           [S] = [1, 1, 0]
(iii)       Similarly, we can obtain the other syndromes as shown in table 10.7.
(iv)       Here, it may be noted that the first row of table 10.7 represent an error vector with no errors. The corresponding syndrome is (0, 0, 0).
(v)        Table 10.7 also shows that the syndrome vectors are same as the rows of the transpose matrix H^T.
Table 10.7. Syndromes for various error vectors