Linear codes and cyclic codes over finite rings and their generalizations: a survey

Djoko Suprijanto

Abstract


We survey a recent progress of cyclic codes over finite rings and their generalization to skew cyclic as well as skew cyclic codes with derivation over finite rings, focusing on structural properties of the codes. We also report recent developments on the construction methods of linear codes from graphs, in particular strongly regular as well as distance regular graphs.

Keywords


Finite rings; linear codes; cyclic codes; skew polynomial ring; skew cyclic codes; skew cyclic codes with derivation; strongly regular graphs; distance regular graphs

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2023.11.2.11

References

T. Abualrub and I. Siap, Cyclic codes over the rings Z2 + uZ2 and Z2 + uZ2 + u2Z2, Des. Codes Cryptogr. 42(3) (2007), 273-287.

A. Alahmadi, A. Alkenani, J.L. Kim, and M. Shi, and Patrick Solé, Directed strongly regular graphs and their codes, Bull. Korean Math. Soc. 54(2) (2017), 497-505.

E.F. Assmus and J.E. Key, Designs and their Codes, Cambridge, 1994.

E.F. Assmus Jr. and H.F. Mattson, Error-correcting codes: An axiomatic approach, Inf. Control 6 (1963), 315-330.

R.K. Bandi and M. Bhaintwal, A note on cyclic codes over Z4 + uZ4, Discrete Math. Algorithms Appl. 8(1) (2016), 1650017 (17 pages).

E. Bannai, Et. Bannai, T. Ito, and R. Tanaka, Algebraic combinatorics, Walter de Gruyter, Berlin/ Boston, 2021.

E. Bannai and T. Ito, Algebraic combinatorics I: Association schemes, Benjamin/ Cummings, Menlo Park, California, 1984.

I.F. Blake, Codes over certain rings, Inf. Control 20 1972, 396-404.

I.F. Blake, Codes over integer residu rings, Inf. Control 29 1975, 295-300.

L.S. Borrow and B.M. Franaszczuk, On cyclic codes generated by graphs, Inf. Control 22 (1973), 296-301.

D. Boucher, W. Geiselmann, and F. Ulmer, Skew cyclic codes, Appl. Algebra Engrg. Comm. Comput. 18(4) (2007), 379-389.

D. Boucher, Solé, and Ulmer, Skew constacyclic codes over Galois rings, Adv. Math. Commun. 2(3) (2008), 273-292.

D. Boucher and F. Ulmer, Coding with skew polynomial rings, J. Symb. Comput. 44(3-4) (2009), 1644-1656.

D. Boucher and F. Ulmer, Coding as modules over skew polynomial rings, in Proceedings of the 12th IMA Conference on Cryptography and Coding, Lecture Notes in Comput. Sci. 5921 (2009), 38-55.

D. Boucher and F. Ulmer, Linear codes using skew polynomials with automorphisms and derivations, Des. Codes Cryptogr. 70(3) (2014), 405-431.

A.E. Brouwer and H. van Maldeghem, Strongly regular graphs, Encyclopedia Math. Appl. 182, Cambridge University Press, 2022.

A.R. Calderbank and N.J.A. Sloane, Modular and p-adic cyclic codes, Des. Codes Cryptogr. 6 (1995), 21-35.

A.R. Calderbank and N.J.A. Sloane, Double circulant codes over Z4 and even unimodular lattices, J. Algebraic Combin. 6(2) (1997), 119-131.

I. Cardinali, L. Giuzzi, and M. Kwiatkowski, On the Grassmann graph of linear codes, Finite Fields Appl. 75 (2021), 101895.

Y. Cengellenmis, A. Dertli, and S.T. Dougherty, Codes over an infinite family of rings with a Gray map, Des. Codes Cryptogr., 72(3) (2014), 559-580.

D. Crnković, S Rukavina, and A. $check{{ }{S}}$vob, Self-orthogonal codes from equitable partitions of association schemes, J. Algebraic Combin. 55(1) (2022), 157-171.

P. Dankelmann, J.D. Key, and B. G. Rodrigues, Codes from incidence matrices of graphs, Des. Codes Cryptogr. 68() (2013), 373-393.

C. Ding and C. Tang, Designs from linear codes (2nd Ed.), World Scientific, 2021.

H.Q. Dinh and S.R. López-Permouth, Cyclic and negacyclic codes over finite chain rings, IEEE Inform. Theory 50(8) (2004), 1728-1744.

S.T. Dougherty, P. Gaborit, M. Harada, A. Munemasa, and P. Solé. Type IV self-dual codes over rings, IEEE Trans. Inform. Theory 45(7) (1999), 2345-2360.

S.T. Dougherty, J.L. Kim, and P. Solé, Doubly circulant codes from two class association schemes, Adv. Math. Commun. 1(1) 2007, 45-64.

N. Fellah, K. Guenda, F. Özbudak, and P. Seneviratne, Construction of self dual codes from graphs, Appl. Algebra Engrg. Comm. Comput. (to appear) (https://doi.org/10.1007/s00200-022-00567-2).

W. Fish, J.D. Key, and E. Mwambene, Codes from incidence matrices and line graphs of Hamming graphs, Discr. Math. 310(13-14) (2010), 1884-1897.

W. Fish, J.D. Key, and E. Mwambene, Codes from the incidence matrices of graphs on 3-sets, Discr. Math. 311(16) (2011), 1823-1840.

P. Gaborit, Quadratic double circulant codes over fields, J. Combin. Theory Ser. A 97(1) (2002), 85-107.

W.H. Haemers, R. Peeters, and J.M. van Rijckevorsel, Binary codes of strongly regular graphs, Des, Codes Cryptogr. 17(1-3) (1999), 187-209.

S.L. Hakimi and H. Frank, Cut-set matrices and linear codes, IEEE Trans. Inform. Theory IT-11 (1965), 457-458.

A.R. Hammons, P.V. Kumar, A.R. Calderbank, N.J.A. Sloane, and P. Solé, The Z4-linearity of Kerdock, Preparata, Goethals and Related Codes, IEEE Trans. Inform. Theory 40 1994, 301-319.

W.C. Huffman and V. Pless, Fundamentals of Error Correcting Codes, Cambridge University Press, 2003.

Irwansyah, A. Barra, S.T. Dougherty, A. Muchlis, I. Muchtadi-Alamsyah, P. Sole, D. Suprijanto, and O. Yemen, ΘS-cyclic codes over Ak, Int. J. Comput. Math. Comput. Syst. Theory 1(1) (2016), 14-31.

Irwansyah, A. Barra, A. Muchlis, I. Muchtadi-Alamsyah, and D. Suprijanto, Skew cyclic codes over Bk, J. Appl. Math. Comput. 57(1-2) (2018), 69-84.

Irwansyah and D. Suprijanto, Structure of linear codes over the ring Bk, J. Appl. Math. Comput. 58(1-2) (2018), 755-775.

Irwansyah and D. Suprijanto, Linear codes over a general infinite family of rings and MacWilliams-type relations, Discrete Math. Lett. 11 (2023), 53-60.

S. Jitman, S. Ling, and P. Udomkavanich, Skew constacyclic codes over finite chain rings, Ad. Math. Commun. 6(1) (2021), 39-63.

P. Kanwar and S. R. López-Permouth, Cyclic codes over the integers modulo pm, Finite Fields Appl. 3(4) (1997), 119-131.

T. Kasami, Topological approach to construction of group codes, J. Inst. Elec. Commun. Eng. Jap. 44 (1961), 1316-1321.

J.L. Kim and P. Solé, Skew Hadamard designs and their codes, Des. Codes Cryptogr. 49(1-3) (2008), 135-145.

O. Ore, Theory of non-commutative polynomials, Annals. Math. 34 (1933), 480-508.

F. Ma, J. Gao, J. Li, and F.W. Li, (σ, δ)-Skew quasi-cyclic codes over the ring Z4 + uZ4, Cryptogr. Commun. 13(2) (2021), 307-320.

F.J. MacWilliams, N.J.A. Sloane, The Theory of Error-Correcting Codes, North-Holland, Amsterdam, 1977.

G. Norton and A. Sălăgean-Mandache, On the structure of linear cyclic codes over finite chain rings, Appl. Algebra Eng. Commun. Comput. 10(6) (2000), 489–506.

S. Patel and O. Prakash, (θ, δθ)-Cyclic codes over Fq[u, v]/⟨u2 − u, v2 − vuv − vu⟩, Des. Codes Cryptogr. 90(11) (2022), 2763-2781.

V. Pless, On a new family of symmetry codes and related new 5-designs, Bull. AMS, 75 (1969), 1339-1342.

E. Prange, Cyclic error-correcting codes in two symbols, AFCRC-TN-57-I03, Air Force Cambridge Research Center, Cambridge, Mass., Sept. 1957.

E. Prange, Some cyclic error-correcting codes with simple decoding algorithms, AFCRC-TN-58-156, Air Force Cambridge Research Center, Bedford, Mass., April 1958.

K.B. Reid and E. Brown, Doubly regular tournaments are equivalent to skew Hadamard matrices,J. Combin. Theory Ser. A 12(3) (1972), 332-338.

P. Shankar, On BCH codes over arbitrary integer rings, IEEE Trans. Inform. Theory 25(4) (1979), 480-483.

C.E. Shannon, A mathematical theory of communication, Bell System Tech. J. 27(3) (1948), 379-423, and 27(4) (1948), 623-656.

A. Sharma and M. Bhaintwal, A class of skew cyclic codes over Z4 + uZ4 with derivation, Adv. Math. Commun. 12(4) (2018), 723-739.

M. Shi and P. Solé, Three-weight codes, triple sum sets, and strongly walk regular graphs, Des. Codes Cryptogr. 87(10) (2019), 2395-2404.

M. Shi, T. Helleseth, and P. Solé, Strongly regular graphs from reducible cyclic codes, J. Algebraic Combin. 55(1) (2022), 173-184.

E. Spiegel, Code over Zm, Inf. Control 35 (1977), 48-51.

E. Spiegel, Codes over Zm, revisited, Inf. Control 37 (1978), 100-104.

D. Suprijanto and T. Nugraha, A note on linear codes from Johnson graphs, JP Journal of Algebra Number Theory App. 38(5) (2016), 473-488.

D. Suprijanto and H.C. Tang, Skew cyclic codes over Z4 + vZ4 with derivation, submitted (2023).

D. Suprijanto and H.C. Tang, Quantum codes constructed from cyclic codes over a finite non-chain ring, IAENG Int. J. Comput. Sci. 49(3) (2022), 695-700.

D. Suprijanto and Irwansyah, Constacyclic codes over the ring Bk and quantum codes, (tentative title, a work in preparation).

H. Tapia-Recilias and G. Vega, Some constacyclic codes over Z2k and binary quasi-cyclic codes, Discrete Appl. Math. 128(1 SPEC) (2003), 305-316.

H.C. Tang and D. Suprijanto, New optimal linear codes over Z4, Bull. Aust. Math. Soc. 107(1) (2023), 158-169.

H.C. Tang and D. Suprijanto, A general family of Plotkin-optimal two-weight codes over Z4, Des, Codes Cryptogr. 91(5) (2023), 1737-1750.

V.D. Tonchev, Binary codes derived from the Hoffman–Singleton and Higman–Sims graphs, IEEE Trans. Inform. Theory 43(3) (1997), 1021-1025.

V.D. Tonchev, Codes and Designs, in: V.S. Pless, W.C. Huffman (Eds.), Handbook of Coding Theory, Chapter 15, Elsevier, Amsterdam, 1998, pp. 1229-1267.

V.D. Tonchev, Error-correcting codes from graphs, Discr. Math. 257(2-3) (2002), 549-557.

J. Wolfmann, Negacyclic and cyclic codes over Z4, IEEE Trans. Inform. Theory 45(7) (1999), 2527-2532.

J. Wood, Duality for modules over finite rings and applications to coding theory, Amer. J. Math. 121 (1999), 555-575.


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats