Codes from the incidence matrices and line graphs of Hamming graphs $H^k(n,2)$ for $k \geq 2$

Jennifer D. Key; Washiela Fish; Eric Mwambene

doi:10.3934/amc.2011.5.373

Article Contents

2011, Volume 5, Issue 2: 373-394. Doi: 10.3934/amc.2011.5.373

This issue Previous Article Associating a numerical semigroup to the triangle-free configurations Next Article On the weight distribution of codes over finite rings

Codes from the incidence matrices and line graphs of Hamming graphs $H^k(n,2)$ for $k \geq 2$

1.
Department of Mathematics and Applied Mathematics, University of the Western Cape, 7535 Bellville

Received: May 2010

Revised: June 2010

Published: May 2011

Abstract / Introduction Related Papers Cited by

Abstract

We examine the $p$-ary codes, for any prime $p$, that can be obtained from incidence matrices and line graphs of the Hamming graphs, $H^k(n,m)$, for $k \geq 2$. For $m=2$, we obtain the main parameters of the codes from the incidence matrices, including the minimum weight and the nature of the minimum words. We show that all the codes can be used for full permutation decoding.

Keywords:

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

Citation:

Related Papers

Cited by

References

[1]	E. F. Assmus, Jr and J. D. Key, "Designs and Their Codes,'' Cambridge University Press, Cambridge, 1992.
[2]	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.
[3]	A. E. Brouwer, A. M. Cohen and A. Neumaier, Distance-Regular Graphs, in "Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)],'' Springer-Verlag, Berlin, (1989), 495.
[4]	J. Cannon, A. Steel and G. White, Linear codes over finite fields, in "Handbook of Magma Functions'' (eds. J. Cannon and W. Bosma), 3951-4023; Magma, Computational Algebra Group, Department of Mathematics, University of Sydney, 2006, V2.13, http://magma.maths.usyd.edu.au/magma
[5]	W. Fish, "Codes from Uniform Subset Graphs and Cyclic Products,'' Ph.D thesis, University of the Western Cape, 2007.
[6]	W. Fish, J. D. Key and E. Mwambene, Codes, designs and groups from the Hamming graphs, J. Combin. Inform. System Sci., 34 (2009), 169-182.
[7]	W. Fish, J. D. Key and E. Mwambene, Graphs, designs and codes related to the $n$-cube, Discrete Math., 309 (2009), 3255-3269.doi: 10.1016/j.disc.2008.09.024.
[8]	W. Fish, J. D. Key and E. Mwambene, Binary codes of line graphs from the $n$-cube, J. Symb. Comput., 45 (2010), 800-812.doi: 10.1016/j.jsc.2010.03.012.
[9]	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.
[10]	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.
[11]	W. C. Huffman, Codes and groups, in "Handbook of Coding Theory'' (eds. V.S. Pless and W.C. Huffman), Elsevier, Amsterdam, (1998), 1345-1440.
[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 and B. G. Rodrigues, Codes from lattice and related graphs, and permutation decoding, Discrete Appl. Math., 158 (2010), 1807-1815.doi: 10.1016/j.dam.2010.07.003.
[16]	J. D. Key and B. G. Rodrigues, Codes from incidence matrices of strongly regular graphs, in preparation.
[17]	J. D. Key and P. Seneviratne, Permutation decoding for binary self-dual codes from the graph $Q_n$ where $n$ is even, in "Advances in Coding Theory and Cryptology'' (eds. T. Shaska, W. C. Huffman, D. Joyner and V. Ustimenko), World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, (2007), 152-159.
[18]	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.
[19]	J. H. van Lint and R. M. Wilson, "A Course in Combinatorics,'' Cambridge University Press, Cambridge, 1992.
[20]	F. J. MacWilliams, Permutation decoding of systematic codes, Bell System Tech. J., 43 (1964), 485-505.
[21]	F. J. MacWilliams and N. J. A. Sloane, "The Theory of Error-Correcting Codes,'' North-Holland, Amsterdam, 1983.
[22]	R. Peeters., On the $p$-ranks of the adjacency matrices of distance-regular graphs, J. Algebraic Combin., 15 (2002), 127-149.doi: 10.1023/A:1013842904024.
[23]	J. Schönheim, On coverings, Pacific J. Math., 14 (1964), 1405-1411.
[24]	H. Whitney, Congruent graphs and the connectivity of graphs, Amer. J. Math., 54 (1932), 154-168.doi: 10.2307/2371086.