Binary self-dual and LCD codes from generator matrices constructed from two group ring elements by a heuristic search scheme

Steven Dougherty; Adrian Korban; Serap Șahinkaya; Deniz Ustun

doi:10.3934/amc.2022036

Article Contents

2024, Volume 18, Issue 4: 922-934. Doi: 10.3934/amc.2022036

This issue Previous Article Differential faultt attack on DEFAULT Next Article Loops, multi-edges and collisions in supersingular isogeny graphs

Binary self-dual and LCD codes from generator matrices constructed from two group ring elements by a heuristic search scheme

1.
University of Scranton, Department of Physical, Mathematical and Engineering Sciences, Scranton, PA, 18518, USA
2.
University of Chester, Department of Physical, Mathematical and Engineering Sciences University of Chester, England
3.
Tarsus University, Faculty of Engineering, Department of Natural and Mathematical Sciences, Turkey
4.
Tarsus University, Faculty of Engineering, Department of Computer Engineering, Turkey

^*Corresponding author: Serap Șahinkaya
^*Corresponding author: Serap Șahinkaya

Received: January 2022

Revised: April 2022

Early access: May 2022

Published: August 2024

The third author is supported by TUBITAK grant no: 1059B192000947

Abstract / Introduction Full Text(HTML) Figure(0) / Table(2) Related Papers Cited by

Abstract

We present a generator matrix of the form $ [ \sigma(v_1) \ | \ \sigma(v_2)] $, where $ v_1 \in RG $ and $ v_2\in RH $, for finite groups $ G $ and $ H $ of order $ n $ for constructing self-dual codes and linear complementary dual codes over the finite Frobenius ring $ R $. In general, many of the constructions to produce self-dual codes forces the code to be an ideal in a group ring which implies that the code has a rich automorphism group. Unlike the traditional cases, codes constructed from the generator matrix presented here are not ideals in a group ring, which enables us to find self-dual and linear complementary dual codes that are not found using more traditional techniques. In addition to that, by using this construction, we improve $ 10 $ of the previously known lower bounds on the largest minimum weights of binary linear complementary dual codes for some lengths and dimensions. We also obtain $ 82 $ new binary linear complementary dual codes, $ 50 $ of which are either optimal or near optimal of lengths $ 41 \leq n \leq 61 $ which are new to the literature.

Keywords:

Mathematics Subject Classification: Primary: 94B05; Secondary: 94B15.

Citation:

Full Text(HTML)

Table 1. New Binary Type Ⅰ Codes of Length 72

	Generator Matrix	Type	$ \gamma $	$ \beta $	$ \|Aut(C_i)\| $
$ C_{1} $	$ \mathcal{G}_{1} $	$ W_{72, 1} $	$ 2 $	$ 226 $	$ 1 $
$ C_{2} $	$ \mathcal{G}_{1} $	$ W_{72, 1} $	$ 4 $	$ 230 $	$ 1 $
$ C_{3} $	$ \mathcal{G}_{2} $	$ W_{72, 1} $	$ 14 $	$ 248 $	$ 1 $
$ C_{4} $	$ \mathcal{G}_{2} $	$ W_{72, 1} $	$ 1 $	$ 184 $	$ 1 $
$ C_{5} $	$ \mathcal{G}_{3} $	$ W_{72, 1} $	$ 10 $	$ 318 $	$ 4 $
$ C_{6} $	$ \mathcal{G}_{3} $	$ W_{72, 1} $	$ 4 $	$ 217 $	$ 4 $
$ C_{7} $	$ \mathcal{G}_{4} $	$ W_{72, 1} $	$ 12 $	$ 315 $	$ 6 $
$ C_{8} $	$ \mathcal{G}_{4} $	$ W_{72, 1} $	$ 6 $	$ 295 $	$ 12 $
$ C_{9} $	$ \mathcal{G}_{5} $	$ W_{72, 1} $	$ 2 $	$ 229 $	$ 2 $
$ C_{10} $	$ \mathcal{G}_{5} $	$ W_{72, 1} $	$ 14 $	$ 267 $	$ 2 $
$ C_{11} $	$ \mathcal{G}_{6} $	$ W_{72, 1} $	$ 2 $	$ 225 $	$ 2 $
$ C_{12} $	$ \mathcal{G}_{6} $	$ W_{72, 1} $	$ 4 $	$ 281 $	$ 4 $
$ C_{13} $	$ \mathcal{G}_{6} $	$ W_{72, 1} $	$ 4 $	$ 236 $	$ 4 $
$ C_{14} $	$ \mathcal{G}_{7} $	$ W_{72, 1} $	$ 18 $	$ 297 $	$ 18 $

| Show Table

DownLoad: CSV

Table 2. LCD Codes, where $ 41 \leq n \leq 61 $ and $ 15 \leq k \leq 30 $

Generator Matrix	$ [n, k, d] $	Optimal/Near Optimal	Generator Matrix	$ [n, k, d] $	Optimal/Near Optimal
$ \mathcal{G}_8 $	$ [30, 15, 7] $	Near Optimal	$ \mathcal{G}_8 $	$ [32, 16, 8] $	Optimal
Extended $ \mathcal{G}_8 $	$ [33, 16, 8] $	Optimal	Punctered $ \mathcal{G}_8 $	$ [31, 16, 7] $	Near Optimal
Shortened $ \mathcal{G}_8 $	$ [31, 15, 8] $	Optimal	$ \mathcal{G}_8 $	$ [34, 17, 8] $	Optimal
Punctered $ \mathcal{G}_8 $	$ [33, 17, 7] $	Near Optimal	Shortened $ \mathcal{G}_8 $	$ [33, 16, 8] $	Optimal
$ \mathcal{G}_8 $	$ [36, 18, 8] $	Optimal	Shortened $ \mathcal{G}_8 $	$ [35, 17, 8] $	Optimal
Extended $ \mathcal{G}_8 $	$ [41, 16, 10] $	$ - $	$ \mathcal{G}_8 $	$ [42, 18, 10] $	-
Extended $ \mathcal{G}_8 $	$ [43, 18, 10] $	$ - $	Punctered $ \mathcal{G}_8 $	$ [41, 18, 9] $	-
$ \mathcal{G}_8 $	$ [42, 20, 10] $	Optimal	Extended $ \mathcal{G}_8 $	$ [43, 20, 10] $	Near Optimal
Punctered $ \mathcal{G}_8 $	$ [41, 20, 9] $	Near Optimal	$ \mathcal{G}_8 $	$ [42, 19, 9] $	-
Punctered $ \mathcal{G}_8 $	$ [41, 19, 8] $	-	$ \mathcal{G}_8 $	$ [42, 21, 9] $	Near Optimal
Punctered $ \mathcal{G}_8 $	$ [41, 21, 8] $	Near Optimal	$ \mathcal{G}_8 $	$ [44, 20, 10] $	-
Extended $ \mathcal{G}_8 $	$ [45, 20, 10] $	-	Punctered $ \mathcal{G}_8 $	$ [43, 20, 9] $	-
$ \mathcal{G}_8 $	$ [44, 22, 9] $	Near Optimal	Extended $ \mathcal{G}_8 $	$ [45, 22, 10] $	Near Optimal
Punctered $ \mathcal{G}_8 $	$ [43, 22, 8] $	Near Optimal	Shortened $ \mathcal{G}_8 $	$ [43, 21, 9] $	Near Optimal
$ \mathcal{G}_9 $	$ [46, 22, 10] $	-	Extended $ \mathcal{G}_8 $	$ [47, 22, 10] $	-
Punctered $ \mathcal{G}_8 $	$ [45, 22, 9] $	-	$ \mathcal{G}_8 $	$ [46, 23, 9] $	-
Punctered $ \mathcal{G}_8 $	$ [45, 23, 8] $	-	$ \mathcal{G}_8 $	$ [48, 24, 9] $	-
Extended $ \mathcal{G}_8 $	$ [49, 24, 10] $	-	Punctered $ \mathcal{G}_8 $	$ [47, 24, 8] $	-
Shortened $ \mathcal{G}_8 $	$ [47, 23, 9] $	-	$ \mathcal{G}_8 $	$ [50, 21, 12] $	Optimal
Punctered $ \mathcal{G}_8 $	$ [49, 21, 11] $	Optimal	Shortened $ \mathcal{G}_8 $	$ [49, 20, 12] $	Optimal
$ \mathcal{G}_8 $	$ [50, 24, 10] $	-	Extended $ \mathcal{G}_8 $	$ [51, 24, 10] $	-
Punctered $ \mathcal{G}_8 $	$ [49, 24, 9] $	-	$ \mathcal{G}_8 $	$ [50, 25, 10] $	Optimal
Punctered $ \mathcal{G}_8 $	$ [49, 25, 9] $	Near Optimal	Shortened $ \mathcal{G}_8 $	$ [49, 24, 10] $	-
$ \mathcal{G}_8 $	$ [52, 24, 12] $	Optimal	Extended $ \mathcal{G}_8 $	$ [53, 24, 12] $	Optimal
Punctered $ \mathcal{G}_8 $	$ [51, 24, 11] $	Optimal	$ \mathcal{G}_8 $	$ [52, 26, 10] $	Optimal
Extended $ \mathcal{G}_8 $	$ [53, 26, 10] $	Near Optimal	Punctered $ \mathcal{G}_9 $	$ [51, 26, 9] $	Near Optimal
Shortened $ \mathcal{G}_8 $	$ [51, 25, 10] $	Near Optimal	$ \mathcal{G}_8 $	$ [54, 26, 12] $	Optimal
Extended $ \mathcal{G}_8 $	$ [55, 26, 12] $	Optimal	Punctered $ \mathcal{G}_8 $	$ [53, 26, 11] $	Optimal
$ \mathcal{G}_8 $	$ [54, 24, 12] $	Optimal	Extended $ \mathcal{G}_8 $	$ [55, 24, 12] $	Optimal
Punctered $ \mathcal{G}_8 $	$ [53, 24, 11] $	Near Optimal	$ \mathcal{G}_8 $	$ [54, 25, 11] $	Near Optimal
Punctered $ \mathcal{G}_8 $	$ [53, 25, 10] $	-	Shortened $ \mathcal{G}_8 $	$ [53, 24, 11] $	Near Optimal
$ \mathcal{G}_8 $	$ [54, 27, 10] $	Near Optimal	Punctered $ \mathcal{G}_8 $	$ [53, 27, 9] $	Near Optimal
Shortened $ \mathcal{G}_8 $	$ [53, 26, 10] $	Near Optimal	$ \mathcal{G}_8 $	$ [56, 24, 12] $	Optimal
Extended $ \mathcal{G}_8 $	$ [57, 24, 12] $	Near Optimal	Punctered $ \mathcal{G}_8 $	$ [55, 24, 11] $	Near Optimal
$ \mathcal{G}_8 $	$ [56, 28, 11] $	Near Optimal	Extended $ \mathcal{G}_8 $	$ [57, 28, 12] $	Optimal
Punctered $ \mathcal{G}_8 $	$ [55, 28, 10] $	Near Optimal	Shortened $ \mathcal{G}_8 $	$ [55, 27, 11] $	Near Optimal
$ \mathcal{G}_8 $	$ [58, 28, 12] $	Optimal	Extended $ \mathcal{G}_8 $	$ [59, 28, 12] $	Optimal
Punctered $ \mathcal{G}_8 $	$ [57, 28, 11] $	Optimal	$ \mathcal{G}_8 $	$ [58, 29, 11] $	Near Optimal
Punctered $ \mathcal{G}_8 $	$ [57, 29, 10] $	-	Shortened $ \mathcal{G}_8 $	$ [57, 28, 11] $	Near Optimal
$ \mathcal{G}_8 $	$ [60, 28, 12] $	Optimal	Extended $ \mathcal{G}_8 $	$ [61, 28, 12] $	Near Optimal
Punctered $ \mathcal{G}_8 $	$ [59, 28, 11] $	Near Optimal	$ \mathcal{G}_8 $	$ [60, 30, 11] $	Near Optimal
Extended $ \mathcal{G}_8 $	$ [61, 30, 12] $	Optimal	Punctured $ \mathcal{G}_8 $	$ [59, 30, 10] $	-
Shortened $ \mathcal{G}_8 $	$ [59, 29, 11] $	Near Optimal	$ \mathcal{G}_8 $	$ [60, 26, 11] $	-
Extended $ \mathcal{G}_8 $	$ [61, 26, 12] $	-	Punctered $ \mathcal{G}_8 $	$ [59, 26, 10] $	-
Shortened $ \mathcal{G}_8 $	$ [59, 25, 11] $	-	$ \mathcal{G}_9 $	$ [60, 24, 10] $	-
Extended $ \mathcal{G}_9 $	$ [61, 24, 10] $	-	Punctered $ \mathcal{G}_9 $	$ [59, 24, 10] $	-

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	M. Araya and M. Harada, On the minimum weights of binary linear complementary dual codes, Cryptogr. Commun., 12 (2020), 285-300. doi: 10.1007/s12095-019-00402-5.
[2]	M. Araya, M. Harada and K. Saito, Characterization and classification of optimal LCD codes, Des. Codes Cryptogr., 89 (2021), 617-640. doi: 10.1007/s10623-020-00834-8.
[3]	W. Bosma, J. Cannon and C. Playoust, The Magma algebra system. Ⅰ. The user language, J. Symbolic Comput., 24 (1997), 235-265. doi: 10.1006/jsco.1996.0125.
[4]	S. Bouyuklieva, Optimal binary LCD codes, Des. Codes Cryptogr., 89 (2021), 2445-2461. doi: 10.1007/s10623-021-00929-w.
[5]	R. Dontcheva, New binary self-dual $[70, 35, 12]$ and binary $[72, 36, 12]$ self-dual doubly-even codes, Serdica Math. J., 27 (2022), 287-302.
[6]	S. T. Dougherty, Algebraic Coding Theory over Finite Commutative Rings, SpringerBriefs in Mathematics, Springer, Cham, 2017. doi: 10.1007/978-3-319-59806-2.
[7]	S. T. Dougherty, J. Gildea and A. Kaya, $2^n$ Bordered constructions of self-dual codes from group rings, Finite Fields Appl., 67 (2020), 101692, 17 pp. doi: 10.1016/j.ffa.2020.101692.
[8]	S. T. Dougherty, J. Gildea, A. Kaya, A. Korban, A. Tylyshchak and B. Yildiz, Bordered constructions of self-dual codes from group rings and new extremal binary self-dual codes, Finite Fields Appl., 57 (2019), 108-127. doi: 10.1016/j.ffa.2019.02.004.
[9]	S. T. Dougherty, J. Gildea, A. Kaya and B. Yildiz, New self-dual and formally self-dual codes from group ring constructions, Adv. Math. Commun., 14 (2020), 11-22. doi: 10.3934/amc.2020002.
[10]	S. T. Dougherty, J. Gildea and A. Korban, Extending an established isomorphism between group rings and a subring of the $n \times n$ matrices, Internat. J. Algebra Comput., 31 (2021), 471-490. doi: 10.1142/S0218196721500223.
[11]	S. T. Dougherty, J. Gildea, A. Korban and A. Kaya, Composite matrices from group rings, composite $G$-codes and constructions of self-dual codes, Des. Codes Cryptogr., 89 (2021), 1615-1638. doi: 10.1007/s10623-021-00882-8.
[12]	S. T. Dougherty, J. Gildea, R. Taylor and A. Tylshchak, Group rings, $G$-codes and constructions of self-dual and formally self-dual codes, Des. Codes and Cryptog., 86 (2018), 2115-2138. doi: 10.1007/s10623-017-0440-7.
[13]	S. T. Dougherty, T. A. Gulliver and M. Harada, Extremal binary self dual codes, IEEE Trans. Inform. Theory, 43 (1997), 2036-2047. doi: 10.1109/18.641574.
[14]	S. T. Dougherty, J. L. Kim, B. Ozkaya, L. Sok and P. Sole, The combinatorics of LCD codes: Linear programming bound and orthogonal matrices, Int. J. Inf. Coding Theory, 4 (2017), 116-128. doi: 10.1504/IJICOT.2017.083827.
[15]	S. T. Dougherty, J.-L. Kim and P. Sole, Double circulant codes from two class association schemes, Adv. Math. of Commun., 1 (2007), 45-64. doi: 10.3934/amc.2007.1.45.
[16]	S. T. Dougherty, A. Korban, S. Sahinkaya and D. Ustun, Group matrix ring codes and constructions of self-dual codes, Appl. Algebra Engrg. Comm. Comput., (2021), https://doi.org/10.1007/s00200-021-00504-9.
[17]	L. Galvez, J.-L. Kim, N. Lee, Y. G. Roe and B.-S. Won, Some bounds on binary LCD codes, Cryptogr. Commun., 10 (2018), 719-728. doi: 10.1007/s12095-017-0258-1.
[18]	J. Gildea, A. Kaya, R. Taylor and B. Yildiz, Constructions for self-dual codes induced from group rings, Finite Fields Appl., 51 (2018), 71-92. doi: 10.1016/j.ffa.2018.01.002.
[19]	J. Gildea, A. Korban, A. Kaya and B. Yildiz, Constructing self-dual codes from group rings and reverse circulant matrices, Adv. in Math. Commun., 15 (2021), 471-485. doi: 10.3934/amc.2020077.
[20]	M. Grassl, Bounds on the minimum distance of linear codes and quantum codes, (2022), http://www.codetables.de.
[21]	T. A. Gulliver and M. Harada, On double circulant doubly-even self-dual $[72, 36, 12]$ codes and their neighbors, Austalas. J. Comb., 40 (2008), 137-144.
[22]	K. Ishizuka, K. Saito, Construction for both self-dual codes and LCD codes, arXiv: 2108.12544.
[23]	A. Korban, All known Type Ⅰ and Type Ⅱ $[72, 36, 12]$ binary self-dual codes, available online at https://sites.google.com/view/adriankorban/binary-self-dual-codes.
[24]	A. Korban, S. Sahinkaya and D. Ustun, A novel genetic search scheme based on nature-inspired evolutionary algorithms for self-dual codes, Adv. Math. Commun..
[25]	J. L. Massey, Linear codes with complementary duals, Discrete Math., 106/107 (1992), 337-342. doi: 10.1016/0012-365X(92)90563-U.
[26]	E. M. Rains and N. J. A. Sloane, The shadow theory of modular and unimodular lattices, J. Number Theory, 73 (1998), 359-389. doi: 10.1006/jnth.1998.2306.
[27]	S. Sahinkaya, available online at https://sites.google.com/view/serap-sahinkaya/generator-matrices.