Quasi-Cyclic Codes

Eric Zhi Chen

School of Engineering
Kristianstad University
291 88 Kristianstad
Sweden




A Database on Binary Quasi-Cyclic Codes


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