American Institute of Mathematical Sciences

Advanced
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

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.  Google Scholar

[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.  Google Scholar

[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.  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), 3951-4023; Magma, Computational Algebra Group, Department of Mathematics, University of Sydney, 2006, V2.13, http://magma.maths.usyd.edu.au/magma Google Scholar

[5]

W. Fish, "Codes from Uniform Subset Graphs and Cyclic Products,'' Ph.D thesis, University of the Western Cape, 2007. Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  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 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.  Google Scholar

[16]

J. D. Key and B. G. Rodrigues, Codes from incidence matrices of strongly regular graphs,, in preparation., ().   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[19]

J. H. van Lint and R. M. Wilson, "A Course in Combinatorics,'' Cambridge University Press, Cambridge, 1992.  Google Scholar

[20]

F. J. MacWilliams, Permutation decoding of systematic codes, Bell System Tech. J., 43 (1964), 485-505. Google Scholar

[21]

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

[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.  Google Scholar

[23]

J. Schönheim, On coverings, Pacific J. Math., 14 (1964), 1405-1411.  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.  Google Scholar

[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.  Google Scholar

[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.  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), 3951-4023; Magma, Computational Algebra Group, Department of Mathematics, University of Sydney, 2006, V2.13, http://magma.maths.usyd.edu.au/magma Google Scholar

[5]

W. Fish, "Codes from Uniform Subset Graphs and Cyclic Products,'' Ph.D thesis, University of the Western Cape, 2007. Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  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 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.  Google Scholar

[16]

J. D. Key and B. G. Rodrigues, Codes from incidence matrices of strongly regular graphs,, in preparation., ().   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[19]

J. H. van Lint and R. M. Wilson, "A Course in Combinatorics,'' Cambridge University Press, Cambridge, 1992.  Google Scholar

[20]

F. J. MacWilliams, Permutation decoding of systematic codes, Bell System Tech. J., 43 (1964), 485-505. Google Scholar

[21]

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

[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.  Google Scholar

[23]

J. Schönheim, On coverings, Pacific J. Math., 14 (1964), 1405-1411.  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]

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$n 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

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (67)
  • HTML views (0)
  • Cited by (15)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy