[Jump to code hierarchy]

Quasi-cyclic code[1]

Description

A block code of length \(n\) is quasi-cyclic if, for each codeword \(c_1 \cdots c_{\ell} c_{\ell+1} \cdots c_n\), the string \(c_{n-\ell+1} \cdots c_n c_1 \cdots c_{n-\ell}\), where each entry is cyclically shifted by \(\ell\) increments, is also a codeword. Code for which \(\ell = 1\) are cyclic, while codes for which \(\ell = 2\) are called double circulant.

The generator of an \([mn_0,mk_0]\) quasi-cyclic linear code is representable as a block matrix of \(m \times m\) circulant matrices [2,3].

Quasi-cyclic codes can also be understood in terms of the number of automorphism-group orbits required to generate all codewords. All codewords of a cyclic code can be obtained from any codeword via cyclic shifts, meaning that the code consists of only one orbit. On the other hand, quasi-cyclic codes consist of multiple disjoint orbits, meaning that not all of their codewords can be obtained from each other.

Notes

A database of quasi-cyclic codes with searchable parameters such as block length and dimension is constructed and displayed here.See [2; Ch. 16] for a review of double circulant codes.

Cousins

Member of code lists

Primary Hierarchy

Parents
Quasi-twisted codes with \(\alpha=1\) are quasi-cyclic.
Quasi-cyclic code
Children
Karlin double circulant codes can be mapped to extended cyclic and extended quadratic-residue codes over \(GF(4)\) [15,16][2; Ch. 16].
Quasi-cyclic codes with \(\ell=1\) are cyclic.

References

[1]
R. Townsend and E. Weldon, “Self-orthogonal quasi-cyclic codes”, IEEE Transactions on Information Theory 13, 183 (1967) DOI
[2]
F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
[3]
Thomas A. Gulliver, Construction of quasi-cyclic codes, Thesis, University of New Brunswick, 1989.
[4]
G. D. Forney, Jr., “Why quasi cyclic codes are interesting,” unpublished note, 1970.
[5]
G. Solomon and H. C. A. Tilborg, “A Connection Between Block and Convolutional Codes”, SIAM Journal on Applied Mathematics 37, 358 (1979) DOI
[6]
R. Michael Tanner, “Error-correcting coding system,” U.S. Patent 4295218, 1981.
[7]
R. Michael Tanner. Convolutional codes from quasi-cyclic codes: A link between the theories of block and convolutional codes. University of California, Santa Cruz, Computer Research Laboratory, 1987.
[8]
“Generalized tail-biting convolutional codes,” Ph.D. dissertation, Univ. of Massachusetts, Amherst, 1985.
[9]
Y. Levy and J. Costello, Jr., “An algebraic approach to constructing convolutional codes from quasi-cyclic codes,” DIMACS Ser. Discr. Math. and Theor. Comp. Sci., vol. 14, pp. 189–198, 1993.
[10]
M. Esmaeili, T. A. Gulliver, N. P. Secord, and S. A. Mahmoud, “A link between quasi-cyclic codes and convolutional codes”, IEEE Transactions on Information Theory 44, 431 (1998) DOI
[11]
M. Hagiwara, K. Kasai, H. Imai, and K. Sakaniwa, “Spatially Coupled Quasi-Cyclic Quantum LDPC Codes”, (2011) arXiv:1102.3181
[12]
A. M. Steane, “Space, Time, Parallelism and Noise Requirements for Reliable Quantum Computing”, Fortschritte der Physik 46, 443 (1998) arXiv:quant-ph/9708021 DOI
[13]
Beenker, G. J. M. "On double circulant codes." (1980).
[14]
I. Siap, T. Abualrub, N. Aydin, and P. Seneviratne, “Skew cyclic codes of arbitrary length”, International Journal of Information and Coding Theory 2, 10 (2011) DOI
[15]
P. Gaborit, V. Pless, P. Solé, and O. Atkin, “Type II Codes over F4”, Finite Fields and Their Applications 8, 171 (2002) DOI
[16]
Karlin M, MacWilliams FJ. Quadratic residue codes over GF (4) and their binary images. InIEEE Int. Symp. on Information Theory, Asilomar, CA 1972.
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

edit on this site

Zoo Code ID: quasi_cyclic

Cite as:
“Quasi-cyclic code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/quasi_cyclic
BibTeX:
@incollection{eczoo_quasi_cyclic, title={Quasi-cyclic code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/quasi_cyclic} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/quasi_cyclic

Cite as:

“Quasi-cyclic code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/quasi_cyclic

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/properties/block/symmetry/cyclic/quasi_cyclic.yml.