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].
Notes
A database of quasi-cyclic codes with searchable parameters such as block length and dimension is constructed and displayed here.
Parent
Children
- Quasi-cyclic LDPC (QC-LDPC) code
- Cyclic code — Quasi-cyclic codes with \(\ell=1\) are cyclic.
- Skew-cyclic code — Under certain conditions, there is an equivalent quasi-cyclic code for every skew-cyclic code [3].
Cousins
- 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].
- 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]
- I. Siap et al., “Skew cyclic codes of arbitrary length”, International Journal of Information and Coding Theory 2, 10 (2011) DOI
- [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 et al., “A link between quasi-cyclic codes and convolutional codes”, IEEE Transactions on Information Theory 44, 431 (1998) DOI
- [11]
- M. Hagiwara et al., “Spatially Coupled Quasi-Cyclic Quantum LDPC Codes”, (2011) arXiv:1102.3181
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