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
Primary Hierarchy
Parents
Quasi-twisted codes with \(\alpha=1\) are quasi-cyclic.
Quasi-cyclic code
Children
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 codes with \(\ell=1\) are cyclic.
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
- [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) 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, Univ. 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., vol. 14, pp. 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]
- Karlin M., MacWilliams F. J. Quadratic residue codes over GF(4) and their binary images. InIEEE 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 (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