February  2011, 5(1): 93-108. doi: 10.3934/amc.2011.5.93

Codes from incidence matrices and line graphs of Paley graphs

1. 

Dipartimento di Matematica, Università di Roma 'La Sapienza', I-00185 Rome, Italy

2. 

School of Mathematical Sciences, University of KwaZulu-Natal, Pietermaritzburg 3209, South Africa

Received  September 2010 Published  February 2011

We examine the $p$-ary codes from incidence matrices of Paley graphs $P(q)$ where $q\equiv 1$(mod $4$) is a prime power, and show that the codes are $[\frac{q(q-1)}{4},q-1,\frac{q-1}{2}]$2 or $[\frac{q(q-1)}{4},q,\frac{q-1}{2}]$p for $p$ odd. By finding PD-sets we show that for $q > 9$ the $p$-ary codes, for any $p$, can be used for permutation decoding for full error-correction. The binary code from the line graph of $P(q)$ is shown to be the same as the binary code from an incidence matrix for $P(q)$.
Citation: 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
References:
[1]

E. F. Assmus, Jr. and J. D. Key, "Designs and their Codes,'' Cambridge University Press, Cambridge, 1992; second printing with corrections, 1993.

[2]

R. Balakrishnan and K. Ranganathan, "A Textbook of Graph Theory,'' New York, Springer-Verlag, 2000.

[3]

W. Bosma, J. Cannon and C. Playoust, The Magma algebra system I: The user language, J. Symb. Comp., 24 (1997), 235-265. doi: 10.1006/jsco.1996.0125.

[4]

J. Cannon, A. Steel and G. White, Linear codes over finite fields, in "Handbook of Magma Functions'' (eds. J. Cannon and W. Bosma), Computational Algebra Group, Department of Mathematics, University of Sydney, (2006), 3951-4023; available online at http://magma.maths.usyd.edu.au/magma

[5]

K. Chouinard, "Weight Distributions of Codes from Planes,'' Ph.D thesis, University of Virginia, 2000.

[6]

W. Fish, J. D. Key and E. Mwambene, Binary codes of line graphs from the $n$-cube, J. Symbolic Comput., 45 (2010), 800-812. doi: 10.1016/j.jsc.2010.03.012.

[7]

W. Fish, J. D. Key and E. Mwambene, Codes from the incidence matrices and line graphs of Hamming graphs, Discrete Math., 310 (2010), 1884-1897. doi: 10.1016/j.disc.2010.02.010.

[8]

W. Fish, J. D. Key and E. Mwambene, Codes from the incidence matrices and line graphs of Hamming graphs $H^k(n,2)$ for $k \ge 2$, Adv. Math. Commun., to appear.

[9]

D. M. Gordon, Minimal permutation sets for decoding the binary Golay codes, IEEE Trans. Inform. Theory, 28 (1982), 541-543. doi: 10.1109/TIT.1982.1056504.

[10]

W. C. Huffman, Codes and groups, in "Handbook of Coding Theory'' (eds. V.S. Pless and W.C. Huffman), Amsterdam, Elsevier, (1998), 1345-1440.

[11]

B. Jackson, Hamilton cycles in regular 2-connected graphs, J. Combin. Theory Ser. B, 29 (1980), 27-46. doi: 10.1016/0095-8956(80)90042-8.

[12]

J. D. Key, T. P. McDonough and V. C. Mavron, Partial permutation decoding for codes from finite planes, European J. Combin., 26 (2005), 665-682. doi: 10.1016/j.ejc.2004.04.007.

[13]

J. D. Key, T. P. McDonough and V. C. Mavron, Information sets and partial permutation decoding for codes from finite geometries, Finite Fields Appl., 12 (2006), 232-247. doi: 10.1016/j.ffa.2005.05.007.

[14]

J. D. Key, J. Moori and B. G. Rodrigues, Codes associated with triangular graphs, and permutation decoding, Int. J. Inform. Coding Theory, 1 (2010), 334-349. doi: 10.1504/IJICOT.2010.032547.

[15]

J. D. Key, J. Moori and B. G. Rodrigues, Codes from incidence matrices and line graphs of symplectic graphs, in preparation.

[16]

J. D. Key and B. G. Rodrigues, Codes associated with lattice graphs, and permutation decoding, Discrete Appl. Math., 158 (2010), 1807-1815. doi: 10.1016/j.dam.2010.07.003.

[17]

H.-J. Kroll and R. Vincenti, PD-sets related to the codes of some classical varieties, Discrete Math., 301 (2005), 89-105. doi: 10.1016/j.disc.2004.11.020.

[18]

M. Lavrauw, L. Storme, P. Sziklai and G. Van de Voorde, An empty interval in the spectrum of small weight codewords in the code from points and k-spaces of $PG(n,q)$, J. Combin. Theory Ser. A, 116 (2009), 996-1001. doi: 10.1016/j.jcta.2008.09.004.

[19]

F. J. MacWilliams, Permutation decoding of systematic codes, Bell System Tech. J., 43 (1964), 485-505.

[20]

F. J. MacWilliams and N. J. A. Sloane, "The Theory of Error-Correcting Codes,'' Amsterdam, North-Holland, 1983.

[21]

C. S. J. A. Nash-Williams, Hamiltonian arcs and circuits, in "1971 Recent Trends in Graph Theory (Proc. Conf, New York, 1970),'' Springer, Berlin, (1970), 197-210.

[22]

J. Schönheim, On coverings, Pacific J. Math., 14 (1964), 1405-1411.

[23]

G. Van de Voorde, "Blocking Sets in Finite Projective Spaces and Coding Theory,'' Ph.D thesis, University of Ghent, 2010.

[24]

H. Whitney, Congruent graphs and the connectivity of graphs, Amer. J. Math., 54 (1932), 154-168. doi: 10.2307/2371086.

show all references

References:
[1]

E. F. Assmus, Jr. and J. D. Key, "Designs and their Codes,'' Cambridge University Press, Cambridge, 1992; second printing with corrections, 1993.

[2]

R. Balakrishnan and K. Ranganathan, "A Textbook of Graph Theory,'' New York, Springer-Verlag, 2000.

[3]

W. Bosma, J. Cannon and C. Playoust, The Magma algebra system I: The user language, J. Symb. Comp., 24 (1997), 235-265. doi: 10.1006/jsco.1996.0125.

[4]

J. Cannon, A. Steel and G. White, Linear codes over finite fields, in "Handbook of Magma Functions'' (eds. J. Cannon and W. Bosma), Computational Algebra Group, Department of Mathematics, University of Sydney, (2006), 3951-4023; available online at http://magma.maths.usyd.edu.au/magma

[5]

K. Chouinard, "Weight Distributions of Codes from Planes,'' Ph.D thesis, University of Virginia, 2000.

[6]

W. Fish, J. D. Key and E. Mwambene, Binary codes of line graphs from the $n$-cube, J. Symbolic Comput., 45 (2010), 800-812. doi: 10.1016/j.jsc.2010.03.012.

[7]

W. Fish, J. D. Key and E. Mwambene, Codes from the incidence matrices and line graphs of Hamming graphs, Discrete Math., 310 (2010), 1884-1897. doi: 10.1016/j.disc.2010.02.010.

[8]

W. Fish, J. D. Key and E. Mwambene, Codes from the incidence matrices and line graphs of Hamming graphs $H^k(n,2)$ for $k \ge 2$, Adv. Math. Commun., to appear.

[9]

D. M. Gordon, Minimal permutation sets for decoding the binary Golay codes, IEEE Trans. Inform. Theory, 28 (1982), 541-543. doi: 10.1109/TIT.1982.1056504.

[10]

W. C. Huffman, Codes and groups, in "Handbook of Coding Theory'' (eds. V.S. Pless and W.C. Huffman), Amsterdam, Elsevier, (1998), 1345-1440.

[11]

B. Jackson, Hamilton cycles in regular 2-connected graphs, J. Combin. Theory Ser. B, 29 (1980), 27-46. doi: 10.1016/0095-8956(80)90042-8.

[12]

J. D. Key, T. P. McDonough and V. C. Mavron, Partial permutation decoding for codes from finite planes, European J. Combin., 26 (2005), 665-682. doi: 10.1016/j.ejc.2004.04.007.

[13]

J. D. Key, T. P. McDonough and V. C. Mavron, Information sets and partial permutation decoding for codes from finite geometries, Finite Fields Appl., 12 (2006), 232-247. doi: 10.1016/j.ffa.2005.05.007.

[14]

J. D. Key, J. Moori and B. G. Rodrigues, Codes associated with triangular graphs, and permutation decoding, Int. J. Inform. Coding Theory, 1 (2010), 334-349. doi: 10.1504/IJICOT.2010.032547.

[15]

J. D. Key, J. Moori and B. G. Rodrigues, Codes from incidence matrices and line graphs of symplectic graphs, in preparation.

[16]

J. D. Key and B. G. Rodrigues, Codes associated with lattice graphs, and permutation decoding, Discrete Appl. Math., 158 (2010), 1807-1815. doi: 10.1016/j.dam.2010.07.003.

[17]

H.-J. Kroll and R. Vincenti, PD-sets related to the codes of some classical varieties, Discrete Math., 301 (2005), 89-105. doi: 10.1016/j.disc.2004.11.020.

[18]

M. Lavrauw, L. Storme, P. Sziklai and G. Van de Voorde, An empty interval in the spectrum of small weight codewords in the code from points and k-spaces of $PG(n,q)$, J. Combin. Theory Ser. A, 116 (2009), 996-1001. doi: 10.1016/j.jcta.2008.09.004.

[19]

F. J. MacWilliams, Permutation decoding of systematic codes, Bell System Tech. J., 43 (1964), 485-505.

[20]

F. J. MacWilliams and N. J. A. Sloane, "The Theory of Error-Correcting Codes,'' Amsterdam, North-Holland, 1983.

[21]

C. S. J. A. Nash-Williams, Hamiltonian arcs and circuits, in "1971 Recent Trends in Graph Theory (Proc. Conf, New York, 1970),'' Springer, Berlin, (1970), 197-210.

[22]

J. Schönheim, On coverings, Pacific J. Math., 14 (1964), 1405-1411.

[23]

G. Van de Voorde, "Blocking Sets in Finite Projective Spaces and Coding Theory,'' Ph.D thesis, University of Ghent, 2010.

[24]

H. Whitney, Congruent graphs and the connectivity of graphs, Amer. J. Math., 54 (1932), 154-168. doi: 10.2307/2371086.

[1]

Washiela Fish, Jennifer D. Key, Eric Mwambene. Partial permutation decoding for simplex codes. Advances in Mathematics of Communications, 2012, 6 (4) : 505-516. doi: 10.3934/amc.2012.6.505

[2]

Ricardo A. Podestá, Denis E. Videla. The weight distribution of irreducible cyclic codes associated with decomposable generalized Paley graphs. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021002

[3]

Kwankyu Lee. Decoding of differential AG codes. Advances in Mathematics of Communications, 2016, 10 (2) : 307-319. doi: 10.3934/amc.2016007

[4]

Elisa Gorla, Felice Manganiello, Joachim Rosenthal. An algebraic approach for decoding spread codes. Advances in Mathematics of Communications, 2012, 6 (4) : 443-466. doi: 10.3934/amc.2012.6.443

[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]

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

[7]

Terasan Niyomsataya, Ali Miri, Monica Nevins. Decoding affine reflection group codes with trellises. Advances in Mathematics of Communications, 2012, 6 (4) : 385-400. doi: 10.3934/amc.2012.6.385

[8]

Heide Gluesing-Luerssen, Uwe Helmke, José Ignacio Iglesias Curto. Algebraic decoding for doubly cyclic convolutional codes. Advances in Mathematics of Communications, 2010, 4 (1) : 83-99. doi: 10.3934/amc.2010.4.83

[9]

Xiang Wang, Wenjuan Yin. New nonexistence results on perfect permutation codes under the hamming metric. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021058

[10]

Hannes Bartz, Antonia Wachter-Zeh. Efficient decoding of interleaved subspace and Gabidulin codes beyond their unique decoding radius using Gröbner bases. Advances in Mathematics of Communications, 2018, 12 (4) : 773-804. doi: 10.3934/amc.2018046

[11]

Joan-Josep Climent, Diego Napp, Raquel Pinto, Rita Simões. Decoding of $2$D convolutional codes over an erasure channel. Advances in Mathematics of Communications, 2016, 10 (1) : 179-193. doi: 10.3934/amc.2016.10.179

[12]

Johan Rosenkilde. Power decoding Reed-Solomon codes up to the Johnson radius. Advances in Mathematics of Communications, 2018, 12 (1) : 81-106. doi: 10.3934/amc.2018005

[13]

Irene I. Bouw, Sabine Kampf. Syndrome decoding for Hermite codes with a Sugiyama-type algorithm. Advances in Mathematics of Communications, 2012, 6 (4) : 419-442. doi: 10.3934/amc.2012.6.419

[14]

Anas Chaaban, Vladimir Sidorenko, Christian Senger. On multi-trial Forney-Kovalev decoding of concatenated codes. Advances in Mathematics of Communications, 2014, 8 (1) : 1-20. doi: 10.3934/amc.2014.8.1

[15]

Vladimir Sidorenko, Christian Senger, Martin Bossert, Victor Zyablov. Single-trial decoding of concatenated codes using fixed or adaptive erasing. Advances in Mathematics of Communications, 2010, 4 (1) : 49-60. doi: 10.3934/amc.2010.4.49

[16]

Peter Beelen, Kristian Brander. Efficient list decoding of a class of algebraic-geometry codes. Advances in Mathematics of Communications, 2010, 4 (4) : 485-518. doi: 10.3934/amc.2010.4.485

[17]

Alexey Frolov, Victor Zyablov. On the multiple threshold decoding of LDPC codes over GF(q). Advances in Mathematics of Communications, 2017, 11 (1) : 123-137. doi: 10.3934/amc.2017007

[18]

Julia Lieb, Raquel Pinto. A decoding algorithm for 2D convolutional codes over the erasure channel. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021031

[19]

Fernando Hernando, Tom Høholdt, Diego Ruano. List decoding of matrix-product codes from nested codes: An application to quasi-cyclic codes. Advances in Mathematics of Communications, 2012, 6 (3) : 259-272. doi: 10.3934/amc.2012.6.259

[20]

Jennifer D. Key, Washiela Fish, Eric Mwambene. Codes from the incidence matrices and line graphs of Hamming graphs $H^k(n,2)$ for $k \geq 2$. Advances in Mathematics of Communications, 2011, 5 (2) : 373-394. doi: 10.3934/amc.2011.5.373

2021 Impact Factor: 1.015

Metrics

  • PDF downloads (285)
  • HTML views (0)
  • Cited by (7)

Other articles
by authors

[Back to Top]