In this lesson, the concept of syndrome is introduced. The use of syndrome for error detection and correction is discussed.
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 ri ≠ vi 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.
If the transmitted code word v = (0001101) and the received vector r = (0001100) .
So the vector sum of v and r is
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
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 (r0 , r1 , ... , 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
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