chapter  8
19 Pages

Cyclic Codes

ByJohn Baylis

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 Fn , 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 ai being the coefficient of xi we have to represent the words as a 0 a 1 … a n–1 rather thana 1 a 2 … an . Of course F[X] has infinitely many members, whereas Fn (e.g. Z p n ) has only pn 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 c2 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 λ1c1 + λ2c2 has λ1c1(x) + λ2c2(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].