Introduction:

     Cyclic codes are a sub-class of linear block codes, considered to be the most important class. Where we can derive many other codes and too which many other codes are equivalent. A linear code C is cyclic if x0 ... xn in C implies xn ... xn-1 in C. A cyclic codes can easily be created by performing  right cyclic shifts on an initial codeword, developing a new code-word with each shift, which continues until the original codeword is obtained. Put simply, all the elements of a codeword are shifted one space to the right and the element on the end moves to the beginning of the codeword.

  
 

 

 

  
 

In order to better understand and study cyclic codes we map them to polynomials. From this the cyclic codes can not only be produced by matrices, but by polynomials as well. The structure of these cyclic codes allows for them to be encoded and decoded through simple feedback circuitry.

  
   

 

Polynomials:

     Binary cyclic codes, for purposes you'll see later, are often thought of as strings of polynomials. We use a  isomorphic mapping Zn to Rn(Z2), where Rn(Z2) is polynomials with coefficients from the alphabet Z2 under modulo(xn - 1),   associate the elements of a cyclic codeword to the coefficients of a polynomial, where addition and scalar multiplication are preserved (from now on we will use Rn to represent Rn(Z2)) . In the case for binary cyclic codes, the element cj (from 0 to n-1) becomes the coefficient of the xj variable in the associated polynomial. From this association we are able to think of cyclic codes (or any string) as polynomials and vice versa.

  
   


 

 

  
 

In order to perform the right cyclic shift in polynomial form, we use multiplication modulo, where we multiply the polynomial codeword by x and then take the modulo(xn-1) of that product, thus performing the cyclic shift. To apply multiple shifts at once we can simply multiply the polynomial codeword by xj, where j is the number of cyclic shifts to occur.

  
 

 

 

  
   

 

Code Generators:

     A complete cyclic code can be generated strictly from a single polynomial. This polynomial, denoted g(x), is known as the generator polynomial and is described in the following formula:

  
 


Theorem 1
Let C be a cyclic code in Rn. Then a unique polynomial g(x) in C that is monic and has the smallest degree among all nonzero polynomials in C. Moreover, C = <g(x)>
 

  

 

From this theorem we get our generator polynomial g(x) for any given cyclic code C in Rn, where Rn is the set of polynomials under modulo(xn - 1).  So, with this idea we can form cyclic codes from a given g(x) or derive g(x) from a cyclic code already obtained.

  
   


 

  
 

     From other examples you can see that codes can be generated by different polynomials, but only one of these is the generator polynomial, so by using the first theorem and the definition of a monic polynomial we obtain  a better definition of a generator polynomial and how to find it.

  
 


Theorem 1a
A monic polynomial p(x) in Rn(Zp) is the generator polynomial of a cyclic code in Rn if and only if it divides xn-1.

 

      Along with the generator polynomial, we can also use a matrix to generate a cyclic code C. From the following formula we can derive the generator matrix of a cyclic code C. However, you can see that the matrix generator G is based on the polynomial generator g(x). Implying the importance of the polynomial idea in cyclic codes.

  
 


Theorem 2
Let C be a nonzero cyclic code in Rn with generator polynomial g(x) = g0 + g1x + ... + gkxk of degree k. Then C has a basis B = [g(x), xg(x), ... , xn-k-1g(x)] and a generator matrix G(x) =

whose (n-k) rows each consist of a right cyclic shift of the row above it.



 

  
   

 

Decoding of Cyclic Codes:

     For our purposes, decoding will refer to the situation when a codeword is received that is not contained in the given code C. First we must determine if the codeword received is in C or not, then (if not) we must determine the closest codeword in C. In order to determine if the code we received is in fact a codeword from C, we implement the help of a check polynomial. A check polynomial is a polynomial h(x) such that xn - 1 = h(x) * g(x). It is used in the following theorem, where we find the criteria for determining the validity of a codeword.

  
 


Theorem 3
Let C be a cyclic code in Rn, with check polynomial h(x). Then a polynomial p(x) in Rn is in C if and only if p(x)*h(x) = 0 in Rn.

 

  
 


*Note: Examples 7 and 8 are in R4, not in R5 like the previous examples


 

  
 

The matrix H is the generator matrix for a code that is orthogonal to the cyclic code C. That is H is comprised of right cyclic shifts of the string h = hk hk-1 ... h0, where h is orthogonal to any codeword c = c0 c1 ... cn-1 in C. That is:
 

  
 

H =
 



 
 
  From this we acquire the following theorem:  
 


Theorem 4
If C is a cyclic code with check polynomial h(x), then the matrix H as defined above is a parity check matrix for C.