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, (1992).   Google Scholar

[2]

R. Balakrishnan and K. Ranganathan, "A Textbook of Graph Theory,'', New York, (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.  doi: 10.1006/jsco.1996.0125.  Google Scholar

[4]

J. Cannon, A. Steel and G. White, Linear codes over finite fields,, in, (2006), 3951.   Google Scholar

[5]

K. Chouinard, "Weight Distributions of Codes from Planes,'', Ph.D thesis, (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.  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.  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.  doi: 10.1109/TIT.1982.1056504.  Google Scholar

[10]

W. C. Huffman, Codes and groups,, in, (1998), 1345.   Google Scholar

[11]

B. Jackson, Hamilton cycles in regular 2-connected graphs,, J. Combin. Theory Ser. B, 29 (1980), 27.  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.  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.  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.  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.  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.  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.  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.   Google Scholar

[20]

F. J. MacWilliams and N. J. A. Sloane, "The Theory of Error-Correcting Codes,'', Amsterdam, (1983).   Google Scholar

[21]

C. S. J. A. Nash-Williams, Hamiltonian arcs and circuits,, in, (1970), 197.   Google Scholar

[22]

J. Schönheim, On coverings,, Pacific J. Math., 14 (1964), 1405.   Google Scholar

[23]

G. Van de Voorde, "Blocking Sets in Finite Projective Spaces and Coding Theory,'', Ph.D thesis, (2010).   Google Scholar

[24]

H. Whitney, Congruent graphs and the connectivity of graphs,, Amer. J. Math., 54 (1932), 154.  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, (1992).   Google Scholar

[2]

R. Balakrishnan and K. Ranganathan, "A Textbook of Graph Theory,'', New York, (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.  doi: 10.1006/jsco.1996.0125.  Google Scholar

[4]

J. Cannon, A. Steel and G. White, Linear codes over finite fields,, in, (2006), 3951.   Google Scholar

[5]

K. Chouinard, "Weight Distributions of Codes from Planes,'', Ph.D thesis, (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.  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.  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.  doi: 10.1109/TIT.1982.1056504.  Google Scholar

[10]

W. C. Huffman, Codes and groups,, in, (1998), 1345.   Google Scholar

[11]

B. Jackson, Hamilton cycles in regular 2-connected graphs,, J. Combin. Theory Ser. B, 29 (1980), 27.  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.  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.  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.  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.  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.  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.  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.   Google Scholar

[20]

F. J. MacWilliams and N. J. A. Sloane, "The Theory of Error-Correcting Codes,'', Amsterdam, (1983).   Google Scholar

[21]

C. S. J. A. Nash-Williams, Hamiltonian arcs and circuits,, in, (1970), 197.   Google Scholar

[22]

J. Schönheim, On coverings,, Pacific J. Math., 14 (1964), 1405.   Google Scholar

[23]

G. Van de Voorde, "Blocking Sets in Finite Projective Spaces and Coding Theory,'', Ph.D thesis, (2010).   Google Scholar

[24]

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

[1]

Agnaldo José Ferrari, Tatiana Miguel Rodrigues de Souza. Rotated $ A_n $-lattice codes of full diversity. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020118

2019 Impact Factor: 0.734

Metrics

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

Other articles
by authors

[Back to Top]