American Institute of Mathematical Sciences

Advanced
doi: 10.3934/amc.2020079

Binary codes from $ m $-ary $ n $-cubes $ Q^m_n $

Jennifer D. Key 1,, and  Bernardo G. Rodrigues 2,

1. 

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

Department of Mathematics and Applied Mathematics, University of Pretoria, Hatfield 0028, South Africa

* Corresponding author: J. D. Key

Received  October 2019 Revised  December 2019 Published  April 2020

Fund Project: The second author is supported by the National Research Foundation of South Africa (Grant Numbers 95725 and 106071)

We examine the binary codes from adjacency matrices of the graph with vertices the nodes of the $ m $-ary $ n $-cube $ Q^m_n $ and with adjacency defined by the Lee metric. For $ n = 2 $ and $ m $ odd, we obtain the parameters of the code and its dual, and show the codes to be $ LCD $. We also find $ s $-PD-sets of size $ s+1 $ for $ s < \frac{m-1}{2} $ for the dual codes, i.e. $ [m^2,2m-1,m]_2 $ codes, when $ n = 2 $ and $ m\ge 5 $ is odd.

Keywords: LCD codes, Lee graph, permutation decoding.
Mathematics Subject Classification: Primary: 05C50, 94B05; Secondary: 05B05.
Citation: Jennifer D. Key, Bernardo G. Rodrigues. Binary codes from $ m $-ary $ n $-cubes $ Q^m_n $. Advances in Mathematics of Communications, doi: 10.3934/amc.2020079
References:
[1]

E. F. Assmus, Jr. and J. D. Key, Designs and Their Codes, Cambridge Tracts in Mathematics,103. Cambridge University Press, Cambridge, 1992. doi: 10.1017/CBO9781316529836.  Google Scholar

[2]

B. Bose, B. Broeg, Y. Kwon and Y. Ashir, Lee distance and topological properties of $k$-ary $n$-cubes, IEEE Trans. Computers, 44 (1995), 1021-1030.  doi: 10.1109/12.403718.  Google Scholar

[3]

W. Bosma, J. Cannon and C. Playoust, The Magma algebra system. I: The user language, J. Symbolic Comput., 24 (1997), 235-265.  doi: 10.1006/jsco.1996.0125.  Google Scholar

[4]

J. Cannon, A. Steel and G. White, Linear codes over finite fields, Handbook of Magma Functions, Computational Algebra Group, Department of Mathematics, University of Sydney, (2006), 3951–4023. http://magma.maths.usyd.edu.au/magma. Google Scholar

[5]

K. Day and A. E. Al Ayyoub, Fault diameter of $k$-ary $n$-cube networks, IEEE Trans. Parallel and Distributed Systems, 8 (1997), 903-907.  doi: 10.1109/71.615436.  Google Scholar

[6]

W. Fish, Binary codes and permutation decoding sets from the graph products of cycles, Appl. Algebra Engrg. Comm. Comput., 28 (2017), 369-389.  doi: 10.1007/s00200-016-0310-y.  Google Scholar

[7]

W. Fish, J. D. Key and E. Mwambene, LCDcodes from products of graphs, In preparation. Google Scholar

[8]

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.  doi: 10.1016/j.disc.2008.09.024.  Google Scholar

[9]

W. Fish, Codes from Uniform Subset Graphs and Cycle Products, PhD thesis, University of the Western Cape, 2007. 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, Handbook of Coding Theory, North-Holland, Amsterdam, 1, 2 (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, T. P. Mc{D}onough and V. C. Mavron, Improved partial permutation decoding for Reed-Muller codes, Discrete Math., 340 (2017), 722-728.  doi: 10.1016/j.disc.2016.11.031.  Google Scholar

[15]

J. D. Key and B. G. Rodrigues, LCD codes from adjacency matrices of graphs, Appl. Algebra Engrg. Comm. Comput., 29 (2018), 227-244.  doi: 10.1007/s00200-017-0339-6.  Google Scholar

[16]

J. D. Key and B. G. Rodrigues, Special $LCD$ codes from {P}eisert and generalized Peisert graphs, Graphs Combin., 35 (2019), 633-652.  doi: 10.1007/s00373-019-02019-0.  Google Scholar

[17]

C. Kravvaritis, Determinant evaluations for binary circulant matrices, Spec. Matrices, 1 (2013), 187–199. http://dx.doi.org/10.2478/spma-2014-0019.  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]

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

[20]

F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes. II, North-Holland Mathematical Library, Vol. 16. North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977.  Google Scholar

[21]

J. L. Massey, Linear codes with complementary duals, Discrete Math., 106/107 (1992), 337-342.  doi: 10.1016/0012-365X(92)90563-U.  Google Scholar

[22]

J. Schönheim, On coverings, Pacific J. Math., 14 (1964), 1405-1411.  doi: 10.2140/pjm.1964.14.1405.  Google Scholar

show all references

References:
[1]

E. F. Assmus, Jr. and J. D. Key, Designs and Their Codes, Cambridge Tracts in Mathematics,103. Cambridge University Press, Cambridge, 1992. doi: 10.1017/CBO9781316529836.  Google Scholar

[2]

B. Bose, B. Broeg, Y. Kwon and Y. Ashir, Lee distance and topological properties of $k$-ary $n$-cubes, IEEE Trans. Computers, 44 (1995), 1021-1030.  doi: 10.1109/12.403718.  Google Scholar

[3]

W. Bosma, J. Cannon and C. Playoust, The Magma algebra system. I: The user language, J. Symbolic Comput., 24 (1997), 235-265.  doi: 10.1006/jsco.1996.0125.  Google Scholar

[4]

J. Cannon, A. Steel and G. White, Linear codes over finite fields, Handbook of Magma Functions, Computational Algebra Group, Department of Mathematics, University of Sydney, (2006), 3951–4023. http://magma.maths.usyd.edu.au/magma. Google Scholar

[5]

K. Day and A. E. Al Ayyoub, Fault diameter of $k$-ary $n$-cube networks, IEEE Trans. Parallel and Distributed Systems, 8 (1997), 903-907.  doi: 10.1109/71.615436.  Google Scholar

[6]

W. Fish, Binary codes and permutation decoding sets from the graph products of cycles, Appl. Algebra Engrg. Comm. Comput., 28 (2017), 369-389.  doi: 10.1007/s00200-016-0310-y.  Google Scholar

[7]

W. Fish, J. D. Key and E. Mwambene, LCDcodes from products of graphs, In preparation. Google Scholar

[8]

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.  doi: 10.1016/j.disc.2008.09.024.  Google Scholar

[9]

W. Fish, Codes from Uniform Subset Graphs and Cycle Products, PhD thesis, University of the Western Cape, 2007. 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, Handbook of Coding Theory, North-Holland, Amsterdam, 1, 2 (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, T. P. Mc{D}onough and V. C. Mavron, Improved partial permutation decoding for Reed-Muller codes, Discrete Math., 340 (2017), 722-728.  doi: 10.1016/j.disc.2016.11.031.  Google Scholar

[15]

J. D. Key and B. G. Rodrigues, LCD codes from adjacency matrices of graphs, Appl. Algebra Engrg. Comm. Comput., 29 (2018), 227-244.  doi: 10.1007/s00200-017-0339-6.  Google Scholar

[16]

J. D. Key and B. G. Rodrigues, Special $LCD$ codes from {P}eisert and generalized Peisert graphs, Graphs Combin., 35 (2019), 633-652.  doi: 10.1007/s00373-019-02019-0.  Google Scholar

[17]

C. Kravvaritis, Determinant evaluations for binary circulant matrices, Spec. Matrices, 1 (2013), 187–199. http://dx.doi.org/10.2478/spma-2014-0019.  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]

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

[20]

F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes. II, North-Holland Mathematical Library, Vol. 16. North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977.  Google Scholar

[21]

J. L. Massey, Linear codes with complementary duals, Discrete Math., 106/107 (1992), 337-342.  doi: 10.1016/0012-365X(92)90563-U.  Google Scholar

[22]

J. Schönheim, On coverings, Pacific J. Math., 14 (1964), 1405-1411.  doi: 10.2140/pjm.1964.14.1405.  Google Scholar

Table 1.  Blocks in $ \mathcal{{B}} $$ _m $
$ m $
$ 5 $ $ 0,2 $
$ 7 $ $ 0,0 $ $ 0,3 $ $ 2,2 $
$ 9 $ $ 0,2 $ $ 0,3 $ $ 2,4 $
$ 11 $ $ 0,0 $ $ 0,3 $ $ 0,4 $ $ 2,2 $ $ 2,5 $ $ 4,4 $
$ 13 $ $ 0,2 $ $ 0,3 $ $ 0,6 $ $ 2,4 $ $ 2,5 $ $ 4,6 $
$ 15 $ $ 0,0 $ $ 0,3 $ $ 0,4 $ $ 0,7 $ $ 2,2 $ $ 2,5 $ $ 2,6 $ $ 4,4 $ $ 4,7 $ $ 6,6 $
$ 17 $ $ 0,2 $ $ 0,3 $ $ 0,6 $ $ 0,7 $ $ 2,4 $ $ 2,5 $ $ 2,8 $ $ 4,6 $ $ 4,7 $ $ 6,8 $
$ 19 $ $ 0,0 $ $ 0,3 $ $ 0,4 $ $ 0,7 $ 0, 8 $ 2,2 $ $ 2,5 $ $ 2,6 $ 2, 9 $ 4,4 $ $ 4,7 $ 4, 8 $ 6,6 $ 6, 9 8, 8
Table Options

Download as excel

$ m $
$ 5 $ $ 0,2 $
$ 7 $ $ 0,0 $ $ 0,3 $ $ 2,2 $
$ 9 $ $ 0,2 $ $ 0,3 $ $ 2,4 $
$ 11 $ $ 0,0 $ $ 0,3 $ $ 0,4 $ $ 2,2 $ $ 2,5 $ $ 4,4 $
$ 13 $ $ 0,2 $ $ 0,3 $ $ 0,6 $ $ 2,4 $ $ 2,5 $ $ 4,6 $
$ 15 $ $ 0,0 $ $ 0,3 $ $ 0,4 $ $ 0,7 $ $ 2,2 $ $ 2,5 $ $ 2,6 $ $ 4,4 $ $ 4,7 $ $ 6,6 $
$ 17 $ $ 0,2 $ $ 0,3 $ $ 0,6 $ $ 0,7 $ $ 2,4 $ $ 2,5 $ $ 2,8 $ $ 4,6 $ $ 4,7 $ $ 6,8 $
$ 19 $ $ 0,0 $ $ 0,3 $ $ 0,4 $ $ 0,7 $ 0, 8 $ 2,2 $ $ 2,5 $ $ 2,6 $ 2, 9 $ 4,4 $ $ 4,7 $ 4, 8 $ 6,6 $ 6, 9 8, 8
[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]

Kwankyu Lee. Decoding of differential AG codes. Advances in Mathematics of Communications, 2016, 10 (2) : 307-319. doi: 10.3934/amc.2016007
[3]

Haode Yan, Hao Liu, Chengju Li, Shudi Yang. Parameters of LCD BCH codes with two lengths. Advances in Mathematics of Communications, 2018, 12 (3) : 579-594. doi: 10.3934/amc.2018034
[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]

Bram van Asch, Frans Martens. Lee weight enumerators of self-dual codes and theta functions. Advances in Mathematics of Communications, 2008, 2 (4) : 393-402. doi: 10.3934/amc.2008.2.393
[7]

Bram van Asch, Frans Martens. A note on the minimum Lee distance of certain self-dual modular codes. Advances in Mathematics of Communications, 2012, 6 (1) : 65-68. doi: 10.3934/amc.2012.6.65
[8]

Minjia Shi, Daitao Huang, Lin Sok, Patrick Solé. Double circulant self-dual and LCD codes over Galois rings. Advances in Mathematics of Communications, 2019, 13 (1) : 171-183. doi: 10.3934/amc.2019011
[9]

Fatma-Zohra Benahmed, Kenza Guenda, Aicha Batoul, Thomas Aaron Gulliver. Some new constructions of isodual and LCD codes over finite fields. Advances in Mathematics of Communications, 2019, 13 (2) : 281-296. doi: 10.3934/amc.2019019
[10]

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
[11]

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
[12]

Masaaki Harada. Note on the residue codes of self-dual $\mathbb{Z}_4$-codes having large minimum Lee weights. Advances in Mathematics of Communications, 2016, 10 (4) : 695-706. doi: 10.3934/amc.2016035
[13]

Xia Li, Feng Cheng, Chunming Tang, Zhengchun Zhou. Some classes of LCD codes and self-orthogonal codes over finite fields. Advances in Mathematics of Communications, 2019, 13 (2) : 267-280. doi: 10.3934/amc.2019018
[14]

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
[15]

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
[16]

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
[17]

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
[18]

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
[19]

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
[20]

Peter Beelen, Kristian Brander. Efficient list decoding of a class of algebraic-geometry codes. Advances in Mathematics of Communications, 2010, 4 (4) : 485-518. doi: 10.3934/amc.2010.4.485

2018 Impact Factor: 0.879

Tools

Article outline

Figures and Tables

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences