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].

Notes

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

Parents

Children

Cousins

  • Binary linear LTC — Cyclic linear codes cannot be \(c^3\)-LTCs [5]. Codeword symmetries are in general an obstruction to achieving such LTCs [6].
  • Majorana stabilizer code — Cyclic binary linear codes can be used to construct translation-invariant Majorana stabilizer codes, provided that they are also self-orthogonal [7].
  • Reed-Muller (RM) code — Punctured RM codes are cyclic ([3], Ch. 13, Thm. 11), making RM codes extended cyclic codes. RM codes with nonzero evaluation points are cyclic ([8], pg. 52).

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]
F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
[4]
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
[5]
L. Babai, A. Shpilka, and D. Stefankovic, “Locally Testable Cyclic Codes”, IEEE Transactions on Information Theory 51, 2849 (2005). DOI
[6]
M. Sudan, “Invariance in Property Testing”, Property Testing 211 (2010). DOI
[7]
Sagar Vijay and Liang Fu, “Quantum Error Correction for Complex and Majorana Fermion Qubits”. 1703.00459
[8]
M. A. Tsfasman and S. G. Vlăduţ, Algebraic-geometric Codes (Springer Netherlands, 1991). DOI
Page edit log

Zoo code information

Internal code ID: binary_cyclic

Your contribution is welcome!

on github.com (edit & pull request)

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 |  | 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/tree/main/codes/classical/bits/cyclic/binary_cyclic.yml.