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
- Cyclic code
- Linear binary code
- Group-algebra code — A length-\(n\) cyclic binary linear code is an abelian group-algebra code for the cyclic group with \(n\) elements \( \mathbb{Z}_n \).
Children
- Binary BCH code
- Binary duadic code
- One-hot code
- Repetition code
- Single parity-check (SPC) code — Since permutations preserve parity, the cyclic permutation of an SPC codeword is another codeword.
- Zetterberg code
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
- Victor V. Albert (2022-07-13) — most recent
Zoo code information
Cite as:
“Cyclic linear binary code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/binary_cyclic