American Institute of Mathematical Sciences

Advanced
August  2021, 15(3): 507-524. 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  August 2021 Early access  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, 2021, 15 (3) : 507-524. 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.

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

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

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

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

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

[7]

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

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

[9]

W. Fish, Codes from Uniform Subset Graphs and Cycle Products, PhD thesis, University of the Western Cape, 2007.

[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, Handbook of Coding Theory, North-Holland, Amsterdam, 1, 2 (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, 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.

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

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

[17]

C. Kravvaritis, Determinant evaluations for binary circulant matrices, Spec. Matrices, 1 (2013), 187–199. http://dx.doi.org/10.2478/spma-2014-0019.

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

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

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

[21]

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

[22]

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

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.

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

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

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

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

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

[7]

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

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

[9]

W. Fish, Codes from Uniform Subset Graphs and Cycle Products, PhD thesis, University of the Western Cape, 2007.

[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, Handbook of Coding Theory, North-Holland, Amsterdam, 1, 2 (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, 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.

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

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

[17]

C. Kravvaritis, Determinant evaluations for binary circulant matrices, Spec. Matrices, 1 (2013), 187–199. http://dx.doi.org/10.2478/spma-2014-0019.

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

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

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

[21]

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

[22]

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

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]

Violetta Weger, Karan Khathuria, Anna-Lena Horlemann, Massimo Battaglioni, Paolo Santini, Edoardo Persichetti. On the hardness of the Lee syndrome decoding problem. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022029
[3]

Anna-Lena Horlemann-Trautmann, Violetta Weger. Information set decoding in the Lee metric with applications to cryptography. Advances in Mathematics of Communications, 2021, 15 (4) : 677-699. doi: 10.3934/amc.2020089
[4]

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

Xinmei Huang, Qin Yue, Yansheng Wu, Xiaoping Shi. Ternary Primitive LCD BCH codes. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021014
[6]

Zihui Liu. Galois LCD codes over rings. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022002
[7]

Ranya Djihad Boulanouar, Aicha Batoul, Delphine Boucher. An overview on skew constacyclic codes and their subclass of LCD codes. Advances in Mathematics of Communications, 2021, 15 (4) : 611-632. doi: 10.3934/amc.2020085
[8]

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

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

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

Keita Ishizuka, Ken Saito. Construction for both self-dual codes and LCD codes. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2021070
[12]

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

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

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

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

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

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

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

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

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

2021 Impact Factor: 1.015

Tools

Metrics

  • PDF downloads (335)
  • HTML views (615)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy