where, for all k, Rk = (Zi,j:i+j = k:PixQ.j) . This makes polynomial multiplication behave like normal multiplication. For example,

which is what one would obtain if x is assumed to be a normal variable, and multiplication and addition obey the rules of real arithmetic. An immediate consequence of the definition is that, for non-zero polynomials P and Q, degree. (PxQ) = degree. + degree. Q . For this to be true when P or Q is zero, we require that -oo + n. - -oo, for all n (including -oo). Exact division of polynomials cannot be defined, just as it is impossible to define exact division of integers. Remainder computation can be defined, however, and it is this which is exploited in cyclic codes. The precise specification of the remainder r after dividing the polynomial P by the non-zero polynomial Q is degree.r < degree.Q A (3d :: P = Qxd + r) . In this specification, d ranges over polynomials. For example, with arithmetic on the coefficients defined to be modulo 2, the remainder on dividing x2 + l by x+l is 0 because

degree.Q = -oo < l = degree. ( x + l ) . (Remember that addition is modulo 2, so that 1 + 1 = 0 and, hence, x+x = 0.) The remainder on dividing x2+x+l by x+l is 1 because

degree.l = 0 < 1 = degree. ( x + l ) .

To form a sequence of check bits from a data polynomial P, a so-called generator polynomial Q is used. Generator polynomials are chosen according to their error detection/repair capabilities, and are published in internationally recognized standards. The most important point, of course, is that both the transmitter and the receiver of the data agree on which generator polynomial to use. The check bits are defined to be the coefficients of the remainder polynomial after division of the input polynomial pxxdg#ree-Q by Q. The coefficients of the data polynomial are then transmitted followed by the coefficients of the remainder polynomial, hi effect, this is equivalent to transmitting pxx^ree-Q + r, where r is the remainder. But, since addition modulo 2 coincides with subtraction modulo 2, this polynomial equals pxxde&ree-Q -r, which is divisible by Q. Thus, the receiver may check for errors during transmission by determining whether or not the remainder, after dividing the received data polynomial by Q, isO. Example 16.1. Suppose the generator polynomial is x5 +x 4 +x 2 +1. Then, the message 1000100101, corresponding to the data polynomial x 9 +x 5 +x 2 + l, would be encoded as 100010010100011. This corresponds to the polynomial

( X 9 + X 5 + X 2 + 1 ) X X 5 + (X + l)

4 3 2

(x 5 +x 4 +x 2 + l)x(x 9 +x 8 +x 7 +x 3 +x 2 +x+l) + (x+l) . If the transmission occurs without error, the receiver computes the remainder after dividing

( X 9 + X 5 + X 2 + 1 ) X X 5 + (X + l)

(X 9 +X 5 +X 2 +1)XX 5 + (X + l) (X 5 +X 4 +X 2 + 1 ) X ( X 9 + X 8 + X 7 + X 3 + X 2 + X + 1 ) .

The simple parity check illustrated in Figure 16.1 is the cyclic code resulting from computing the remainder after division of the data polynomial by x+1. We can see this from the specification of the remainder. Substituting x+l for Q, the remainder satisfies degree.r < 1 A (3d :: P = (x+l)xd