Cyclic code

In coding theory, a cyclic code is a block code, where the circular shifts of each codeword gives another word that belongs to the code. They are error-correcting codes that have algebraic properties that are convenient for efficient error detection and correction.

Definition
Let  be a linear code over a finite field (also called  Galois field)  of block length .  is called a cyclic code if, for every codeword  from , the word  in  obtained by a cyclic right shift of components is again a codeword. Because one cyclic right shift is equal to  cyclic left shifts, a cyclic code may also be defined via cyclic left shifts. Therefore, the linear code  is cyclic precisely when it is invariant under all cyclic shifts.

Cyclic codes have some additional structural constraint on the codes. They are based on Galois fields and because of their structural properties they are very useful for error controls. Their structure is strongly related to Galois fields because of which the encoding and decoding algorithms for cyclic codes are computationally efficient.

Algebraic structure
Cyclic codes can be linked to ideals in certain rings. Let   be a polynomial ring over the finite field .   Identify the elements of the cyclic code  with polynomials in  such that 
 maps to the polynomial 
: thus multiplication by  corresponds to a cyclic shift. Then  is an ideal in , and hence principal, since  is a principal ideal ring.  The ideal is generated by the unique monic element in  of minimum degree, the generator polynomial .
This must be a divisor of . It follows that every cyclic code is a polynomial code.
If the generator polynomial  has degree  then the rank of the code  is .

The idempotent of  is a codeword  such that  (that is,  is an idempotent element of ) and  is an identity for the code, that is  for every codeword .  If  and  are coprime such a word always exists and is unique; it is a generator of the code.

An irreducible code is a cyclic code in which the code, as an ideal is irreducible, i.e. is minimal in , so that its check polynomial is an irreducible polynomial.

Examples
For example, if  and , the set of codewords contained in cyclic code generated by  is precisely

.

It corresponds to the ideal in  generated by .

The polynomial  is irreducible in the polynomial ring, and hence the code is an irreducible code.

The idempotent of this code is the polynomial , corresponding to the codeword .

Trivial examples
Trivial examples of cyclic codes are  itself and the code containing only the zero codeword.  These correspond to generators  and  respectively: these two polynomials must always be factors of .

Over  the parity bit code, consisting of all words of even weight, corresponds to generator .  Again over  this must always be a factor of .

Quasi-cyclic codes and shortened codes

Before delving into the details of cyclic codes first we will discuss quasi-cyclic and shortened codes which are closely related to the cyclic codes and they all can be converted into each other.

Definition

Quasi-cyclic codes:

An  quasi-cyclic code is a linear block code such that, for some  which is coprime to , the polynomial  is a codeword polynomial whenever  is a codeword polynomial.

Here, codeword polynomial is an element of a linear code whose code words are polynomials that are divisible by a polynomial of shorter length called the generator polynomial. Every codeword polynomial can be expressed in the form , where  is the generator polynomial. Any codeword  of a cyclic code  can be associated with a codeword polynomial, namely, . A quasi-cyclic code with  equal to  is a cyclic code.

Definition
Shortened codes:

An  linear code is called a proper shortened cyclic code if it can be obtained by deleting  positions from an  cyclic code.

In shortened codes information symbols are deleted to obtain a desired blocklength smaller than the design blocklength. The missing information symbols are usually imagined to be at the beginning of the codeword and are considered to be 0. Therefore, − is fixed, and then  is decreased which eventually decreases . It is not necessary to delete the starting symbols. Depending on the application sometimes consecutive positions are considered as 0 and are deleted.

All the symbols which are dropped need not be transmitted and at the receiving end can be reinserted. To convert  cyclic code to  shortened code, set  symbols to zero and drop them from each codeword.  Any cyclic code can be converted to quasi-cyclic codes by dropping every th symbol where  is a factor of . If the dropped symbols are not check symbols then this cyclic code is also a shortened code.

Cyclic codes for correcting errors

Now, we will begin the discussion of cyclic codes explicitly with error detection and correction. Cyclic codes can be used to correct errors, like Hamming codes as cyclic codes can be used for correcting single error. Likewise, they are also used to correct double errors and burst errors. All types of error corrections are covered briefly in the further subsections.

The (7,4) Hamming code has a generator polynomial . This polynomial has a zero in Galois extension field  at the primitive element , and all codewords satisfy . Cyclic codes can also be used to correct double errors over the field . Blocklength will be  equal to  and primitive elements  and  as zeros in the  because we are considering the case of two errors here, so each will represent one error.

The received word is a polynomial of degree  given as

where  can have at most two nonzero coefficients corresponding to 2 errors.

We define the Syndrome Polynomial,  as the remainder of polynomial  when divided by the generator polynomial  i.e.

 as .

For correcting two errors

Let the field elements  and  be the two error location numbers. If only one error occurs then  is equal to zero and if none occurs both are zero.

Let  and .

These field elements are called "syndromes". Now because  is zero at primitive elements  and , so we can write  and . If say two errors occur, then

 and 
.

And these two can be considered as two pair of equations in  with two unknowns and hence we can write

 and 
.
 
Hence if the two pair of nonlinear equations can be solved cyclic codes can used to correct two errors.

Hamming code
The Hamming(7,4) code may be written as a cyclic code over GF(2) with generator . In fact, any binary Hamming code of the form Ham(r, 2) is equivalent to a cyclic code, and any Hamming code of the form Ham(r,q) with r and q-1 relatively prime is also equivalent to a cyclic code.  Given a Hamming code of the form Ham(r,2) with , the set of even codewords forms a cyclic -code.

Hamming code for correcting single errors

A code whose minimum distance is at least 3, have a check matrix all of whose columns are distinct and non zero. If a check matrix for a binary code has  rows, then each column is an -bit binary number. There are  possible columns. Therefore, if a check matrix of a binary code with  at least 3 has  rows, then it can only have  columns, not more than that. This defines a  code, called Hamming code.

It is easy to define Hamming codes for large alphabets of size . We need to define one  matrix with linearly independent columns. For any word of size  there will be columns who are multiples of each other. So, to get linear independence all non zero -tuples with one as a top most non zero element will be chosen as columns. Then two columns will never be linearly dependent because three columns could be linearly dependent with the minimum distance of the code as 3.

So, there are  nonzero columns with one as top most non zero element. Therefore, a Hamming code is a  code.

Now, for cyclic codes, Let  be primitive element in , and let . Then  and thus  is a zero of the polynomial  and is a generator polynomial for the cyclic code of block length .

But for , . And the received word is a polynomial of degree   given as

where,  or  where  represents the error locations.

But we can also use  as an element of  to index error location. Because , we have  and all powers of  from  to  are distinct. Therefore, we can easily determine error location  from  unless  which represents no error. So, a Hamming code is a single error correcting code over  with  and .

Cyclic codes for correcting burst errors
From Hamming distance concept, a code with minimum distance  can correct any  errors. But in many channels error pattern is not very arbitrary, it occurs within very short segment of the message. Such kind of errors are called burst errors. So, for correcting such errors we will get a more efficient code of higher rate because of the less constraints. Cyclic codes are used for correcting burst error. In fact, cyclic codes can also correct cyclic burst errors along with burst errors. Cyclic burst errors are defined as

A cyclic burst of length  is a vector whose nonzero components are among  (cyclically) consecutive components, the first and the last of which are nonzero.

In polynomial form cyclic burst of length  can be described as  with  as a polynomial of degree  with nonzero coefficient . Here  defines the pattern and  defines the starting point of error. Length of the pattern is given by deg.  The syndrome polynomial is unique for each pattern and is given by

A linear block code that corrects all burst errors of length  or less must have at least  check symbols. Proof: Because any linear code that can correct burst pattern of length  or less cannot have a burst of length  or less as a codeword because if it did then a burst of length  could change the codeword to burst pattern of length , which also could be obtained by making a burst error of length  in all zero codeword. Now, any two vectors that are non zero in the first  components must be from different co-sets of an array to avoid their difference being a codeword of bursts of length . Therefore, number of such co-sets are equal to number of such vectors which are . Hence at least  co-sets and hence at least  check symbol.

This property is also known as Rieger bound and it is similar to the Singleton bound for random error correcting.

Fire codes as cyclic bounds
In 1959, Philip Fire presented a construction of cyclic codes generated by a product of a binomial and a primitive polynomial. The binomial has the form  for some positive odd integer . Fire code is a cyclic burst error correcting code over  with the generator polynomial

where  is a prime polynomial with degree  not smaller than  and  does not divide . Block length of the fire code is the smallest integer  such that  divides
.

A fire code can correct all burst errors of length t or less if no two bursts  and  appear in the same co-set. This can be proved by contradiction. Suppose there are two distinct nonzero bursts  and  of length  or less and are in the same co-set of the code. So, their difference is a codeword. As the difference is a multiple of  it is also a multiple of . Therefore,

.

This shows that  is a multiple of , So

for some . Now, as  is less than  and  is less than  so  is a codeword. Therefore,

.

Since  degree is less than degree of , cannot divide . If  is not zero, then  also cannot divide  as  is less than  and by definition of ,  divides  for no  smaller than . Therefore  and  equals to zero. That means both that both the bursts are same, contrary to assumption.

Fire codes are the best single burst correcting codes with high rate and they are constructed analytically. They are of very high rate and when   and  are equal, redundancy is least and is equal to . By using multiple fire codes longer burst errors can also be corrected.

For error detection cyclic codes are widely used and are called  cyclic redundancy codes.

Cyclic codes on Fourier transform
Applications of Fourier transform are widespread in signal processing. But their applications are not limited to the complex fields only; Fourier transforms also exist in the Galois field . Cyclic codes using Fourier transform can be described in a setting closer to the signal processing.

Fourier transform over finite fields
Fourier transform over finite fields
   
The discrete  Fourier transform of vector   is given by a vector  where,

 =  where,

where exp() is an th root of unity. Similarly in the finite field th root of unity is element  of order . Therefore

If  is a vector over , and  be an element of  of order , then Fourier transform of the vector  is the vector  and components are given by

 =  where,

Here  is time index,  is frequency and  is the spectrum. One important difference between Fourier transform in complex field and Galois field is that complex field  exists for every value of  while in Galois field  exists only if  divides . In case of extension fields, there will be a Fourier transform in the extension field   if  divides  for some .  
In Galois field time domain vector  is over the field  but the spectrum  may be over the extension field .

Spectral description of cyclic codes
Any codeword of cyclic code of blocklength  can be represented by a polynomial  of degree at most . Its encoder can be written as . Therefore, in frequency domain encoder can be written as . Here codeword spectrum  has a value in  but all the components in the time domain are from . As the data spectrum  is arbitrary, the role of  is to specify those  where  will be zero.

Thus, cyclic codes can also be defined as

Given a set of spectral indices, ,  whose elements are called check frequencies,  the cyclic code  is the set of words over  whose spectrum is zero in the components indexed by . Any such spectrum  will have components of the form .

So, cyclic codes are vectors in the field  and the spectrum given by its inverse fourier transform is over the field  and are constrained to be zero at certain components. But every spectrum in the field  and zero at certain components may not have inverse transforms with components in the field . Such spectrum can not be used as cyclic codes.

Following are the few bounds on the spectrum of cyclic codes.

BCH bound
If  be a factor of  for some . The only vector in  of weight  or less that has  consecutive components of its spectrum equal to zero is all-zero vector.

Hartmann-Tzeng bound
If  be a factor of  for some , and  an integer that is coprime with . The only vector  in  of weight  or less whose spectral 
components  equal zero for , where  and , is the all zero vector.

Roos bound
If  be a factor of  for some  and . The only vector in 
 of weight  or less whose spectral components  equal to zero for , where  and  takes at least  values in the range , is the all-zero vector.

Quadratic residue codes
When the prime  is a quadratic residue modulo the prime  there is a quadratic residue code which is a cyclic code of length , dimension  and minimum weight at least  over .

Generalizations
A constacyclic code is a linear code with the property that for some constant λ if (c1,c2,...,cn) is a codeword then so is (λcn,c1,...,cn-1).  A negacyclic code is a constacyclic code with λ=-1.  A quasi-cyclic code has the property that for some s, any cyclic shift of a codeword by s places is again a codeword.  A double circulant code is a quasi-cyclic code of even length with s=2. Quasi-twisted codes and multi-twisted codes are further generalizations of constacyclic codes.

See also
 Cyclic redundancy check
 BCH code
 Reed–Muller code
 Binary Golay code
 Ternary Golay code
 Eugene Prange

Notes

References

Further reading
 Ranjan Bose, Information theory, coding and cryptography, 
 Irving S. Reed and Xuemin Chen, Error-Control Coding for Data Networks, Boston: Kluwer Academic Publishers, 1999, .
 Scott A. Vanstone, Paul C. Van Oorschot, An introduction to error correcting codes with applications,

External links
 John Gill's (Stanford) class notes – Notes #3, October 8, Handout #9, EE 387.
 Jonathan Hall's (MSU) class notes – Chapter 8. Cyclic codes - pp. 100 - 123
 

Coding theory
Finite fields