## Cyclic Codes

The aim of this chapter is to show the connection between cyclic codes introduced in section 6.7 and the polynomial algebra of the previous chapter. Then we exploit the latter to throw light on the former. The connection is that each word in F^{n}
, say a
_{0}
a
_{1} … a
_{
n–1}, is thought of as a polynomial a
_{0}+ a
_{1}
x … a
_{n–1}
x
^{n–1} in F[X]. Notice that in order to retain the sensible notation of a_{i}
being the coefficient of x^{i}
we have to represent the words as a
_{0}
a
_{1} … a
_{
n–1} rather thana
_{1}
a
_{2} … a_{n}
. Of course F[X] has infinitely many members, whereas F^{n}
(e.g.
Z
p
n
) has only p^{n}
members, so the match is not perfect. To overcome this we just replace the set F[X] by its subset of polynomials with degree less than n. Then it is easy to see that if c
_{1} and c_{2}
are any codewords and c
_{1}(x),c
_{2}(x) are their corresponding polynomials and λ_{1}, λ_{2} are any members of F, then the codeword λ_{1}c_{1} + λ_{2}c_{2} has λ_{1}c_{1}(x) + λ_{2}c_{2}(x) as its polynomial representative. For cyclic codes it turns out that multiplication of polynomials is a very useful operation, but here we hit a snag: if C has length n so that its polynomials have degree less than n, the product of two such polynomials can have degree at least n, so does not represent a codeword. To get round this we pick a polynomial f of degree n and define our multiplication operation to be polynomial multiplication modulo f(x), so that any two polynomials which differ by a multiple of f(x) are regarded as equal. So our set of polynomials of degree less than n which will represents codewords can be thought of as the set of all remainder polynomials on division by f(x). Our notation for this set is F[X]/f(x), and we shall make use of congruence notation by using ≡ for equality in f[X]/f(x) and = for equality in F[X].