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.
Parents
Children
- Binary BCH code
- Binary duadic code
- Gold code
- Melas code
- Zetterberg code
- One-hot code
- Single parity-check (SPC) code — Since permutations preserve parity, the cyclic permutation of an SPC codeword is another codeword. The generator polynomial of the code is \(x-1\).
- Repetition code — The repetition code is cyclic with generator polynomial \(1+x+\cdots+x^{n-1}\).
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], 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 [10].
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”, Property Testing 211 (2010) DOI
- [9]
- M. A. Tsfasman and S. G. Vlăduţ, Algebraic-Geometric Codes (Springer Netherlands, 1991) DOI
- [10]
- S. Vijay and L. Fu, “Quantum Error Correction for Complex and Majorana Fermion Qubits”, (2017) arXiv:1703.00459
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