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. For odd \(n\), cyclic binary codes can also be described by defining sets of roots of generator polynomials, and by equivalent generating-idempotent and trace constructions [1; Secs. 2.3 and 2.4].
Protection
The BCH and Hartmann-Tzeng bounds give lower bounds on the distance of cyclic binary 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][1; Secs. 2.1-2.4] for expositions on cyclic codes.See Ref. [7] 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 [8]. Codeword symmetries are in general an obstruction to achieving such LTCs [9].
- Reed-Muller (RM) code— Punctured RM codes, i.e., RM codes with nonzero evaluation points, are cyclic [10][6; Ch. 13, Thm. 11][1; Sec. 2.8][11; pg. 52], making RM codes extended cyclic codes.
- Majorana stabilizer code— Cyclic binary linear codes can be used to construct translation-invariant Majorana stabilizer codes, provided that they are also self-orthogonal [12].
- CSS-T code— Binary cyclic and extended cyclic codes can be used to construct CSS-T codes via the CSS construction [13].
- Higher-dimensional homological product code— Higher-dimensional homological-product codes can be constructed out of CSS codes that in turn stem from cyclic codes [14; Sec. 4.2].
- Quantum synchronizable code— The original construction of quantum synchronizable codes is based on pairs of binary cyclic codes satisfying \(C^\perp \subseteq C \subset D\) [15].
- Rotated surface code— Periodic checkerboard or rotated-toric codes on the same lattice can be obtained from hypergraph products of two cyclic linear binary codes with palindromic check polynomials [16; Sec. IV.D].
Primary Hierarchy
Parents
Cyclic linear binary code
Children
The repetition code is cyclic with generator polynomial \(1+x+\cdots+x^{n-1}\).
Simplex codes can be realized as maximal-length feedback-shift-register codes, and are therefore cyclic [6; pgs. 89 and 216].
References
- [1]
- C. Ding, “Cyclic Codes over Finite Fields.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [2]
- J. van Lint and R. Wilson, “On the minimum distance of cyclic codes”, IEEE Transactions on Information Theory 32, 23 (1986) DOI
- [3]
- J. Meggitt, “Error correcting codes and their implementation for data transmission systems”, IEEE Transactions on Information Theory 7, 234 (1961) DOI
- [4]
- E. Prange, “The use of information sets in decoding cyclic codes”, IEEE Transactions on Information Theory 8, 5 (1962) DOI
- [5]
- J. Macwilliams, “Permutation Decoding of Systematic Codes”, Bell System Technical Journal 43, 485 (1964) DOI
- [6]
- F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
- [7]
- 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
- [8]
- L. Babai, A. Shpilka, and D. Stefankovic, “Locally Testable Cyclic Codes”, IEEE Transactions on Information Theory 51, 2849 (2005) DOI
- [9]
- M. Sudan, “Invariance in Property Testing”, Lecture Notes in Computer Science 211 (2010) DOI
- [10]
- M. Tsfasman, S. Vlǎduţ, and D. Nogin. Algebraic geometric codes: basic notions. Vol. 139. American Mathematical Society, 2022.
- [11]
- M. A. Tsfasman and S. G. Vlăduţ, Algebraic-Geometric Codes (Springer Netherlands, 1991) DOI
- [12]
- S. Vijay and L. Fu, “Quantum Error Correction for Complex and Majorana Fermion Qubits”, (2017) arXiv:1703.00459
- [13]
- 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
- [14]
- B. Audoux and A. Couvreur, “On tensor products of CSS Codes”, (2018) arXiv:1512.07081
- [15]
- Y. Fujiwara, “Block synchronization for quantum information”, Physical Review A 87, (2013) arXiv:1206.0260 DOI
- [16]
- 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
- Mazin Karjikar (2022-12-30) — most recent
- Victor V. Albert (2022-07-13)
Cite as:
“Cyclic linear binary code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/binary_cyclic