Cyclic code: Article and Information about Cyclic code

Cyclic code - Fuhz Articles
Visually Impaired Edition.

Cyclic code article, this Fuhz page will hopefully provide the answers to the who, what where and why on the Cyclic code topic.
At the bottom of the page we often provide links to external documents relating to Cyclic code which may also help your research. Every effort is made to ensure the content on this page is as accurate and error free as possible, however whenever researching information that requires the utmost accuracy such as a term paper it is always best to cross reference facts with numerous sources.

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

1 Definition
2 Algebraic structure
3 Examples
4 Generalizations
5 See also
6 Notes
7 References
8 External links

Definition

Let C be a linear code over a finite field $G F (q)$ 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 $G F (q n)$ 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 n - 1)$ . Identify the elements of the cyclic code C with polynomials in R such that $( c_0, \ldots, c_{n-1} )$ maps to the polynomial $c_0 + x c_1+\cdots+c_{n-1} x^{n-1}$ : 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.¹ This must be a divisor of $x n - 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;² 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= $\mathbb{F}_2$ 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 $\mathbb{F}_2[x]/(x^3-1)$ 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 n - 1$ respectively: these two polynomials must always be factors of $x n - 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 n - 1$ .

Hamming code

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

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 $\sqrt{p}$ over $G F (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.⁵ 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.⁶

Notes

^ van Lint, p.76
^ van Lint, p.80
^ Hill, 1988, pp.141,163
^ Hill, 1988 p.163
^ van Lint, p.75
^ ^a ^b MacWilliams and Sloane, p.506

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 Creative Commons Attribution/Share-Alike License.

Return to Fuhz Home - This article covering Cyclic code is enhanced for the visually impaired.

Article from Wikipedia. All text is available under the terms of the GNU Free Documentation License - Our Privacy Policy - Thanks Auto Blog Commenter

Contents