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 cyclic shift by \(\ell\) positions, \(c_{n-\ell+1} \cdots c_n c_1 \cdots c_{n-\ell}\), is also a codeword. Codes 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 cyclic-shift automorphisms. Cyclic codes are invariant under a shift by one position, while quasi-cyclic codes are invariant under a shift by \(\ell\) positions.

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 [4; pg. 4].
Self-dual linear code— Quasi-cyclic self-dual constructions include double circulant codes and, in odd characteristic, their negacirculant analogs such as double negacirculant and four-negacirculant codes [5; Sec. 4.4].
Convolutional code— Quasi-cyclic codes can be unwrapped to obtain convolutional codes [6–12].
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 [13].
Quantum divisible code— Certain double circulant codes can be used to construct doubly even \([[55,1,11]]\) and \([[87,1,15]]\) codes [14].
Binary quadratic-residue (QR) code— Binary QR codes are equivalent to double circulant codes for all \(n<200\) except 89 and 167 [15].
Skew-cyclic code— Under certain conditions, there is an equivalent quasi-cyclic or cyclic code for every skew-cyclic code [16].
Quasi-cyclic quantum code— Quasi-cyclic quantum codes are quantum analogues of quasi-cyclic codes.

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

\([2m+2,m+1]\) Karlin code

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

Quasi-cyclic LDPC (QC-LDPC) code

Cyclic codeQR

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

\([2q+2,q+1]_3\) Pless symmetry code

Pless symmetry codes are double circulant [2; pg. 510].

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]
T. A. Gulliver, “Construction of quasi-cyclic codes”, PhD thesis, University of New Brunswick, 1989 URL
[4]
M. Borello and W. Willems, “On the algebraic structure of quasi group codes”, (2021) arXiv:1912.09167
[5]
S. Bouyuklieva, “Self-dual codes”, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021), pp. 79-96 DOI
[6]
G. D. Forney, Jr., “Why quasi cyclic codes are interesting”, unpublished note, 1970
[7]
G. Solomon and H. C. A. Tilborg, “A Connection Between Block and Convolutional Codes”, SIAM Journal on Applied Mathematics 37, 358 (1979) DOI
[8]
R. M. Tanner, “Error-Correcting Coding System”, U.S. Patent 4295218 (1981)
[9]
R. M. 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
[10]
H. H. Ma, “Generalized tail-biting convolutional codes”, PhD thesis, University of Massachusetts, Amherst, 1985
[11]
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. 14, 189–198 (1993)
[12]
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
[13]
M. Hagiwara, K. Kasai, H. Imai, and K. Sakaniwa, “Spatially Coupled Quasi-Cyclic Quantum LDPC Codes”, (2011) arXiv:1102.3181
[14]
A. M. Steane, “Space, Time, Parallelism and Noise Requirements for Reliable Quantum Computing”, Fortschritte der Physik 46, 443 (1998) arXiv:quant-ph/9708021 DOI
[15]
G. J. M. Beenker, “On double circulant codes”, (1980)
[16]
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
[17]
P. Gaborit, V. Pless, P. Solé, and O. Atkin, “Type II Codes over F4”, Finite Fields and Their Applications 8, 171 (2002) DOI
[18]
M. Karlin and F. J. MacWilliams, “Quadratic residue codes over GF(4) and their binary images”, in IEEE Int. Symp. on Information Theory, Asilomar, CA, 1972
[19]
Self-Dual Codes and Invariant Theory (Springer-Verlag, 2006) DOI

Page edit log

Victor V. Albert (2026-06-08) — most recent
Victor V. Albert (2022-06-14)
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.), 2026. https://errorcorrectionzoo.org/c/quasi_cyclic, arXiv:2606.11484

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