Generating generalized necklaces and new quasi-cyclic codes

Abstract

In many cases there is a need of exhaustive lists of combinatorial objects of a given type. We consider generation of all inequivalent polynomials from which defining polynomials for constructing quasi-cyclic (QC) codes are to be chosen. Using these defining polynomials we construct 34 new good QC codes over GF(11) and 36 such codes over GF(13). In many cases there is a need of exhaustive lists of combinatorial objects of a given type. We consider generation of all inequivalent polynomials from which defining polynomials for constructing quasi-cyclic (QC) codes are to be chosen. Using these defining polynomials we construct 34 new good QC codes over GF(11) and 36 such codes over GF(13).

Keywords

• Finite field
• Quasi-cyclic linear codes
• Necklaces

References

1. [1] N. Aydin, I. Siap, D. K. Ray–Chaudhuri, The structure of 1–generator quasi–twisted codes and new linear codes, Des. Codes Cryptogr. 24 (2001) 313–326.
2. [2] N. Aydin, I. Siap, New quasi–cyclic codes over F$_{5}$, Appl. Math. Lett. 15 (2002) 833–836.
3. [3] N. Aydin, J. Murphree, New linear codes from constacyclic codes, J. Franklin Inst. 351(3) (2014) 1691–1699.
4. [4] N. Aydin, N. Connolly, M. Grassl, Some results on the structure of constacyclic codes and new linear codes over GF(7) from QT codes, Adv. Math. Commun. 11(1) (2017) 245–258.
5. [5] N. Aydin, N. Connolly, J. Murphree, New binary linear codes from quasi–cyclic codes and an augmentation algorithm, Appl. Algebra Engrg. Comm. Comput. 28(4) (2017) 339–350.
6. [6] N. Aydin,J. Lambrinos, O. VandenBerg, On equivalence of cyclic codes, generalization of a quasi– twisted search algorithm, and new linear codes, Des. Codes Cryptogr. 87 (2019) 2199–2212.
7. [7] N. Aydin, D. Foret, New linear codes over GF(3), GF(11) and GF(13), J. Algebra Comb. Discrete Struct. Appl. 6(1) (2019) 13–20.
8. [8] S. Ball, Table of bounds on three dimensional linear codes or $(n, r)$ Arcs in PG(2, q), available at https://web.mat.upc.edu/simeon.michael.ball/codebounds.html

9. [9] E. Z. Chen, Database of Quasi–twisted codes, available at http://www.tec.hkr.se/chen/research/codes/
10. [10] E. Z. Chen, A new iterative computer search algorithm for good quasi–twisted codes,Des. Codes Cryptogr. 76(2) (2015) 307–323.
11. [11] E. Z. Chen, Some new binary linear codes with improved minimum distances, J. Algebra Comb. Discrete Struct. Appl. 5(2) (2018) 65–70.
12. [12] E. Z. Chen, N. Aydin, New quasi–twisted codes over F$_{11}$ minimum distance bounds and a new database, J. Inf. Optim. Sci. 36(1–2) (2015) 129–157.
13. [13] E. Z. Chen, N. Aydin, A database of linear codes over F$_{13}$ with minimum distance bounds and new quasi–twisted codes from a heuristic search algorithm, J. Algebra Comb. Discrete Struct. Appl. 2(1) (2015) 1–16.
14. [14] R. Daskalov, E. Metodieva, The nonexistence of some 5–dimensional quaternary linear codes, IEEE Trans. Inform. Theory 41(2) (1995) 581–583.
15. [15] R. N. Daskalov, T. A. Gulliver, New good quasi–cyclic ternary and quaternary linear codes, IEEE Trans. Inform. Theory 43 (1997) 1647–1650.
16. [16] R. Daskalov, T. A. Gulliver, Bounds on Minimum Distance for Linear Codes over GF(5), Appl. Algebra Engrg. Comm. Comput. 9(6) (1999) 547–558.
17. [17] R. Daskalov, P. Hristov, New one–enerator quasi–cyclic codes over GF(7), Problemi Peredachi Informatsii 38(1) (2002) 59–63. English translation: Probl. Inf. Transm. 38(1) (2002) 50–54.
18. [18] R. Daskalov, P. Hristov, Some new quasi–twisted ternary linear codes, J. Algebra Comb. Discrete Struct. Appl. 2(3) (2016) 211–216.
19. [19] R. Daskalov, P. Hristov, Some new ternary linear codes, J. Algebra Comb. Discrete Struct. Appl. 4(3) (2017) 227–234.
20. [20] R. Daskalov, P. Hristov, E. Metodieva, New minimum distance bounds for linear codes over GF(5), Discrete Math. 275(1–3) (2004) 97–110.
21. [21] R. Daskalov, E. Metodieva, The nonexistence of ternary [105,6,68] and [230,6,152] codes, Discrete Math. 286(3) (2004) 225–232.
22. [22] H. Fredricksen, J. Maiorana, Necklaces of beads in k colors and k–ary de Bruijn sequences, Discrete Math. 23 (1978) 207–210.
23. [23] H. Fredricksen, I. J. Kessler, An algorithm for generating necklaces of beads in two colors, Discrete Math. 61 (1986) 181–188.
24. [24] P. P. Greenough, R. Hill, Optimal ternary quasi–cyclic codes, Des. Codes Crypt. 2 (1992) 81–91.
25. [25] T. A. Gulliver, Quasi–twisted codes over F$_{11}$ , Ars Combinatoria 99 (2011) 3–17.
26. [26] T. A. Gulliver, Quasi–cyclic codes over F$_{13}$ , In Combinatorial Algorithms, Lecture Notes in Computer Science 7056 (2011) 236–246.
27. [27] T. A. Gulliver, P. R. J. Ostergard, Improved bounds for ternary linear codes of dimension 7, IEEE Trans. Inform. Theory 43 (1997) 1377–1388.
28. [28] M. Grassl, Bounds on the minimum distances of linear codes, available at http://www.codetables.de
29. [29] F. Ruskey, C. Savage, T. Wang, Generating necklaces, Journal of Algorithms 13 (1992) 414–430.
30. [30] A. Vardy, The intractability of computing the minimum distance of a code, IEEE Trans. Inform. Theory 43 (1997) 1757–1766.
31. [31] V. Venkaiah, T. A.Gulliver, Quasi–cyclic codes over F13 and enumeration of definining polynomials, Journal Discrete Algorithms 16 (2012) 249–257.
32. [32] T. A. Gulliver, V. Venkaiah, Construction of quasi–twisted codes and enumeration of definining polynomials, J. Algebra Comb. Discrete Struct. Appl. 7(1) (2020) 3–20.