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

A database of quasi-cyclic codes with searchable parameters such as block length and dimension is constructed and displayed here.

Parent

Children

Cousins

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

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

edit on this site

Zoo Code ID: quasi_cyclic

Cite as:
“Quasi-cyclic code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/quasi_cyclic
BibTeX:
@incollection{eczoo_quasi_cyclic, title={Quasi-cyclic code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/quasi_cyclic} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/quasi_cyclic

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/cyclic/quasi_cyclic.yml.