[Jump to code hierarchy]

Cyclic linear binary code

Description

A binary 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=2^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.

Protection

Shift bound [1] gives a lower bound on the distance of cyclic binary codes.

Decoding

Meggitt decoder [2].Information set decoding (ISD) [3], a probabilistic decoding strategy that essentially tries to guess \(k\) correct positions in the received word, where \(k\) is the size of the code. Then, an error vector is constructed to map the received word onto the nearest codeword, assuming the \(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 [4].

Notes

See Ch. 7 of Ref. [5] for an exposition on cyclic codes.See Ref. [6] for tables of the best binary cyclic codes of odd lengths 101 to 127.

Cousins

  • Binary linear LTC— Cyclic linear codes cannot be \(c^3\)-LTCs [7]. Codeword symmetries are in general an obstruction to achieving such LTCs [8].
  • Reed-Muller (RM) code— Punctured RM codes are cyclic ([5], Ch. 13, Thm. 11), making RM codes extended cyclic codes. RM codes with nonzero evaluation points are cyclic [9][10; pg. 52].
  • Majorana stabilizer code— Cyclic binary linear codes can be used to construct translation-invariant Majorana stabilizer codes, provided that they are also self-orthogonal [11].
  • CSS-T code— Binary cyclic and extended cyclic codes can be used to construct CSS-T codes via the CSS construction [12].
  • Generalized homological-product qubit CSS code— Iterative tensor-product codes can be constructed out of CSS codes that in turn stem from cyclic codes [13].
  • Rotated surface code— The rotated code can be obtained from hypergraph product of two cyclic linear binary codes with palindromic generator polynomial [14; Exam. 7].

Member of code lists

Primary Hierarchy

Classical Domain
Binary Kingdom
Binary codeECC
Binary group-orbit codeECC
Linear binary codeLinear \(q\)-ary Linear code over \(\mathbb{Z}_q\) ECC
Parents
Linear binary code
Cyclic linear \(q\)-ary codeLinear \(q\)-ary Cyclic Constacyclic Skew-cyclic ECC
Cyclic linear binary code
Children
Binary BCH code
Binary duadic code
Gold code
Kasami code
Melas code
Zetterberg code
Cyclic redundancy check (CRC) code
Repetition code
The repetition code is cyclic with generator polynomial \(1+x+\cdots+x^{n-1}\).
One-hot code
Difference-set cyclic (DSC) code

References

[1]
J. van Lint and R. Wilson, “On the minimum distance of cyclic codes”, IEEE Transactions on Information Theory 32, 23 (1986) DOI
[2]
J. Meggitt, “Error correcting codes and their implementation for data transmission systems”, IEEE Transactions on Information Theory 7, 234 (1961) DOI
[3]
E. Prange, “The use of information sets in decoding cyclic codes”, IEEE Transactions on Information Theory 8, 5 (1962) DOI
[4]
J. Macwilliams, “Permutation Decoding of Systematic Codes”, Bell System Technical Journal 43, 485 (1964) DOI
[5]
F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
[6]
D. Schomaker and M. Wirtz, “On binary cyclic codes of odd lengths from 101 to 127”, IEEE Transactions on Information Theory 38, 516 (1992) DOI
[7]
L. Babai, A. Shpilka, and D. Stefankovic, “Locally Testable Cyclic Codes”, IEEE Transactions on Information Theory 51, 2849 (2005) DOI
[8]
M. Sudan, “Invariance in Property Testing”, Lecture Notes in Computer Science 211 (2010) DOI
[9]
M. Tsfasman, S. Vlǎduţ, and D. Nogin. Algebraic geometric codes: basic notions. Vol. 139. American Mathematical Society, 2022.
[10]
M. A. Tsfasman and S. G. Vlăduţ, Algebraic-Geometric Codes (Springer Netherlands, 1991) DOI
[11]
S. Vijay and L. Fu, “Quantum Error Correction for Complex and Majorana Fermion Qubits”, (2017) arXiv:1703.00459
[12]
E. Camps-Moreno, H. H. López, G. L. Matthews, D. Ruano, R. San-José, and I. Soprunov, “An algebraic characterization of binary CSS-T codes and cyclic CSS-T codes for quantum fault tolerance”, Quantum Information Processing 23, (2024) arXiv:2312.17518 DOI
[13]
B. Audoux and A. Couvreur, “On tensor products of CSS Codes”, (2018) arXiv:1512.07081
[14]
A. A. Kovalev and L. P. Pryadko, “Improved quantum hypergraph-product LDPC codes”, 2012 IEEE International Symposium on Information Theory Proceedings 348 (2012) arXiv:1202.0928 DOI
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

edit on this site

Zoo Code ID: binary_cyclic

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

Cite as:

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

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/bits/cyclic/binary_cyclic.yml.