cyclic encoder design , Syndrome calculator , syndrome calculation in cyclic codes , cyclic encoder design , design of encoder and syndrome calculator for cyclic codes :-

**EXAMPLE 10.37. Determine the encoded message for the following 8 bit data codes using the following CRC generating polynomial : **

**P(x) = x^{4} + x^{3} + x^{0}**

**(i) 1 1 0 0 1 1 0 0**

**(ii) 0 1 0 1 1 1 1 1**

**Solution :**The given message is 1 1 0 0 1 1 0 0. This means that there are 8 message bits.

Thus,

*k*= 8

We know that the degree of generator polynomial is equal to the number of parity (check) bits in the code.

Therefore, number of parity bits (n – k) = 4

Hence, codeword length, n = 8 + 4 = 12

Hence the message polynomial corresponding to the message 1 1 0 0 1 1 0 0 is given as

M(x) =

*x*

^{7}+

*x*

^{6}+ 0

*x*+ 0

*x*

^{4}+

*x*

^{3}+

*x*

^{2}+ 0

*x*+0

or M(x) =

*x*

^{7}+

*x*

^{6}+

*x*

^{2}+

*x*

^{2}

Now, the generator polynomial is given by,

P(x) =

*x*

^{4}+

*x*

^{3}+ 1

Next, let us multiply the message polynomial by

*x*

^{n-k}i.e.

*x*

^{4}

Thus,

*x*

^{4}[M(x)] =

*x*

^{4}[

*x*

^{7}+

*x*

^{6}+

*x*

^{3}+

*x*

^{2}]

or

*x*

^{4}M(x) =

*x*

^{11}+

*x*

^{10}+

*x*

^{7}+

*x*

^{6}

let us divide

*x*

^{4}M(

*x*) by the generator polynomial as under :

**equation**

Mod 2 addition →

Mod 2 addition →

Mod 2 addition →

Mod 2 addition →

Now, let us obtain the codeword polynomial X(x) as under :

X(x) =

*x*

^{4}M(

*x*) + C(

*x*)

or X(

*x*) = (

*x*

^{11}

*+ x*

^{10}

*+ x*

^{7}

*+ x*

^{6}) + (

*x*

^{3}

*+ x*

^{2}

*+ x + 1*)

or X(

*x*) =

*x*

^{11}+

*x*

^{10}+ 0

*x*

^{9}+ 0

*x*

^{8}+

*x*

^{7}+

*x*

^{6}+ 0

*x*

^{5}+ 0

*x*

^{4}+

*x*

^{3}+

*x*

^{2}+

*x*+1

Hence, the codeword will be

**equation**

(ii) Similarly, we can obtain the codeword for the other message. The corresponding codeword for the message 0101111 is,

**equation**

**EXAMPLE 10.38. Using the generator polynomial g(**

*x*) = 1 +*x*^{2}+*x*^{3}, generate the systematic and non systematic cyclic codewords for the message vectors 1011 and 1001.**Solution :**Non systematic code vectors

The number of message bits =

*k*= 4

Therefore, the number of parity bits (n – k) = degree of generator polynomial = 3

The total number of hits per codeword n = 4 + 3 + 7

The message polynomial for the message vector 1011 is given by

M(

*x*) = m0 + m

_{1}

*x*+ m

_{2}

*x*

^{2}+ m

_{3}

*x*

^{3}…(i)

Substituting the value of m0 ….., m

_{3 }we obtain

M(

*x*) = 1 +

*x*

^{2}+

*x*

^{3 }…(ii)

Therefore, the generator polynomial is given by,

g(x) = 1 +

*x*

^{2}+

*x*

^{3}

Also, the non systematic cyclic codeword polynomial is given by :

X(

*x*) = M(

*x*) . g(

*x*) = (1 + x

^{2}+ x

^{3}) (1 + x

^{2}+ x

^{3})

or X(

*x*) = 1 +

*x*

^{2}+

*x*

^{3}+

*x*

^{2}+

*x*

^{4}+

*x*

^{5}+

*x*

^{3}+

*x*

^{5}+

*x*

^{6}

or X(

*x*) = 1 +

*x*

^{2}(1 + 1) +

*x*

^{3}(1 + 1) +

*x*

^{4}+

*x*

^{5}(1 + 1) +

*x*

^{6}

But. 1 + 1 = 0 (Modulo-2 addition).

so, X(

*x*) = 1 +

*x*

^{4}+

*x*

^{6}

It may be noted that the degree of the codeword polynomial is 6 i.e. (n – 1). The codeword is given by,

X = (1 0 0 0 1 1 1)

**Ans.**

This is the non systematic codeword for the message vector 1011.

**Systematic code vector**

**Let us multiply M(**

*x*) by x

^{n-k}as under:

*x*

^{n-k}M(

*x*) =

*x*

^{3}[1 +

*x*

^{2}+

*x*

^{3}] =

*x*

^{3}+

*x*

^{5}+

*x*

^{6}

Now, we divide

*x*

^{n-k}M(

*x*) by the generator polynomial.

The division is as under :

**equation**

Next, let us obtain the codeword polynomial X(

*x*).

The codeword polynomial can be obtained by adding D

^{n-k}M(p) to the remainder polynomial C(

*x*).

Thus X(

*x*) = [x

^{n-k}M(

*x*)] Å C(

*x*)]

or X(

*x*) =

*x*

^{6}+

*x*

^{5}+ 0

*x*

^{4}+

*x*

^{3}+ 0

*x*

^{2}+ 0

*x*+ 0] Å [0 + 0 + 0]

or X(

*x*) = [0 + 0

*x*+ 0

*x*

^{2}+

*x*

^{3}+ 0

*x*

^{4}+

*x*

^{5}+

*x*

^{6}]

Hence, the codeword is given by,

**diagram**

**EXAMPLE 10.39. Sketch the encoder and syndrome calculator for the generator polynomial g(**

*x*) = 1 +*x*^{2}+*x*^{3}, and obtain the syndrome for the received codeword 1001011.**Solution : Encoder :**

The received code word has 7 bits, hence, n = 7 and the degree of generator polynomial is 3, hence, n – k = 3, so k = 4. Thus, the given code is a (7, 4) cyclic code.

The generator polynomial of an (

*n, k*) cyclic code is expressed as,

**equation**

or

**equation**

The given generator polynomial is,

g(

*x*) = 1 + 0

*x*+

*x*

^{2}+

*x*

^{1}…(ii)

Comparing equations (i) and (ii), we obtain

g

_{1}= 0, g

_{2}= 1

Hence, the encoder is shown in figure 10.45.

**diagram**

**FIGURE 10.45**

*Encoder for example 10.38.*

**Syndrome calculator**

The given generator polynomial is,

g(

*x*) = 1 +

*x*

^{2}+

*x*

^{3}

or g(

*x*) =

*x*

^{3}+

*x*

^{2}+ 0

*x*+ 1 …(iii)

We know that the general form of generator polynomial is given by

g(

*x*) =

*x*

^{3}+ g

_{2}

*x*

^{2}+ g

_{1}

*x*+ 1 …(iv)

Comparing equations (iii) and (iv), we get

g

_{1}= 0

g

_{2}= 1

The syndrome calculator is shown in figure 10.46.

**diagram**

**FIGURE 10.46.**

*Syndrome calculator.*

**Calculation of syndrome**

**The output switch of figure 10.46 will be initially in position 1 until all the 7 bits of the received signal Y are shifted into the register. After that, the output switch is shifted to position 2. Clock pulses are then applied to the shift register to output the syndrome vector S. Table 10.16 explains the process of syndrome generation.**

Thus, the required syndrome will be

S = 100

**Table 10.16.**

Shift |
Input bits(Y) |
Contents of the shift register |
||

S_{0} = Y Å S_{2} |
S_{1} = S_{0} |
S_{2} = S_{1} Å S_{0} |
||

— | 0 | 0 | 0 | |

1 | 1 (LSB) | 1 | 0 | 0 |

2 | 1 | 1 | 1 | 1 |

3 | 0 | 1 | 1 | 0 |

4 | 1 | 1 | 1 | 1 |

5 | 0 | 1 | 1 | 0 |

6 | 0 | 0 | 1 | 1 |

7 | 1 (MSB) | 0 | 0 | 1 |