SYNDROME DECODING OF CYCLIC CODES

3.5 SYNDROME DECODING OF CYCLIC CODES

The syndrome computation may be performed by a shift register similar in form to that used for encoding.

To elaborate, let us consider a systematic cyclic code and let us represent the received code vector R by the polynomial R(x). In general, R = C + E, where C is the transmitted code word and E is the error vector. Hence, we have

R(x) = C(x) + E(x)

= D(x) g(x) + E(x)                            (3.17)

Now, suppose we divide R(x) by the generator polynomial g(x). This division will yield

R(x) / g(x) = Q(x) +S(x) / g(x)

or, equivalently,

R(x) =Q(x) g(x) + S(x)                                (3.18)

The remainder S(x) is a polynomial of degree less than or equal to n - k-1. If we combine Equation 3.17 with Equation 3.18, we obtain

E(x) = [D(x) + Q(x)] g(x) + S(x)                        (3.19)

This relationship illustrates that the remainder S(x) obtained from dividing R(x) by g(x) depends only on the error polynomial E(x), and, hence, S(x) is simply the syndrome associated with the error pattern E. Therefore,

R(x) =Q(x)g(x) + S(x)

where S(x) is the syndrome polynomial of degree less than or equal to

n-k-1. If g(x) divides R(x) exactly, then S(x) = 0 and the received decoded word is Ĉ = R.

The division of R(x) by the generator polynomial g(x) may be carried out by means of a shift register which performs division as follows:

First the received vector R is shifted into an (n- k) stage shift register as illustrated in Figure 3.3

 

Initially, all the shift-register contents are zero and the gate is on. After the entire n-bit received vector has been shifted into the register, the contents of the n - k stages constitute the syndrome with the order of the bits numbered as shown in Figure 3.3. Given the syndrome from the (n – k) stage shift register.