Quasi-Cyclic Codes
Eric Zhi Chen
School of Engineering
Kristianstad University
291 88 Kristianstad
Sweden
Introduction to Quasi-Cyclic Codes
Quasi-cyclic(QC) codes are a generalization of cyclic codes whereby a cyclic
shift of a codeword by p positions results in another codeword.Therefore,
cyclic codes are QC codes with p = 1.
The QC codes can be described by circulants. A circulant matrix is defined
to be a square matrix C of the form
c
c1 c2
... cm-1
cm-1
c0 c1
... cm-2
C= cm-2 c
m-1 c0 ... cm-3
....
c1
c2
c3 ... c0
where each successive row a cyclic shift of the previous one. The algebra
of circulant mxm matrices over GF(2) is isomorphic to the algebra of polynomials
in the ring f[x]/xm + 1 if C is mapped onto the polynomial c(x)
= c0 + c1x1 + c2
x 2 +cm-1xm-1 .
Let c0 (x), c1 (x), ..., and cp-1
(x) are p polynomials corresponding to p mxm matrices. Then one subclass
of binary QC codes, which is called 1-generator QC codes, can be defined
as
c0 (x)
c1 (x) ...
cp-1 (x)
x c
0 (x) x c
1 (x) ...
x cp-1 (x)
G= x2 c0 (x)
x2 c1 (x) ...
x2 cp-1 (x)
......
xk-1 c0
(x) xk-1 c1 (x)
... xk-1 cp-1 (x)
with all multiplications modulo xm + 1, where k is the
dimension of the binary QC [pm, k] code and is equal to the degree of h(x):
h(x) = ( xm + 1 )/ ( xm + 1,
c0 (x), c1 (x), ..., c
p-1 (x) ).
For more information on quasi-cyclic codes see the references listed below.
References
[1] R.L. Townsend and E.: Weldon, "Self-orthogonal quasi-cyclic codes",
IEEE Trans. Inform. Theory, vol. IT-13, no.2, pp.183-195, April 1967
[2] E.J. Weldon, Jr., "Long quasi-cyclic codes are good", IEEE Trans.
Inform. Theory, vol.IT-16, no.1, p.130, Jan. 1970
[3] T. Kasami, "A Gilbert-Varhamov bound for quasi-cyclic codes of
rate ½" IEEE Trans. Inform. Theory, vol.IT-20, no.5, p674, Sept. 1974
[4] M. Karlin, "New binary coding results by circulants", IEEE Trans.
Inform. Theory, vol.IT-15, no.1, pp.81-92, Jan. 1969
[5] M. Karlin, "Decoding of circulant codes", IEEE Trans. Inform.
Theory, vol.IT-16, no.6, pp.797-802, Nov. 1970
[6] C.L. Chen, W.W. Peterson, and E.J. Weldon, Jr., "Some results
on quasi-cyclic codes", Inform. Contr., vol.15, pp.407-423, 1969
[7] V.K. Bhargava, G.E. Seguin, and J.M. Stein, "Some (mk, k) cyclic
codes in quasi-cyclic form", IEEE Trans. Inform. Theory, vol.IT-24, pp.358-369,
Sept. 1978
[8] C.W. Hoffner and S.M. Reddy, "Circulant bases for cyclic codes",
IEEE Trans. Inform. Theory, vol. IT-16, no.4, pp.511-512,
July 1970
[9] F.J. MacWillianms, "Decomposition of cyclic codes of block lengths
3p, 5p,7p", IEEE Trans. Inform. Theory, vol.IT-25, no.1, pp.112-118, 1979
[10]P. Piret, "Good linear codes of length 27 and 28", IEEE Trans. Inform.
Theory, vol.IT-26, no.3, p.277, Mar. 1980
[11]J.M. Stein and V.K. Bhargava, "Equivalent rate ½ quasi-cyclic
codes", IEEE Trans. Inform. Theory, vol.IT-21, no.5, pp.588-589, Setp. 1975
[12]J.M. Stein, V.K. Bhargava, and S.E. Tavares, "Weight distribution of
some best (3m, 2m) binary quasi-cyclic codes", IEEE Trans. Inform. Theory,
vol.IT-21, no.6, pp.708-711, Nov. 1975
[13]S.E. Tavares, V.K. Bhargava, and S.G.S. Shiva,"Some rate p/(p+1) quasi-cyclic
codes", IEEE Trans. Inform.Theory, vol.IT-20, no.1, pp.133-135, Jan. 1974
[14]H.C.A. van Tilborg, "on quasi-cyclic codes with rate 1/m", IEEE Trans.
Inform. Theory, vol.IT-24, no.5, pp.628-629, Sept. 1978
[15]T.A. Gulliver and V.K. Bhargava, "Some best rate 1/p and rate (p-1)/p
systematic quasi-cyclic codes", IEEE Trans. Inform.Theory, vol.IT-37, no.3,
pp.552-555, May 1991
[16]T.A. Gulliver and V.K. Bhargava, "Nine good (m-1)/pm quasi-cyclic codes",
IEEE Trans. Inform.Theory, vol.IT-38, no.4, pp.1366-1369, July 1992
[17]T.A. Gulliver and V.K. Bhargava, "Some best rate 1/p and rate (p-1)/p
systematic quasi-cyclic codes over GF(3) and GF(4)", IEEE Trans. Inform.Theory,
vol.IT-38, no.4, pp.1369-1374, July 1992
[18]T.A. Gulliver and V.K. Bhargava, "Twelve good rate (m-r)/pm binary quasi-cyclic
codes", IEEE IT-39,no.5,pp.1750-1751, 1993
[19]Zhi Chen, "Six new binary quasi-cyclic codes", IEEE Trans. Inform. Theory,
vol.IT-40, no.5, pp.1666-1667, Sept. 1994
[20]Zhi Chen, "On Computer Search for Good Quasi-Cyclic Codes", IEEE Symp.
on Information Theory, Norway, 1994
[21]Zhi Chen, " New Results on Binary Quasi-Cyclic Codes", Proceeding IEEE
Intern. Symp. on Information Theory, ISIT2000, Sorrento, Italy, 2000
[22]Petra Heijnen, Henk van Tilborg, Tom Verhoeff, and Sander Weijs,
"Some new binary quasi-cyclic codes", IEEE Trans. Inform. Theory, vol. 44,
1994-1996, Sept. 1998
[23]G. Solomon and H.C.A. van Tilborg, "A connection between block codes
and convolutional codes", SIAM J. Appl. Math., vol.37, pp.358-369, Oct. 1979
[24]R.M. Tanner, "Convolutional codes form quasi-cyclic codes: A link between
the theories of block and convolutional codes", in IEEE Int. Symp.
Inform. Theory, Kobe, Japan, June 1988
[25]Zhi Chen, P.Z. Fan, and F. Jin, "Disjoint difference sets, difference
triangle sets and related codes", IEEE Trans. Inform. Theory, vol.IT-38,
pp.518-522, March 1992
[26]Zhi Chen, "New constructions of majority logic decodable quasi-cyclic
codes", Electronics Letters, vol. 28, pp.1198-1200, 1992
[27] I.E. Bocharova, R. Johannesson, B. D. Kudryashov, and P. Ståhl,
"Tailbiting codes: bounds and search results", IEEE Trans. on Inform Theory,
vol. 48, NO.1, pp. 137--148, Jan 2002
[28] S. Ling and P. Sole, "On the algebraic structure of quasi-cyclic codes
I: finite fields", IEEE Trans. Inform. Theory, vol. IT-47, 2751--2759, Nov.
2001
[29] K. Lally and P. Fitzpatrick, "Algebraic structure of quasi-cyclic codes",
Discr. Appl. Math., vol. 111, 157--175, 2001
[30]
URL: http://moodle.tec.hkr.se/~chen/research/codes/qc.htm
Last modified 2002.03.06