(M3L2) Lesson 2: Syndrome and Error Detection

In this lesson, the concept of syndrome is introduced. The use of syndrome for error detection and correction is discussed.

Objectives
Upon completion of this lesson, you will be able to:
- Know what is the syndrome and how can we compute it.
-Know how to use the syndrome to detect errors then correct them.
- Understand the major engineering task to design and implement the channel encoder/decoder pair.

What is the Syndrome?

Consider an (n, k) linear code with generator matrix G and parity-check matrix H. Let v = (v0, v1, ..., vn-1) be a code word that was transmitted over a noisy channel. Let r = (r0, r1, ..., rn-1) be the received vector at the output of the channel. Because of the channel noise, r may be different from v. The vector sum

e = r + v = (e0, e1, ..., en-1).           (3.9)

is an n-tuple where ei = 1 for rivi and ei = 0 for ri = vi .

This n-tuple is called the error vector (or error pattern).

The 1's in e are the trasmission error caused by the channel noise. It follows from (3.9) that the received vector r is the vector sum of the transmitted code word and the error vector, that is,

r = v + e.

Example 3.6

If the transmitted code word v = (0001101) and the received vector r = (0001100) .
So the vector sum of v and r is

                                                (0001101)
                                          +
                                                (0001100)
                                                -----------
                          v + r = e =  (0000001)

i.e. the error vector e = (0000001).

i.e. the received code vector r have an errror in the 7th bit.

Of course, the receiver does not know either v or e. Upon receiving r, the decoder must first determine whether r contains transmission errors. If the presence of errors is detected, the decoder will either take actions to locate the errors and correct them (FEC) or request for a retransmission of v (ARQ).
When r is received, the decoder computes the following (n - k)-tuple:

s = r . HT = (s0, s1, ..., sn-k-1).      (3.10)

Which is called syndrome of r.
Then s = 0 if and only if r is a code word, and s ≠ 0 if and only if r is not a code word.
It is possible that the errors in certain error vectors are not detectable (i.e., r contains errors but s = r . HT = 0).
This happens when the error pattern e is identical to a nonzero code word. In this event, r is the sum of two code words which is a code word, and consequently r . HT = 0. Error patterns of this kind are called
undetectable error patterns. Since there are 2k - 1 nonzero code words, there are 2k - 1 undetectable error patterns. when an undetectable error pattern occurs, the decoder makes a decoding error.
In a later section of the module we derive the probability of an undetected error for a BSC and show that this error probability can be made very small.

Based on (3.7) and (3.10), the syndrome digits are as follows:

s0       = r0 + rn-k p00 + rn-k+1 p10 + ... + rn-1 pk-1,0
s1       = r1 + rn-k p01 + rn-k+1 p11 + ... + rn-1 pk-1,1
.
.                                                                                                                     
(3.11)
.
sn-k-1 = rn-k-1 + rn-k p0,n-k-1 + rn-k+1 p1,n-k-1 + ... + rn-1 pk-1,n-k-1

If we examine the equations above carefully, we find that the syndrome s is simply the vector sum of the received parity digits (rr, ... , rn-k-1) and the parity-check digits recomputed from the received information digits rn-k-1 rn-k , rn-k+1 , ... , rn-1 .
Therefore, the syndrome can be formed by a circuit similar to the encoding circuit.
A general syndrome circuit is shown in Figure 3.4.

Figure 3.4 Syndrome circuit for an (n, k) linear systematic code

Example 3.7
Consider the (7, 4) linear code whose parity-check matrix is given in Example 3.4.
Let r = (r0, r1, r2, r3, r4, r5, r6) be the received vector. Then the syndrome is given by

 

The syndrome digits are:

srrrr6
s1  rrrr5
s2  rrrr

The syndrome circuit for this code is shown in Example 3.5.

Figure 3.5  Syndrome circuit for the (7, 4) systematic code given in Table 3.1.