A SYSTEMATIC CODE

3.3 METHOD FOR CONSTRUCTING A SYSTEMATIC CODE

A systematic code can be gener­ated directly from the generator polynomial g(x). Suppose that we multiply the message polynomial D(x) by x ^n-1 Thus, we obtain

   x ^n-k  D(x) = d_k-1  x ^n-1 + d_k-2  x ^n-2 + . . . + d₁  x  ^n-k+1 +d₀  x ^n-k   (3.14)

In a systematic code, this polynomial represents the first k bits in the code word C(x). To this polynomial we must add a polynomial of degree less than n-k representing the parity check bits. Now, if x ^n-k D(x) is divided by g(x), the result

                    x ^{n- k} D(x) / g(x) = Q (x) + r(x) / g(x)                      (3.15)

Or, equivalently,

                 x ^n-k D(x) = Q(x)g(x) + r(x)                             (3.16)

where r(x) has degree less than n – k . Clearly, Q(x)g(x) is a code word of the cyclic code. Hence, by adding (modulo-2) r(x) to both sides of Equation 3.14, we obtain the desired systematic code.

To summarize, the systematic code may be generated by

1- Multiplying the message polynomial D(x) by x ^n-k.

2- Dividing x ^n-k D(x) by g(x) to obtain the remainder r(x).

3- Adding r(x) to x ^n-k D(x).

Below we demonstrate how these computations can be performed by using shift registers with feedback.

Since x ⁿ + 1 = g(x)h(x) or, equivalently, g(x)h(x) = 0 mod (x ⁿ + 1), we say that the polynomials g(x) and h(x) are orthogonal. Furthermore, the polynomials x ⁱ g(x) and x ^j h(x) are also orthogonal for all i and j.