[Jump to code hierarchy]

Cyclic linear \(q\)-ary code

Description

A \(q\)-ary code of length \(n\) 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. A cyclic code is called primitive when \(n=q^r-1\) for some \(r\geq 2\). A shortened cyclic code is obtained from a cyclic code by taking only codewords with the first \(j\) zero entries, and deleting those zeroes.

Cyclic-to-polynomial correspondence

Cyclic-to-polynomial correspondence: Cyclic linear \(q\)-ary codes and their properties can be naturally formulated using the theory of polynomials. Codewords \(c_1 c_2 \cdots c_n\) of a cyclic \(q\)-ary 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]\). 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 \(\mathbb{F}_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. In the coprime case, cyclic codes also admit unique generating idempotents, parity-check polynomials, and trace representations [1; Secs. 2.3 and 2.4]. In the same setting, an irreducible cyclic code \(C(q,n,i)\) is the length-\(n\) cyclic code over \(\mathbb{F}_q\) whose parity-check polynomial is the minimal polynomial \(M_{\alpha^i}(x)\) of \(\alpha^i\), where \(\alpha\) is a primitive \(n\)th root of unity. Such codes are also called minimal cyclic codes because they correspond to minimal ideals of \(\mathbb{F}_q[x]/(x^n-1)\) [1; Sec. 2.5].

Protection

The BCH and Hartmann-Tzeng bounds give lower bounds on the distance of cyclic \(q\)-ary codes [1; Sec. 2.4]; the shift bound [2] gives another lower bound.

Decoding

Meggitt decoder [3].Information set decoding (ISD) [4], a probabilistic decoding strategy that essentially tries to guess an information set of \(k\) correct positions in the received word, where \(k\) is the code dimension. Then, an error vector is constructed to map the received word onto the nearest codeword, assuming those \(k\) positions are error-free. When the Hamming weight of the error vector is low enough, that codeword is assumed to be the intended transmission.Permutation decoding [5].

Notes

See [6; Ch. 7][7; Sec. 1.12][1; Secs. 2.1-2.4] for expositions.Any nontrivial \(q\)-ary linear code invariant under the general affine group \(GA(m,\mathbb{F}_{q^r})\) for some \(r > 1\) is equivalent to an extended cyclic code [8].

Cousins

  • \(q\)-ary linear LTC— Cyclic linear codes cannot be \(c^3\)-LTCs [9]. Codeword symmetries are in general an obstruction to achieving such LTCs [10].
  • Self-dual linear code— See Refs. [11,12] for tables of cyclic self-dual codes.
  • Combinatorial design— Two families of cyclic \(q\)-ary codes support an infinite family of combinatorial 3-designs [13]. The supports of all fixed-weight codewords of a \(q\)-ary cyclic code support a combinatorial \(1\)-design [14; Corr. 5.2.4].
  • Reversible code— A reversible cyclic code is a cyclic code with self-reciprocal generator polynomial and is an LCD code [1; Thm. 2.10.3].
  • Reed-Solomon (RS) code— If the length divides \(q-1\), then it is possible to construct a cyclic RS code. Such codes are Abelian group-algebra codes [15; Exam. 16.4.9].
  • Generalized RM (GRM) code— Punctured affine GRM codes, i.e., affine GRM codes with nonzero evaluation points, are cyclic, and their extensions recover affine GRM codes [1; Sec. 2.8][16; pg. 52].
  • Linear code with complementary dual (LCD)— A cyclic \([n,k]\) code with generator polynomial \(g(x)\) is LCD if and only if \(g(x)\) is self-reciprocal and \(\gcd( g(x), (x^{n}-1)/g(x) )=1\) [15; Cor. 16.7.11].
  • Projective geometry code— Every projective linear code is a punctured code of a special cyclic code [1; Thm. 2.3.6].
  • Quantum maximum-distance-separable (MDS) code— Quantum MDS codes can be constructed from \(q\)-ary cyclic codes using the Hermitian construction [17].
  • Quantum tensor-product code— Reversible cyclic codes can be used to construct quantum tensor-product codes [18].
  • Galois-qudit CSS code— Galois CSS codes can be constructed using self-orthogonal \(q\)-ary cyclic codes [19].

Primary Hierarchy

Parents
A length-\(n\) cyclic \(q\)-ary linear code is an Abelian group-algebra code for the cyclic group with \(n\) elements \( \mathbb{Z}_n \) [15; Exam. 16.4.9].
Cyclic linear \(q\)-ary code
Children
Since permutations preserve coordinate sums, the cyclic permutation of an SPC codeword is another codeword. The generator polynomial of the code is \(x-1\).
The \(q\)-ary repetition code is cyclic with generator polynomial \(1+x+\cdots+x^{n-1}\).

References

  1. [1]

    C. Ding, “Cyclic Codes over Finite Fields”, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021), pp. 45-60 DOI

  2. [2]

    J. van Lint and R. Wilson, “On the minimum distance of cyclic codes”, IEEE Transactions on Information Theory 32, 23 (1986) DOI

  3. [3]

    J. Meggitt, “Error correcting codes and their implementation for data transmission systems”, IEEE Transactions on Information Theory 7, 234 (1961) DOI

  4. [4]

    E. Prange, “The use of information sets in decoding cyclic codes”, IEEE Transactions on Information Theory 8, 5 (1962) DOI

  5. [5]

    J. Macwilliams, “Permutation Decoding of Systematic Codes”, Bell System Technical Journal 43, 485 (1964) DOI

  6. [6]

    F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes (Elsevier, 1977)

  7. [7]

    W. C. Huffman, J.-L. Kim, and P. Solé, “Basics of coding theory”, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021), pp. 3-44 DOI

  8. [8]

    P. Delsarte, “On cyclic codes that are invariant under the general linear group”, IEEE Transactions on Information Theory 16, 760 (1970) DOI

  9. [9]

    L. Babai, A. Shpilka, and D. Stefankovic, “Locally Testable Cyclic Codes”, IEEE Transactions on Information Theory 51, 2849 (2005) DOI

  10. [10]

    M. Sudan, “Invariance in Property Testing”, Lecture Notes in Computer Science 211 (2010) DOI

  11. [11]

    Yan Jia, San Ling, and Chaoping Xing, “On Self-Dual Cyclic Codes Over Finite Fields”, IEEE Transactions on Information Theory 57, 2243 (2011) DOI

  12. [12]

    S. Jitman, S. Ling, H. Liu, and X. Xie, “Abelian Codes in Principal Ideal Group Algebras”, IEEE Transactions on Information Theory 59, 3046 (2013) DOI

  13. [13]

    C. Ding, C. Tang, and V. D. Tonchev, “The Projective General Linear Group \(\mathrm{PGL}_2(\mathrm{GF}(2^m))\) and Linear Codes of Length \(2^m+1\)”, (2020) arXiv:2010.09448

  14. [14]

    V. D. Tonchev, “Codes and designs”, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021), pp. 97-110 DOI

  15. [15]

    W. Willems, “Codes in Group Algebras”, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021), pp. 363-384 DOI

  16. [16]

    M. A. Tsfasman and S. G. Vlăduţ, Algebraic-Geometric Codes (Springer Netherlands, 1991) DOI

  17. [17]

    G. G. La Guardia, “New Quantum MDS Codes”, IEEE Transactions on Information Theory 57, 5551 (2011) DOI

  18. [18]

    J. Fan, Y. Li, M.-H. Hsieh, and H. Chen, “On Quantum Tensor Product Codes”, (2017) arXiv:1605.09598

  19. [19]

    Y. Tang, S. Zhu, X. Kai, and J. Ding, “New quantum codes from dual-containing cyclic codes over finite rings”, (2016) arXiv:1608.06674

Page edit log

Your contribution is welcome!

on github.com (edit & pull request)

— see instructions

Zoo Code ID: q-ary_cyclic

Cite as:
“Cyclic linear \(q\)-ary code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2026. https://errorcorrectionzoo.org/c/q-ary_cyclic, arXiv:2606.11484
BibTeX:
@incollection{eczoo_q-ary_cyclic,
title={Cyclic linear \(q\)-ary code},
booktitle={The Error Correction Zoo},
year={2026},
editor={Albert, Victor V. and Faist, Philippe},
eprint={2606.11484},
doi={10.48550/arXiv.2606.11484},
url={https://errorcorrectionzoo.org/c/q-ary_cyclic}
}
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/q-ary_cyclic

Cite as:

“Cyclic linear \(q\)-ary code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2026. https://errorcorrectionzoo.org/c/q-ary_cyclic, arXiv:2606.11484

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/q-ary_digits/group/cyclic/q-ary_cyclic.yml.