Cyclic code

In mathematics of coding theory and digital communications, cyclic codes find an important application in error detection and correction.

Definition

Let C be a linear code over a finite field A of block length n. C is called a cyclic code, if for every codeword c=(c₁,...,c_n) from C, the word (c_n,c₁,...,c_n-1) in Aⁿ obtained by a cyclic right shift of components is again a codeword.

Algebraic structure

Cyclic codes can be linked to ideals in certain rings. Let R = A[x] / (xⁿ − 1). Identify the elements of the cyclic code C with polynomials in R such that maps to the polynomial : thus multiplication by x corresponds to a cyclic shift. Then C is an ideal in R, and hence principal, since R is a principal ideal ring. The ideal is generated by the unique monic element in C of minimum degree, the generator polynomial g.^[1] This must be a divisor of xⁿ − 1. It follows that every cyclic code is a polynomial code. If the generator polynomial g has degree d then the rank of the code C is n − d.

The idempotent of C is a codeword e such that e² = e (that is, e is an idempotent element of C) and e is an identity for the code, that is e c = c for every codeword c. Such a word always exists and is unique;^[2] it is a generator of the code.

An irreducible code is a cyclic code in which the code, as an ideal, is minimal in R, so that its generator is an irreducible polynomial.

Examples

For example, if A= and n=3, the codewords contained in the (1,1,0)-cyclic code are precisely

(0,0,0),(1,1,0),(0,1,1) and (1,0,1).

It corresponds to the ideal in generated by (1 + x).

Trivial examples

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

Over GF(2) the parity bit code, consisting of all words of even weight, corresponds to generator x + 1. Again over GF(2) this must always be a factor of xⁿ − 1.

Hamming code

The Hamming(7,4) code may be written as a cyclic code over GF(2) with generator 1 + x + x³. In fact, any binary Hamming code of the form Ham(2,q) is equivalent to a cyclic code when q is even.^[3] Hamming codes of the form Ham(r,2) are also cyclic when - they are [2^r − 1,2^r − r − 2,4]-codes.^[4]

Quadratic residue codes

When the prime l is a quadratic residue modulo the prime p there is a quadratic residue code which is a cyclic code of length p, dimension (p + 1) / 2 and minimum weight at least over GF(l).

Generalizations

A constacyclic code is a linear code with the property that for some constant λ if (c₁,c₂,...,c_n) is a codeword then so is (λc_n,c₁,...,c_n-1). A negacyclic code is a constacyclic code with λ=-1.^[5] A quasi-cyclic code has the property that for some s, any cyclic shift of a codeword by s places is again a codeword.^[6] A double circulant code is a quasi-cyclic code of even length with s=2.^[6]

See also

• Cyclic redundancy check

Notes

References

• J.H. Van Lint, Introduction to Coding Theory (3rd ed), Graduate Texts in Mathematics 86, Springer Verlag, 1998. ISBN 3-540-64133-5. Chapter 6.
• Hill, Raymond. A First Course In Coding Theory, Oxford University Press, 1988, ISBN 0-19-853803-0. Chapter 12.
• F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, New York: North-Holland Publishing, 1977, ISBN 0444850112.
• Irving S. Reed and Xuemin Chen, Error-Control Coding for Data Networks, Boston: Kluwer Academic Publishers, 1999, ISBN 0792385284.

External links

• David Terr, "Cyclic Code" from MathWorld.

This article incorporates material from cyclic code on PlanetMath, which is licensed under the GFDL.