American Institute of Mathematical Sciences

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. Google Scholar [2] R. Balakrishnan and K. Ranganathan, "A Textbook of Graph Theory,'' New York, Springer-Verlag, 2000. Google Scholar [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.  Google Scholar [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 Google Scholar [5] K. Chouinard, "Weight Distributions of Codes from Planes,'' Ph.D thesis, University of Virginia, 2000. Google Scholar [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.  Google Scholar [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.  Google Scholar [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., ().   Google Scholar [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.  Google Scholar [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. Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [15] J. D. Key, J. Moori and B. G. Rodrigues, Codes from incidence matrices and line graphs of symplectic graphs,, in preparation., ().   Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [19] F. J. MacWilliams, Permutation decoding of systematic codes, Bell System Tech. J., 43 (1964), 485-505. Google Scholar [20] F. J. MacWilliams and N. J. A. Sloane, "The Theory of Error-Correcting Codes,'' Amsterdam, North-Holland, 1983. Google Scholar [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.  Google Scholar [22] J. Schönheim, On coverings, Pacific J. Math., 14 (1964), 1405-1411.  Google Scholar [23] G. Van de Voorde, "Blocking Sets in Finite Projective Spaces and Coding Theory,'' Ph.D thesis, University of Ghent, 2010. Google Scholar [24] H. Whitney, Congruent graphs and the connectivity of graphs, Amer. J. Math., 54 (1932), 154-168. doi: 10.2307/2371086.  Google Scholar

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. Google Scholar [2] R. Balakrishnan and K. Ranganathan, "A Textbook of Graph Theory,'' New York, Springer-Verlag, 2000. Google Scholar [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.  Google Scholar [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 Google Scholar [5] K. Chouinard, "Weight Distributions of Codes from Planes,'' Ph.D thesis, University of Virginia, 2000. Google Scholar [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.  Google Scholar [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.  Google Scholar [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., ().   Google Scholar [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.  Google Scholar [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. Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [15] J. D. Key, J. Moori and B. G. Rodrigues, Codes from incidence matrices and line graphs of symplectic graphs,, in preparation., ().   Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [19] F. J. MacWilliams, Permutation decoding of systematic codes, Bell System Tech. J., 43 (1964), 485-505. Google Scholar [20] F. J. MacWilliams and N. J. A. Sloane, "The Theory of Error-Correcting Codes,'' Amsterdam, North-Holland, 1983. Google Scholar [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.  Google Scholar [22] J. Schönheim, On coverings, Pacific J. Math., 14 (1964), 1405-1411.  Google Scholar [23] G. Van de Voorde, "Blocking Sets in Finite Projective Spaces and Coding Theory,'' Ph.D thesis, University of Ghent, 2010. Google Scholar [24] H. Whitney, Congruent graphs and the connectivity of graphs, Amer. J. Math., 54 (1932), 154-168. doi: 10.2307/2371086.  Google Scholar
 [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] 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 [10] 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 [11] 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 [12] 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 [13] 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 [14] 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 [15] 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 [16] 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 [17] 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 [18] 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 [19] Cristóbal Camarero, Carmen Martínez, Ramón Beivide. Identifying codes of degree 4 Cayley graphs over Abelian groups. Advances in Mathematics of Communications, 2015, 9 (2) : 129-148. doi: 10.3934/amc.2015.9.129 [20] Christine A. Kelley, Deepak Sridhara, Joachim Rosenthal. Zig-zag and replacement product graphs and LDPC codes. Advances in Mathematics of Communications, 2008, 2 (4) : 347-372. doi: 10.3934/amc.2008.2.347

2020 Impact Factor: 0.935