Quasi-cyclic code

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

Quasi group-algebra code— A quasi group-algebra code for \(G\) being the cyclic group is a quasi-cyclic \(q\)-ary linear code.
Convolutional code— Quasi-cyclic codes can be unwrapped to obtain convolutional codes [4–10].
Quantum spatially coupled (SC-QLDPC) code— Quasi-cyclic binary code parity-check matrices can be used as sub-matrices to define a 1D SC-QLDPC code [11].
Quantum divisible code— Certain double circulant codes can be used to construct doubly even \([[55,1,11]]\) and \([[87,1,15]]\) codes [12].
Binary quadratic-residue (QR) code— Binary QR codes are equivalent to double circulant codes for all \(n<200\) except 89 and 167 [13].
Skew-cyclic code— Under certain conditions, there is an equivalent quasi-cyclic or cyclic code for every skew-cyclic code [14].
Quasi-cyclic quantum code

Member of code lists

Classical codes

Primary Hierarchy

Classical Domain

Error-correcting code (ECC)

Block code

Quasi-twisted code

Parents

Quasi-twisted code

Quasi-twisted codes with \(\alpha=1\) are quasi-cyclic.

Quasi-cyclic code

Children

Karlin double circulant code

Karlin double circulant codes can be mapped to extended cyclic and extended quadratic-residue codes over \(GF(4)\) [15,16][2; Ch. 16][17; Sec. 2.4.2] by identifying \((0,\omega,\bar{\omega},1)\) with \((00),(10),(01),(11)\) [15].

Quasi-cyclic LDPC (QC-LDPC) code

Cyclic codeQR

Quasi-cyclic codes with \(\ell=1\) are cyclic.

Pless symmetry code

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.
[17]: Self-Dual Codes and Invariant Theory (Springer-Verlag, 2006) DOI

Page edit log

Victor V. Albert (2022-06-14) — most recent
Micah Shaw (2022-06-13)
Nolan Coble (2021-11-27)

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.