# 24.7 Cyclic Codes

Cyclic codes are a very important class of codes. In the next two sections, we’ll meet two of the most useful examples of these codes. In this section, we describe the general framework.

A code  is called cyclic if



For example, if  is in a cyclic code, then so is . Applying the definition two more times, we see that  and  are also codewords, so all cyclic permutations of the codeword are codewords. This might seem to be a strange condition for a code to satisfy. After all, it would seem to be rather irrelevant that, for a given codeword, all of its cyclic shifts are still codewords. The point is that cyclic codes have a lot of structure, which makes them easier to study. In the case of BCH codes (see Section 24.8), this structure yields an efficient decoding algorithm.



The rows of  generate a three-dimensional subspace of seven-dimensional binary space. In fact, in this case, the cyclic shifts of the first row give all the nonzero codewords:



Clearly the minimum weight is 4, so we have a cyclic [7, 3, 4] code.

We now show an algebraic way to obtain this code. Let  denote polynomials in  with coefficients mod 2, and let  denote these polynomials mod . For a detailed description of what this means, see Section 3.11. For the present, it suffices to say that working mod  means we are working with polynomials of degree less than 7. Whenever we have a polynomial of degree 7 or higher, we divide by  and take the remainder.

Let . Consider all products



with  of degree . Write the coefficients of the product as a vector . For example,  yields , which is the top row of . Similarly,  yields the second row of  and  yields the third row of . Also,  yields , which is the sum of the first and third rows of . In this way, we obtain all the codewords of our code.

We obtained this code by considering products  with . We could also work with  of arbitrary degree and obtain the same code, as long as we work mod . Note that . Divide  into :



with . Then



Therefore,  gives the same codeword as , so we may restrict to working with polynomials of degree at most two, as claimed.

Why is the code cyclic? Start with the vector for . The vectors for  and  are cyclic shifts of the one for  by one place and by two places, respectively. What happens if we multiply by ? We obtain a polynomial of degree 7, so we divide by  and take the remainder:



The remainder yields the vector . This is the cyclic shift by three places of the vector for .

A similar calculation for  shows that the vector for  yields the shift by  places of the vector for . In fact, this is a general phenomenon. If  is a polynomial, then



The remainder is , which corresponds to the vector . Therefore, multiplying by  and reducing mod  corresponds to a cyclic shift by one place of the corresponding vector. Repeating this  times shows that multiplying by  corresponds to shifting by  places.

We now describe the general situation. Let  be a finite field. For a treatment of finite fields, see Section 3.11. For the present purposes, you may think of  as being the integers mod , where  is a prime number, since this is an example of a finite field. For example, you could take , the integers mod 2. Let  denote polynomials in  with coefficients in . Choose a positive integer . We’ll work in , which denotes the elements of  mod . This means we’re working with polynomials of degree less than . Whenever we encounter a polynomial of degree , we divide by  and take the remainder. Let  be a polynomial in . Consider the set of polynomials



where  runs through all polynomials in  (we only need to consider  with degree less than , since higher-degree polynomials can be reduced mod ). Write



The coefficients give us the -dimensional vector . The set of all such coefficients forms a subspace  of -dimensional space . Then  is a code.

If  is any such polynomial, and  is another polynomial, then  is the multiple of  by the polynomial . Therefore, it yields an element of the code . In particular, multiplication by  and reducing mod  corresponds to a codeword that is a cyclic shift of the original codeword, as above. Therefore,  is cyclic.

The following theorem gives the general description of cyclic codes.

# Theorem

Let  be a cyclic code of length  over a finite field . To each codeword , associate the polynomial  in . Among all the nonzero polynomials obtained from  in this way, let  have the smallest degree. By dividing by its highest coefficient, we may assume that the highest nonzero coefficient of  is 1. The polynomial  is called the generating polynomial for . Then

1.  is uniquely determined by .

2.  is a divisor of .

3.  is exactly the set of coefficients of the polynomials of the form  with .

4. Write . Then  corresponds to an element of  if and only if .

Proof.

1. If  is another such polynomial, then  and  have the same degree and have highest nonzero coefficient equal to 1. Therefore,  has lower degree and still corresponds to a codeword, since  is closed under subtraction. Since  had the smallest degree among nonzero polynomials corresponding to codewords,  must be 0, which means that . Therefore,  is unique.

2. Divide  into :



for some polynomials  and , with . This means that



As explained previously, multiplying  by powers of  corresponds to cyclic shifts of the codeword associated to . Since  is assumed to be cyclic, the polynomials  for  therefore correspond to codewords; call them . Write . Then  corresponds to the linear combination



Since each  is in  and each  is in , we have a linear combination of elements of . But  is a vector subspace of -dimensional space . Therefore, this linear combination is in . This means that , which is , corresponds to a codeword. But , which is the minimal degree of a polynomial corresponding to a nonzero codeword in . Therefore, . Consequently , so  is a divisor of .

3. Let  correspond to an element of . Divide  into :



with . As before,  corresponds to a codeword. Also,  corresponds to a codeword, by assumption. Therefore,  corresponds to the difference of these codewords, which is a codeword. But this polynomial is just . As before, this polynomial has degree less than , so . Therefore, . Since , we must have . Conversely, as explained in the proof of (2), since  is cyclic, any such polynomial of the form  yields a codeword. Therefore, these polynomials yield exactly the elements of .

4. Write , which can be done by (2). Suppose  corresponds to an element of . Then , by (3), so



Conversely, suppose  is a polynomial such that  . Write , for some polynomial . Dividing by  yields , which is a multiple of , and hence corresponds to a codeword. This completes the proof of the theorem.

Let  be as in the theorem. By part (3) of the theorem, every element of  corresponds to a polynomial of the form , with . This means that each such  is a linear combination of the monomials . It follows that the codewords of  are linear combinations of the codewords corresponding to the polynomials



But these are the vectors



Therefore, a generating matrix for  can be given by



We can use part (4) of the theorem to obtain a parity check matrix for . Let  be as in the theorem (where ). We’ll prove that the  matrix



is a parity check matrix for . Note that the order of the coefficients of  is reversed. Recall that  is a parity check matrix for  means that  if and only if .

# Proposition

 is a parity check matrix for .

Proof. First observe that since  has 1 as its highest nonzero coefficient, and since , the highest nonzero coefficient  of  must also be 1. Therefore,  is in row echelon form and consequently its rows are linearly independent. Since  has  rows, it has rank . The right null space of  therefore has dimension .

Let . We know from part (4) that  if and only if .

Choose  with  and look at the coefficient of  in the product . It equals



There is a technical point to mention: Since we are looking at , we need to worry about a contribution from the term  (since , the monomial  reduces to ). However, the highest-degree term in the product  before reducing mod  is . Since , we have . Therefore, there is no term with  to worry about.

When we multiply  times , we obtain a vector whose first entry is



More generally, the th entry (where ) is



This is the coefficient of  in the product .

If  is in , then , so all these coefficients are 0. Therefore,  times  is the 0 vector, so the transposes of the vectors of  are contained in the right null space of . Since both  and the null space have dimension , we must have equality. This proves that  if and only if , which means that  is a parity check matrix for .

# Example

In the example at the beginning of this section, we had  and . We have , so . The parity check matrix is



The parity check matrix gives a way of detecting errors, but correcting errors for general cyclic codes is generally quite difficult. In the next section, we describe a class of cyclic codes for which a good decoding algorithm exists.