American Institute of Mathematical Sciences

Advanced
  • Previous Article
    Splitting authentication codes with perfect secrecy: New results, constructions and connections with algebraic manipulation detection codes
  • AMC Home
  • This Issue
  • Next Article
    Another expression of the MacWilliams identities and its applications
doi: 10.3934/amc.2021002
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

The weight distribution of irreducible cyclic codes associated with decomposable generalized Paley graphs

Ricardo A. Podestá , and  Denis E. Videla

FaMAF-CIEM (CONICET), Universidad Nacional de Córdoba, Av. Medina Allende 2144, Ciudad Universitaria, Córdoba (5000), República Argentina

* Corresponding author: Ricardo A. Podestá

Received  February 2020 Revised  February 2021 Early access March 2021

Fund Project: Partially supported by CONICET, FonCyT (BID-PICT 2018-02073) and SECyT-UNC

We use known characterizations of generalized Paley graphs which are Cartesian decomposable to explicitly compute the spectra of the corresponding associated irreducible cyclic codes. As applications, we give reduction formulas for the number of rational points in Artin-Schreier curves defined over extension fields and to the computation of Gaussian periods.

Keywords: Irreducible cyclic codes, generalized Paley graphs, weight distribution, spectra, Cartesian decomposable.
Mathematics Subject Classification: Primary: 94B15, 05C25; Secondary: 05C50, 05C76.
Citation: Ricardo A. Podestá, Denis E. Videla. The weight distribution of irreducible cyclic codes associated with decomposable generalized Paley graphs. Advances in Mathematics of Communications, doi: 10.3934/amc.2021002
References:
[1]

R. Akhtar, T. Jackson-Henderson, R. Karpman, M. Boggess, I. Jiménez, A. Kinzel and D. Pritikin, On the unitary Cayley graph of a finite ring, Electron. J. Combin., 16 (2009), 117-130. 

[2]

L. D. Baumert and R. J. McEliece, Weights of irreducible cyclic codes, Information and Control, 20 (1972), 158-175.  doi: 10.1016/S0019-9958(72)90354-3.

[3]

B. Berndt, R. J. Evans and K. Williams, Gauss and Jacobi Sums, Wiley, New York, 1998.

[4]

D. Cvetkovic, M. Doobs and H. Sachs, Spectra of Graphs, Pure and Applied Mathematics, Academic Press, 1980.

[5]

C. Ding, The weight distribution of some irreducible cyclic codes, IEEE Trans. Inform. Theory, 55 (2009), 955-960.  doi: 10.1109/TIT.2008.2011511.

[6]

C. Ding, A class of three-weight and four-weight codes, Lecture Notes in Computer Science, 5557, Springer Verlag, (2009) 34–42. doi: 10.1007/978-3-642-01877-0_4.

[7]

C. Ding and J. Yang, Hamming weights in irreducible cyclic codes, Discrete Mathematics, 313 (2013), 434-446.  doi: 10.1016/j.disc.2012.11.009.

[8]

H. Q. Dinh, C. Li and Q. Yue, Recent progress on weight distributions of cyclic codes over finite fields, J. Algebra Comb. Discrete Struct. Appl., 2 (2015), 39-63. 

[9]

K. Feng and J. Luo, Weight distribution of some reducible cyclic codes, Finite Fields Appl., 14 (2008), 390-409.  doi: 10.1016/j.ffa.2007.03.003.

[10]

C. D. Godsil and G. F. Royle, Algebraic Graph Theory, Graduate Texts in Mathematics, Springer, 2001. doi: 10.1007/978-1-4613-0163-9.

[11]

A. Garcia and H. Stichtenoth, Topics in Geometry, Coding Theory and Cryptography, Algebra and Applications, Springer, 2007.

[12]

R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs, CRC Press 2nd edition, 2011.

[13]

W. Imrich and S. Klavžar, Product Graphs: Structure and Recognition, Wiley-Interscience, 2000.

[14]

S. Li, S. Hu, T. Feng and G. Ge, The weight distribution of a class of cyclic codes related to Hermitian forms graphs, IEEE Trans. Inform. Theory, 59 (2013), 3064-3067.  doi: 10.1109/TIT.2013.2242957.

[15]

C. Li, Q. Yue and F. Li, Weight distributions of cyclic codes with respect to pairwise coprime order elements, Finite Fields Appl., 28 (2014), 94-114.  doi: 10.1016/j.ffa.2014.01.009.

[16]

T. K. Lim and C. Praeger, On Generalised Paley Graphs and their automorphism groups, Michigan Math. J., 58 (2009), 293-308.  doi: 10.1307/mmj/1242071694.

[17]

R. J. McEliece, Irreducible cyclic codes and Gauss sums, Combinatorics in: Proc. NATO Adv. Study Inst., Breukelen, 1974. Math. Centre Tracts 55, Math. Centrum, Amsterdam, 1974.

[18]

G. Pearce and C. Praeger, Generalised Paley graphs with a product structure, Ann. Comb., 23 (2019), 171-182.  doi: 10.1007/s00026-019-00423-0.

[19]

R. A. Podestá and D. E. Videla, The spectra of generalized Paley graphs of $q^{\ell}+1$ powers and applications, preprint, arXiv: 1812.03332.

[20]

R. A. Podestá and D. E. Videla, Spectral properties of generalized Paley graphs and of their associated irreducible cyclic codes, preprint, arXiv: 1908.08097v2.

[21]

R. A. Podestá and D. E. Videla, The Waring's problem over finite fields through generalized Paley graphs, Discrete Mathematics, 344 (2021), 112324. doi: 10.1016/j.disc.2021.112324.

[22]

A. Rao and N. Pinnawala, A family of two-weight irreducible cyclic codes, IEEE Trans. Inform. Theory, 56 (2010), 2568-2570.  doi: 10.1109/TIT.2010.2046201.

[23]

G. Sabidussi, Graphs with given group and given graph-theoretical properties, Canadian Journal of Mathematics, 9 (1957), 515-525.  doi: 10.4153/CJM-1957-060-7.

[24]

G. Sabidussi, Graph multiplication, Mathematische Zeitschrift, 72 (1960), 446-457.  doi: 10.1007/BF01162967.

[25]

B. Schmidt and C. White, All two weight irreducible cyclic codes, Finite Fields Appl., 8 (2002), 1-17.  doi: 10.1006/ffta.2000.0293.

[26]

A. Sharma and G. K. Bakshi, The weight distribution of some irreducible cyclic codes, Finite Fields Appl., 18 (2012), 144-159.  doi: 10.1016/j.ffa.2011.07.002.

[27]

T. Storer., Cyclotomy and Difference Sets, Markham Publishing Co., Chicago, 1967.

[28]

G. Vega and J. Wolfmann, New classes of 2-weight cyclic codes, Des. Codes Cryptogr., 42 (2007), 327-334.  doi: 10.1007/s10623-007-9038-9.

[29]

Z. Zhou, A. Zhang, C. Ding and M. Xiong, The weight enumerator of three families of cyclic codes, IEEE Trans. Inform. Theory, 59 (2013), 6002-6009.  doi: 10.1109/TIT.2013.2262095.

show all references

References:
[1]

R. Akhtar, T. Jackson-Henderson, R. Karpman, M. Boggess, I. Jiménez, A. Kinzel and D. Pritikin, On the unitary Cayley graph of a finite ring, Electron. J. Combin., 16 (2009), 117-130. 

[2]

L. D. Baumert and R. J. McEliece, Weights of irreducible cyclic codes, Information and Control, 20 (1972), 158-175.  doi: 10.1016/S0019-9958(72)90354-3.

[3]

B. Berndt, R. J. Evans and K. Williams, Gauss and Jacobi Sums, Wiley, New York, 1998.

[4]

D. Cvetkovic, M. Doobs and H. Sachs, Spectra of Graphs, Pure and Applied Mathematics, Academic Press, 1980.

[5]

C. Ding, The weight distribution of some irreducible cyclic codes, IEEE Trans. Inform. Theory, 55 (2009), 955-960.  doi: 10.1109/TIT.2008.2011511.

[6]

C. Ding, A class of three-weight and four-weight codes, Lecture Notes in Computer Science, 5557, Springer Verlag, (2009) 34–42. doi: 10.1007/978-3-642-01877-0_4.

[7]

C. Ding and J. Yang, Hamming weights in irreducible cyclic codes, Discrete Mathematics, 313 (2013), 434-446.  doi: 10.1016/j.disc.2012.11.009.

[8]

H. Q. Dinh, C. Li and Q. Yue, Recent progress on weight distributions of cyclic codes over finite fields, J. Algebra Comb. Discrete Struct. Appl., 2 (2015), 39-63. 

[9]

K. Feng and J. Luo, Weight distribution of some reducible cyclic codes, Finite Fields Appl., 14 (2008), 390-409.  doi: 10.1016/j.ffa.2007.03.003.

[10]

C. D. Godsil and G. F. Royle, Algebraic Graph Theory, Graduate Texts in Mathematics, Springer, 2001. doi: 10.1007/978-1-4613-0163-9.

[11]

A. Garcia and H. Stichtenoth, Topics in Geometry, Coding Theory and Cryptography, Algebra and Applications, Springer, 2007.

[12]

R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs, CRC Press 2nd edition, 2011.

[13]

W. Imrich and S. Klavžar, Product Graphs: Structure and Recognition, Wiley-Interscience, 2000.

[14]

S. Li, S. Hu, T. Feng and G. Ge, The weight distribution of a class of cyclic codes related to Hermitian forms graphs, IEEE Trans. Inform. Theory, 59 (2013), 3064-3067.  doi: 10.1109/TIT.2013.2242957.

[15]

C. Li, Q. Yue and F. Li, Weight distributions of cyclic codes with respect to pairwise coprime order elements, Finite Fields Appl., 28 (2014), 94-114.  doi: 10.1016/j.ffa.2014.01.009.

[16]

T. K. Lim and C. Praeger, On Generalised Paley Graphs and their automorphism groups, Michigan Math. J., 58 (2009), 293-308.  doi: 10.1307/mmj/1242071694.

[17]

R. J. McEliece, Irreducible cyclic codes and Gauss sums, Combinatorics in: Proc. NATO Adv. Study Inst., Breukelen, 1974. Math. Centre Tracts 55, Math. Centrum, Amsterdam, 1974.

[18]

G. Pearce and C. Praeger, Generalised Paley graphs with a product structure, Ann. Comb., 23 (2019), 171-182.  doi: 10.1007/s00026-019-00423-0.

[19]

R. A. Podestá and D. E. Videla, The spectra of generalized Paley graphs of $q^{\ell}+1$ powers and applications, preprint, arXiv: 1812.03332.

[20]

R. A. Podestá and D. E. Videla, Spectral properties of generalized Paley graphs and of their associated irreducible cyclic codes, preprint, arXiv: 1908.08097v2.

[21]

R. A. Podestá and D. E. Videla, The Waring's problem over finite fields through generalized Paley graphs, Discrete Mathematics, 344 (2021), 112324. doi: 10.1016/j.disc.2021.112324.

[22]

A. Rao and N. Pinnawala, A family of two-weight irreducible cyclic codes, IEEE Trans. Inform. Theory, 56 (2010), 2568-2570.  doi: 10.1109/TIT.2010.2046201.

[23]

G. Sabidussi, Graphs with given group and given graph-theoretical properties, Canadian Journal of Mathematics, 9 (1957), 515-525.  doi: 10.4153/CJM-1957-060-7.

[24]

G. Sabidussi, Graph multiplication, Mathematische Zeitschrift, 72 (1960), 446-457.  doi: 10.1007/BF01162967.

[25]

B. Schmidt and C. White, All two weight irreducible cyclic codes, Finite Fields Appl., 8 (2002), 1-17.  doi: 10.1006/ffta.2000.0293.

[26]

A. Sharma and G. K. Bakshi, The weight distribution of some irreducible cyclic codes, Finite Fields Appl., 18 (2012), 144-159.  doi: 10.1016/j.ffa.2011.07.002.

[27]

T. Storer., Cyclotomy and Difference Sets, Markham Publishing Co., Chicago, 1967.

[28]

G. Vega and J. Wolfmann, New classes of 2-weight cyclic codes, Des. Codes Cryptogr., 42 (2007), 327-334.  doi: 10.1007/s10623-007-9038-9.

[29]

Z. Zhou, A. Zhang, C. Ding and M. Xiong, The weight enumerator of three families of cyclic codes, IEEE Trans. Inform. Theory, 59 (2013), 6002-6009.  doi: 10.1109/TIT.2013.2262095.

Table 1.  Weight distribution of $ \mathcal{C} $ with $ p\equiv 2,5,7\pmod 9 $ and $ p>5 $
weight frequency weight frequency
$ w_{0,0} = 0 $ $ A_{0,0}=1 $ $w_{0,2}=p^2-1$ $A_{0,2}=3(\tfrac{p^{2}-1}2)^{2}$
$ w_{1,0}=\tfrac{(p-1)^2}2 $ $ A_{1,0}=3(\tfrac{p^{2}-1}2) $ $w_{0,3}=\tfrac{3(p^{2}-1)}2$ $A_{0,3}=(\tfrac{p^{2}-1}2)^3$
$ w_{2,0}=(p-1)^2 $ $ A_{2,0}=3(\tfrac{p^{2}-1}2)^{2} $ $w_{1,1}=p(p-1)$ $A_{1,1}=6(\tfrac{p^{2}-1}2)^{2}$
$ w_{3,0}=\tfrac{3(p-1)^2}2 $ $ A_{3,0}=(\tfrac{p^{2}-1}2)^3 $ $w_{2,1}=\tfrac{p-1}{2} (3p-1)$ $A_{2,1}=3(\tfrac{p^{2}-1}2)^3$
$ w_{0,1}=\tfrac{p^{2}-1}2 $ $ A_{0,1}=3(\tfrac{p^{2}-1}2) $ $w_{1,2}=\tfrac{p-1}{2} (3p+1)$ $A_{1,2}=3(\tfrac{p^{2}-1}2)^3$
Table Options

Download as excel

weight frequency weight frequency
$ w_{0,0} = 0 $ $ A_{0,0}=1 $ $w_{0,2}=p^2-1$ $A_{0,2}=3(\tfrac{p^{2}-1}2)^{2}$
$ w_{1,0}=\tfrac{(p-1)^2}2 $ $ A_{1,0}=3(\tfrac{p^{2}-1}2) $ $w_{0,3}=\tfrac{3(p^{2}-1)}2$ $A_{0,3}=(\tfrac{p^{2}-1}2)^3$
$ w_{2,0}=(p-1)^2 $ $ A_{2,0}=3(\tfrac{p^{2}-1}2)^{2} $ $w_{1,1}=p(p-1)$ $A_{1,1}=6(\tfrac{p^{2}-1}2)^{2}$
$ w_{3,0}=\tfrac{3(p-1)^2}2 $ $ A_{3,0}=(\tfrac{p^{2}-1}2)^3 $ $w_{2,1}=\tfrac{p-1}{2} (3p-1)$ $A_{2,1}=3(\tfrac{p^{2}-1}2)^3$
$ w_{0,1}=\tfrac{p^{2}-1}2 $ $ A_{0,1}=3(\tfrac{p^{2}-1}2) $ $w_{1,2}=\tfrac{p-1}{2} (3p+1)$ $A_{1,2}=3(\tfrac{p^{2}-1}2)^3$
Table 2.  Weight distribution of $ \mathcal{C}(516,7^6) $
weight frequency weight frequency
$ w_{0,0,0}=0 $ $ A_{0,0,0}=1 $ $w_{0,2,0}=216$ $A_{0,2,0}=114^2$
$ w_{1,0,0}=96 $ $ A_{1,0,0}=228 $ $w_{0,0,2}=180$ $ A_{0,0,2}=114^2$
$ w_{0,1,0}=108 $ $ A_{0,1,0}=228 $ $ w_{1,1,0}=204$ $A_{1,1,0}=2\cdot 114^2$
$ w_{0,0,1}=90 $ $ A_{0,0,1}=228 $ $w_{1,0,1}=186$ $ A_{1,0,1}=2\cdot 114^2$
$ w_{2,0,0}=192 $ $ A_{2,0,0}=114^2 $ $w_{0,1,1}=198$ $A_{0,1,1}=2\cdot 114^2$
Table Options

Download as excel

weight frequency weight frequency
$ w_{0,0,0}=0 $ $ A_{0,0,0}=1 $ $w_{0,2,0}=216$ $A_{0,2,0}=114^2$
$ w_{1,0,0}=96 $ $ A_{1,0,0}=228 $ $w_{0,0,2}=180$ $ A_{0,0,2}=114^2$
$ w_{0,1,0}=108 $ $ A_{0,1,0}=228 $ $ w_{1,1,0}=204$ $A_{1,1,0}=2\cdot 114^2$
$ w_{0,0,1}=90 $ $ A_{0,0,1}=228 $ $w_{1,0,1}=186$ $ A_{1,0,1}=2\cdot 114^2$
$ w_{2,0,0}=192 $ $ A_{2,0,0}=114^2 $ $w_{0,1,1}=198$ $A_{0,1,1}=2\cdot 114^2$
[1]

Gerardo Vega, Jesús E. Cuén-Ramos. The weight distribution of families of reducible cyclic codes through the weight distribution of some irreducible cyclic codes. Advances in Mathematics of Communications, 2020, 14 (3) : 525-533. doi: 10.3934/amc.2020059
[2]

Lanqiang Li, Shixin Zhu, Li Liu. The weight distribution of a class of p-ary cyclic codes and their applications. Advances in Mathematics of Communications, 2019, 13 (1) : 137-156. doi: 10.3934/amc.2019008
[3]

Pankaj Kumar, Monika Sangwan, Suresh Kumar Arora. The weight distributions of some irreducible cyclic codes of length $p^n$ and $2p^n$. Advances in Mathematics of Communications, 2015, 9 (3) : 277-289. doi: 10.3934/amc.2015.9.277
[4]

Dina Ghinelli, Jennifer D. Key. Codes from incidence matrices and line graphs of Paley graphs. Advances in Mathematics of Communications, 2011, 5 (1) : 93-108. doi: 10.3934/amc.2011.5.93
[5]

Alexander Barg, Arya Mazumdar, Gilles Zémor. Weight distribution and decoding of codes on hypergraphs. Advances in Mathematics of Communications, 2008, 2 (4) : 433-450. doi: 10.3934/amc.2008.2.433
[6]

Alexander A. Davydov, Stefano Marcugini, Fernanda Pambianco. On the weight distribution of the cosets of MDS codes. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021042
[7]

Long Yu, Hongwei Liu. A class of $p$-ary cyclic codes and their weight enumerators. Advances in Mathematics of Communications, 2016, 10 (2) : 437-457. doi: 10.3934/amc.2016017
[8]

Nigel Boston, Jing Hao. The weight distribution of quasi-quadratic residue codes. Advances in Mathematics of Communications, 2018, 12 (2) : 363-385. doi: 10.3934/amc.2018023
[9]

Eimear Byrne. On the weight distribution of codes over finite rings. Advances in Mathematics of Communications, 2011, 5 (2) : 395-406. doi: 10.3934/amc.2011.5.395
[10]

Sergio R. López-Permouth, Steve Szabo. On the Hamming weight of repeated root cyclic and negacyclic codes over Galois rings. Advances in Mathematics of Communications, 2009, 3 (4) : 409-420. doi: 10.3934/amc.2009.3.409
[11]

Chengju Li, Qin Yue, Ziling Heng. Weight distributions of a class of cyclic codes from $\Bbb F_l$-conjugates. Advances in Mathematics of Communications, 2015, 9 (3) : 341-352. doi: 10.3934/amc.2015.9.341
[12]

Claude Carlet. Expressing the minimum distance, weight distribution and covering radius of codes by means of the algebraic and numerical normal forms of their indicators. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022047
[13]

M. DeDeo, M. Martínez, A. Medrano, M. Minei, H. Stark, A. Terras. Spectra of Heisenberg graphs over finite rings. Conference Publications, 2003, 2003 (Special) : 213-222. doi: 10.3934/proc.2003.2003.213
[14]

Anuradha Sharma, Saroj Rani. Trace description and Hamming weights of irreducible constacyclic codes. Advances in Mathematics of Communications, 2018, 12 (1) : 123-141. doi: 10.3934/amc.2018008
[15]

Tongjiang Yan, Yanyan Liu, Yuhua Sun. Cyclic codes from two-prime generalized cyclotomic sequences of order 6. Advances in Mathematics of Communications, 2016, 10 (4) : 707-723. doi: 10.3934/amc.2016036
[16]

Fengwei Li, Qin Yue, Fengmei Liu. The weight distributions of constacyclic codes. Advances in Mathematics of Communications, 2017, 11 (3) : 471-480. doi: 10.3934/amc.2017039
[17]

Tim Alderson, Alessandro Neri. Maximum weight spectrum codes. Advances in Mathematics of Communications, 2019, 13 (1) : 101-119. doi: 10.3934/amc.2019006
[18]

Srimathy Srinivasan, Andrew Thangaraj. Codes on planar Tanner graphs. Advances in Mathematics of Communications, 2012, 6 (2) : 131-163. doi: 10.3934/amc.2012.6.131
[19]

Shuangliang Tian, Ping Chen, Yabin Shao, Qian Wang. Adjacent vertex distinguishing edge-colorings and total-colorings of the Cartesian product of graphs. Numerical Algebra, Control and Optimization, 2014, 4 (1) : 49-58. doi: 10.3934/naco.2014.4.49
[20]

Jong Yoon Hyun, Yoonjin Lee, Yansheng Wu. Connection of $ p $-ary $ t $-weight linear codes to Ramanujan Cayley graphs with $ t+1 $ eigenvalues. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020133

2021 Impact Factor: 1.015

Tools

Metrics

  • PDF downloads (416)
  • HTML views (447)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy