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.
Parents
- Cyclic code
- Linear binary code
- Group code — A length-\(n\) cyclic binary linear code is an abelian group code for the cyclic group with \(n\) elements \( \mathbb{Z}_n \).
Children
- Binary BCH code
- Binary duadic code
- One-hot code
- Parity-check code — Since permutations preserve parity, the cyclic permutation of a parity-check codeword is another codeword.
- Repetition code
- Zetterberg code
Cousins
- Majorana stabilizer code — Cyclic binary linear codes can be used to construct translation-invariant Majorana stabilizer codes, provided that they are also self-orthogonal [4].
- 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 ([5], 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]
- Sagar Vijay and Liang Fu, “Quantum Error Correction for Complex and Majorana Fermion Qubits”. 1703.00459
- [5]
- M. A. Tsfasman and S. G. Vlăduţ, Algebraic-geometric Codes (Springer Netherlands, 1991). DOI
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