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]

Yunping Jiang. Global graph of metric entropy on expanding Blaschke products. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1469-1482. doi: 10.3934/dcds.2020325
[2]

Gökhan Mutlu. On the quotient quantum graph with respect to the regular representation. Communications on Pure & Applied Analysis, 2021, 20 (2) : 885-902. doi: 10.3934/cpaa.2020295
[3]

Vaibhav Mehandiratta, Mani Mehra, Günter Leugering. Fractional optimal control problems on a star graph: Optimality system and numerical solution. Mathematical Control & Related Fields, 2021, 11 (1) : 189-209. doi: 10.3934/mcrf.2020033
[4]

Xiangrui Meng, Jian Gao. Complete weight enumerator of torsion codes. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020124
[5]

Vaibhav Mehandiratta, Mani Mehra, Günter Leugering. Existence results and stability analysis for a nonlinear fractional boundary value problem on a circular ring with an attached edge : A study of fractional calculus on metric graph. Networks & Heterogeneous Media, 2021  doi: 10.3934/nhm.2021003
[6]

Agnaldo José Ferrari, Tatiana Miguel Rodrigues de Souza. Rotated $ A_n $-lattice codes of full diversity. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020118
[7]

Vito Napolitano, Ferdinando Zullo. Codes with few weights arising from linear sets. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020129
[8]

Dandan Wang, Xiwang Cao, Gaojun Luo. A class of linear codes and their complete weight enumerators. Advances in Mathematics of Communications, 2021, 15 (1) : 73-97. doi: 10.3934/amc.2020044
[9]

San Ling, Buket Özkaya. New bounds on the minimum distance of cyclic codes. Advances in Mathematics of Communications, 2021, 15 (1) : 1-8. doi: 10.3934/amc.2020038
[10]

Shudi Yang, Xiangli Kong, Xueying Shi. Complete weight enumerators of a class of linear codes over finite fields. Advances in Mathematics of Communications, 2021, 15 (1) : 99-112. doi: 10.3934/amc.2020045
[11]

Karan Khathuria, Joachim Rosenthal, Violetta Weger. Encryption scheme based on expanded Reed-Solomon codes. Advances in Mathematics of Communications, 2021, 15 (2) : 207-218. doi: 10.3934/amc.2020053
[12]

Nicola Pace, Angelo Sonnino. On the existence of PD-sets: Algorithms arising from automorphism groups of codes. Advances in Mathematics of Communications, 2021, 15 (2) : 267-277. doi: 10.3934/amc.2020065
[13]

Jong Yoon Hyun, Boran Kim, Minwon Na. Construction of minimal linear codes from multi-variable functions. Advances in Mathematics of Communications, 2021, 15 (2) : 227-240. doi: 10.3934/amc.2020055
[14]

Sabira El Khalfaoui, Gábor P. Nagy. On the dimension of the subfield subcodes of 1-point Hermitian codes. Advances in Mathematics of Communications, 2021, 15 (2) : 219-226. doi: 10.3934/amc.2020054
[15]

Shanding Xu, Longjiang Qu, Xiwang Cao. Three classes of partitioned difference families and their optimal constant composition codes. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020120
[16]

Fengwei Li, Qin Yue, Xiaoming Sun. The values of two classes of Gaussian periods in index 2 case and weight distributions of linear codes. Advances in Mathematics of Communications, 2021, 15 (1) : 131-153. doi: 10.3934/amc.2020049
[17]

Hongming Ru, Chunming Tang, Yanfeng Qi, Yuxiao Deng. A construction of $ p $-ary linear codes with two or three weights. Advances in Mathematics of Communications, 2021, 15 (1) : 9-22. doi: 10.3934/amc.2020039
[18]

Tingting Wu, Li Liu, Lanqiang Li, Shixin Zhu. Repeated-root constacyclic codes of length $ 6lp^s $. Advances in Mathematics of Communications, 2021, 15 (1) : 167-189. doi: 10.3934/amc.2020051
[19]

Saadoun Mahmoudi, Karim Samei. Codes over $ \frak m $-adic completion rings. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020122
[20]

Hongwei Liu, Jingge Liu. On $ \sigma $-self-orthogonal constacyclic codes over $ \mathbb F_{p^m}+u\mathbb F_{p^m} $. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020127

2019 Impact Factor: 0.734

Tools

Article outline

Figures and Tables

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences