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.
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].
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
Parent
- Quasi-twisted code — Quasi-twisted codes with \(\alpha=1\) are quasi-cyclic.
Children
- Quasi-cyclic LDPC (QC-LDPC) code
- Cyclic code — Quasi-cyclic codes with \(\ell=1\) are cyclic.
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 [3–9].
- 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 [10].
- Skew-cyclic code — Under certain conditions, there is an equivalent quasi-cyclic or cyclic code for every skew-cyclic code [11].
- Quasi-cyclic quantum code
References
- [1]
- R. Townsend and E. Weldon, “Self-orthogonal quasi-cyclic codes”, IEEE Transactions on Information Theory 13, 183 (1967) DOI
- [2]
- Thomas A. Gulliver, Construction of quasi-cyclic codes, Thesis, University of New Brunswick, 1989.
- [3]
- G. D. Forney, Jr., “Why quasi cyclic codes are interesting,” unpublished note, 1970.
- [4]
- G. Solomon and H. C. A. Tilborg, “A Connection Between Block and Convolutional Codes”, SIAM Journal on Applied Mathematics 37, 358 (1979) DOI
- [5]
- R. Michael Tanner, “Error-correcting coding system,” U.S. Patent 4295218, 1981.
- [6]
- 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.
- [7]
- “Generalized tail-biting convolutional codes,” Ph.D. dissertation, Univ. of Massachusetts, Amherst, 1985.
- [8]
- 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.
- [9]
- M. Esmaeili et al., “A link between quasi-cyclic codes and convolutional codes”, IEEE Transactions on Information Theory 44, 431 (1998) DOI
- [10]
- M. Hagiwara et al., “Spatially Coupled Quasi-Cyclic Quantum LDPC Codes”, (2011) arXiv:1102.3181
- [11]
- I. Siap et al., “Skew cyclic codes of arbitrary length”, International Journal of Information and Coding Theory 2, 10 (2011) 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