Next: Code Framework in Java Up: Linear Codes Previous: Hamming Codes   Contents

## Cyclic Codes

The general idea of a cyclic code is to "rotate" the codeword. In this code no parity bits are added to the end of plain text words to make them code words. The unencoded words and the codewords are the same length. {Unencoded Words} {Coded Words}
{Vectors in } {Vectors in } We can represent a codeword as:
{codewords}={ } =
In a cyclic code the encoded words would then look like:

or
for all c If any codeword, length , is rotated n-times, we get back the same codeword. This code is similar to the other linear codes in that a linear map is defined as where is a linear map that rotates the elements of the code words. In matrix representation, is a rotation of the identity matrix. = The matrix rotates the code words by: For any cyclic code, we know that ; . To find cyclic codes, we look for polynomials that divide . If our cyclic code converts a vector of to one a vector of , then k = the degree of the polynomial dividing . Ex n=3 , so has divisors and Note: has no divisors over Possible codes to are given by the polynomials:

Generating Matrix In order to make the generating matrix for a given cyclic code, we have to pick a polynomial. From the last example, we can pick either or . The generating matrix will be a k x n matrix, where k=n- degree of polynomial and n= degree of code. In the last example n=3. x+1 G= k=3-1=2
The first row of the generating matrix begins with the coefficients on the polynomial, and the remaining spaces are filled with zeros. The rows below are rotations of the first row. G= k=3-2=1 Ex for n=4 If we wanted to use the code where n=4, we would have to find the divisors for . The divisors for this polynomial are , , and . Although we had the divisor when n=3, the generating matrix here will be different. x+1 G= k=4-1=3 G= k=4-2=2 G= k=4-3=1

In the previous two linear codes, we constructed the generating matrix by defining the generating matrix G as G=(I). Because we constructed the generating matrix first in the cyclic codes, we can derive the matrix by putting the G matrix in reduced row echelon form and taking the submatrix for . Finding From the example where n=3, we know that the generating matrix for is G= If we block out the nested identity matrix, we are left with .

Next: Code Framework in Java Up: Linear Codes Previous: Hamming Codes   Contents
Frederick Leitner 2004-09-01