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

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

May 2011, 5(2): 373-394. doi: 10.3934/amc.2011.5.373

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

Jennifer D. Key ^1, , Washiela Fish ^1, and Eric Mwambene ^1,

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

Received May 2010 Revised June 2010 Published May 2011

Abstract
Related Papers

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: Hamming graphs, codes, permutation decoding..

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

Citation: 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

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.

show all references

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.

[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]	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
[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]	Joaquim Borges, Josep Rifà, Victor Zinoviev. Completely regular codes by concatenating Hamming codes. Advances in Mathematics of Communications, 2018, 12 (2) : 337-349. doi: 10.3934/amc.2018021
[7]	Anuradha Sharma, Saroj Rani. Trace description and Hamming weights of irreducible constacyclic codes. Advances in Mathematics of Communications, 2018, 12 (1) : 123-141. doi: 10.3934/amc.2018008
[8]	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
[9]	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
[10]	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
[11]	B. K. Dass, Namita Sharma, Rashmi Verma. Characterization of extended Hamming and Golay codes as perfect codes in poset block spaces. Advances in Mathematics of Communications, 2018, 12 (4) : 629-639. doi: 10.3934/amc.2018037
[12]	Sergio R. López-Permouth, Steve Szabo. On the Hamming weight of repeated root cyclic and negacyclic codes over Galois rings. Advances in Mathematics of Communications, 2009, 3 (4) : 409-420. doi: 10.3934/amc.2009.3.409
[13]	Olof Heden, Faina I. Solov’eva. Partitions of $\mathbb F$ⁿ into non-parallel Hamming codes. Advances in Mathematics of Communications, 2009, 3 (4) : 385-397. doi: 10.3934/amc.2009.3.385
[14]	Alonso sepúlveda Castellanos. Generalized Hamming weights of codes over the $\mathcal{GH}$ curve. Advances in Mathematics of Communications, 2017, 11 (1) : 115-122. doi: 10.3934/amc.2017006
[15]	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
[16]	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
[17]	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
[18]	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
[19]	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
[20]	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

2021 Impact Factor: 1.015

Tools

Metrics

Other articles
by authors

on AIMS
Jennifer D. Key Washiela Fish Eric Mwambene
on Google Scholar
Jennifer D. Key Washiela Fish Eric Mwambene

[Back to Top]