#### 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** = (*v*_{0}, v_{1}, ..., v_{n-1}) be a code word that was transmitted over a noisy channel. Let **r** = (*r*_{0}, r_{1}, ..., r_{n-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

_{0}, v

_{1}, ..., v

_{n-1}

_{0}, r

_{1}, ..., r

_{n-1}

#### e = r + v = (*e*_{0}, e_{1}, ..., e_{n-1}). (3.9)

_{0}, e

_{1}, ..., e

_{n-1}

#### is an n-tuple where *e*_{i} = 1 for *r*_{i} ≠ *v*_{i} and *e*_{i} = 0 for *r*_{i} = *v*_{i }.

_{i}

_{i}

_{i}

_{i}

_{i}

#### 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 . H^{T} = (*s*_{0}, s_{1}, ..., s_{n-k-1}). (3.10)

^{T}

_{0}, s

_{1}, ..., s

_{n-k-1}

#### 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** . **H**^{T} = 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** . **H**^{T} = 0. Error patterns of this kind are called undetectable error patterns. Since there are 2^{k} - 1 nonzero code words, there are 2^{k} - 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.

^{T}

^{T}

^{k}

^{k}

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

*s*_{0} = r_{0} + r_{n-k} p_{00} + r_{n-k+1} p_{10} + ... + r_{n-1} p_{k-1,0}

s_{1} = r_{1} + r_{n-k} p_{01} + r_{n-k+1} p_{11} + ... + r_{n-1} p_{k-1,1}

.

. *(3.11)*

*.*

s_{n-k-1} = r_{n-k-1} + r_{n-k} p_{0,n-k-1} + r_{n-k+1} p_{1,n-k-1} + ... + r_{n-1} p_{k-1,n-k-1}

_{0}= r

_{0}+ r

_{n-k}p

_{00}+ r

_{n-k+1}p

_{10}+ ... + r

_{n-1}p

_{k-1,0}

s

_{1}= r

_{1}+ r

_{n-k}p

_{01}+ r

_{n-k+1}p

_{11}+ ... + r

_{n-1}p

_{k-1,1}

.

.

s

_{n-k-1}= r

_{n-k-1}+ r

_{n-k}p

_{0,n-k-1}+ r

_{n-k+1}p

_{1,n-k-1}+ ... + r

_{n-1}p

_{k-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 (*r*_{0 }, *r*_{1 }, ... , *r*_{n-k-1}) and the parity-check digits recomputed from the received information digits *r*_{n-k-1 }, *r*_{n-k , }*r*_{n-k+1 }, ... , *r*_{n-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.

_{0 }

_{1 }

_{n-k-1}

_{n-k-1 }

_{n-k , }

_{n-k+1 }

_{n-1 }

#### 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** = (*r*_{0}, r_{1}, r_{2}, r_{3}, r_{4}, r_{5}, r_{6}) be the received vector. Then the syndrome is given by

_{0}, r

_{1}, r

_{2}, r

_{3}, r

_{4}, r

_{5}, r

_{6}

#### The syndrome digits are:

#### s_{0 } = *r*_{0 }+ *r*_{3 }+ *r*_{5 }+ *r*_{6
}s_{1 }= *r*_{1 }+ *r*_{3 }+ *r*_{4 }+ *r*_{5
}s_{2 }= *r*_{2 }+ *r*_{4 }+ *r*_{5 }+ *r*_{6 }

_{0 }

_{3 }

_{5 }

_{6 }

_{1 }

_{1 }

_{3 }

_{4 }

_{5 }

_{2 }

_{2 }

_{4 }

_{5 }

_{6 }