Cyclic code[1][2][3][4][5]

Description

A code of length \(n\) over an alphabet is cyclic if, for each codeword \(c_1 c_2 \cdots c_n\), the cyclically shifted string \(c_n c_1 \cdots c_{n-1}\) is also a codeword.

Cyclic-to-polynomial correspondence

Cyclic-to-polynomial correspondence: Binary and \(q\)-ary cyclic codes and their properties can be naturally formulated using the theory of polynomials. Cyclic codes correspond to ideals in a particular polynomial ring. Codewords \(c_1 c_2 \cdots c_n\) of a \(q\)-ary Galois-field code can be thought of as coefficients in a polynomial \(c_1+c_2 x+\cdots+c_n x^{n-1}\) in the set of polynomials with \(q\)-ary coefficients, \(\mathbb{F}_q[x]\) with \(\mathbb{F}_q=GF(q)\). Polynomials corresponding to codewords of a linear cyclic code form an ideal (i.e., are closed under multiplication and addition) in the ring \(\mathbb{F}_q[x]/(x^n-1)\) (i.e., the set of equivalence classes of polynomials congruent modulo \(x^n-1\)). Multiplication of a codeword polynomial \(c(x)\) by \(x\) in such a ring corresponds to a cyclic shift of the corresponding codeword string.

Codeword polynomials of a cyclic code can be generated, via multiplication, by a generator polynomial \(g(x)\). A particular generator polynomial \(e(x)\) has the additional property of being idempotent, i.e., \(e(x)^2=e(x)\). Given a generator polynomial, the corresponding check polynomial \(h(x)=(x^n-1)/g(x)\) yields zero when multiplying a codeword polynomial. Its coefficients correspond to the code's parity check matrix.

Since the generator polynomial \(g(x)\) is a polynomial over \(GF(q)\), it can be factorized over some potentially larger splitting field (just like \(x^2+1\) can be factorized over the complex numbers but not the reals). Whenever \(q\) and \(n\) are relatively prime, cyclic codes can also be defined in terms of roots of \(g(x)\). Such roots are called zeroes of the code, and they are all powers of a primitive \(n\)th root of unity because \(g(x)\) is a divisor of \(x^n-1\). Since the generator polynomial generates all codeword polynomials \(c(x)\) by multiplication by \(x\), its zeroes are also zeroes of those polynomials.

Parent

Children

Cousins

  • Octacode — The octacode is a cyclic code over \(\mathbb{Z}_4\) with generator polynomial \(x^2+3x^2+2x+3\) extended by a parity check [6].
  • Quantum cyclic code

References

[1]
E. Prange, Cyclic Error-Correcting Codes in Two Symbols, TN-57-/03, (September 1957)
[2]
E. Prange, Some cyclic error-correcting codes with simple decoding algorithms, TN-58-156, (April 1958)
[3]
E. Prange, The use of coset equivalence in the analysis and decoding of group codes, TN-59-/64, (1959)
[4]
E. Prange, An algorithm for factoring xn - I over a finite field. TN-59-/75, (October 1959)
[5]
W. W. Peterson and E. J. Weldon, Error-correcting codes. MIT press 1972.
[6]
Self-dual Codes and Invariant Theory (Springer-Verlag, 2006). DOI
Page edit log

Zoo code information

Internal code ID: cyclic

Your contribution is welcome!

on github.com (edit & pull request)

edit on this site

Zoo Code ID: cyclic

Cite as:
“Cyclic code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/cyclic
BibTeX:
@incollection{eczoo_cyclic, title={Cyclic code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/cyclic} }
Share via:
Twitter |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/cyclic

Cite as:

“Cyclic code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/cyclic

Github: https://github.com/errorcorrectionzoo/eczoo_data/tree/main/codes/classical/properties/cyclic/cyclic.yml.