Codes from incidence matrices and line graphs of Paley graphs

Dina Ghinelli; Jennifer D. Key

doi:10.3934/amc.2011.5.93

Article Contents

2011, Volume 5, Issue 1: 93-108. Doi: 10.3934/amc.2011.5.93

This issue Previous Article Cryptanalysis of a 2-party key establishment based on a semigroup action problem Next Article Some remarks on the construction of class polynomials

Codes from incidence matrices and line graphs of Paley graphs

Dina Ghinelli^1, and
Jennifer D. Key^2,

1.
Dipartimento di Matematica, Università di Roma 'La Sapienza', I-00185 Rome
2.
School of Mathematical Sciences, University of KwaZulu-Natal, Pietermaritzburg 3209

Received: August 31, 2010

Published: January 2011

Abstract Related Papers Cited by

Abstract

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}]$₂ 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)$.

Keywords:

Mathematics Subject Classification: Primary: 05C45, 05B05; Secondary: 94B05.

Citation:

Related Papers

Cited by

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.