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} $\longrightarrow$ {Coded Words}
{Vectors in $\mathbb{F}_{2}^k$} $\longrightarrow$ {Vectors in $\mathbb{F}_{2}^n$} We can represent a codeword as:
{codewords}={ $c=(c_1, c_2, \hdots, c_n) \vert c_i \epsilon \mathbb{F}_{2}$} = $\zeta$
In a cyclic code the encoded words would then look like:
$c=(c_n, c_1, c_2, \hdots, c_{n-1})$
or $(c_{n-1}, c_n, c_1, \hdots, c_{n-2})$
for all c $\epsilon \zeta$ If any codeword, length $n$, is rotated n-times, we get back the same codeword. This code is similar to the other linear codes in that a linear map $X$ is defined as $X:\zeta \longrightarrow\zeta$ where $X$ is a linear map that rotates the elements of the code words. In matrix representation, $X$ is a rotation of the identity matrix. $X$ = $\left( \begin{array}{cccccc} 0&0&0&\hdots&0&1 1&0&0&\hdots&0&0 0&1&0&\hdots&0&0 \vdots&\vdots 0&0&0&\hdots&1&0\end{array} \right)$ The matrix $X$ rotates the code words by: $\left( \begin{array}{cccccc} 0&0&0&\hdots&0&1 1&0&0&\hdots&0&0 0&1&0&\hdo... ...\left( \begin{array}{c} c_n c_1 c_2 \vdots c_{n-1} \end{array} \right)$ For any cyclic code, we know that $x^n=1$; $x^n-1=0$. To find cyclic codes, we look for polynomials that divide $x^n-1=0$. If our cyclic code converts a vector of $\mathbb{F}_{2}^k$ to one a vector of $\mathbb{F}_{2}^n$, then k = the degree of the polynomial dividing $x^n-1$. Ex n=3 $x^3-1=0$ $(x-1)(1+x+x^2) = x+x^2+x^3-1-x-x^2=x^3-1$, so $x^3-1$ has divisors $x-1$ and $x^2+x+1$ Note: $x^2+x+1$ has no divisors over $\mathbb{F}_{2}$ Possible codes to $\mathbb{F}_{2}^3$ are given by the polynomials:
$x-1=x+1$
$x^2+x+1$

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 $x + 1$ or $x^2+x+1$. 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= $\left( \begin{array}{ccc} 1&1&0 0&1&1 \end{array} \right)$ 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. $x^2+x+1$ G= $\left( \begin{array}{ccc} 1&1&1 \end{array} \right)$ 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 $x^4-1$. The divisors for this polynomial are $x + 1$, $x^2+1$, and $x^3+x^2+x+1$. Although we had the divisor $x + 1$ when n=3, the generating matrix here will be different. x+1 G= $\left( \begin{array}{cccc} 1&1&0&0 0&1&1&0\\ 0&0&1&1 \end{array} \right)$ k=4-1=3 $x^2+1$ G= $\left( \begin{array}{cccc} 1&0&1&0\\ 0&1&0&1 \end{array} \right)$ k=4-2=2 $x^3+x^2+x+1$ G= $\left( \begin{array}{cccc} 1&1&1&1 \end{array} \right)$ k=4-3=1

In the previous two linear codes, we constructed the generating matrix by defining the generating matrix G as G=(I$\pm P^t$). Because we constructed the generating matrix first in the cyclic codes, we can derive the matrix $P^t$ by putting the G matrix in reduced row echelon form and taking the submatrix for $P^t$. Finding $P^t$ From the example where n=3, we know that the generating matrix for $x + 1$ is G= $$\left( \begin{array}{ccc} 1&1&0 0&1&1 \end{array} \right)\... ...w \left( \begin{array}{ccc} 1&0&1 0&1&1 \end{array} \right)$$ If we block out the nested identity matrix, we are left with $P^t=\left( \begin{array}{c} 1 1 \end{array}\right)$.