Generating generalized necklaces and new quasi-cyclic codes
Keywords:
Finite field, Quasi-cyclic linear codes, Necklaces
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).
References
[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] N. Aydin, I. Siap, New quasi–cyclic codes over F5 , Appl. Math. Lett. 15 (2002) 833–836.
[3] N. Aydin, J. Murphree, New linear codes from constacyclic codes, J. Franklin Inst. 351(3) (2014) 1691–1699.
[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] 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] 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] 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] 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] E. Z. Chen, Database of Quasi–twisted codes, available at http://www.tec.hkr.se/chen/research/codes/
[10] E. Z. Chen, A new iterative computer search algorithm for good quasi–twisted codes,Des. Codes Cryptogr. 76(2) (2015) 307–323.
[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] E. Z. Chen, N. Aydin, New quasi–twisted codes over F11 minimum distance bounds and a new database, J. Inf. Optim. Sci. 36(1–2) (2015) 129–157.
[13] E. Z. Chen, N. Aydin, A database of linear codes over F13 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] R. Daskalov, E. Metodieva, The nonexistence of some 5–dimensional quaternary linear codes, IEEE Trans. Inform. Theory 41(2) (1995) 581–583.
[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] 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] 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] R. Daskalov, P. Hristov, Some new quasi–twisted ternary linear codes, J. Algebra Comb. Discrete Struct. Appl. 2(3) (2016) 211–216.
[19] R. Daskalov, P. Hristov, Some new ternary linear codes, J. Algebra Comb. Discrete Struct. Appl. 4(3) (2017) 227–234.
[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] R. Daskalov, E. Metodieva, The nonexistence of ternary [105,6,68] and [230,6,152] codes, Discrete Math. 286(3) (2004) 225–232.
[22] H. Fredricksen, J. Maiorana, Necklaces of beads in k colors and k–ary de Bruijn sequences, Discrete Math. 23 (1978) 207–210.
[23] H. Fredricksen, I. J. Kessler, An algorithm for generating necklaces of beads in two colors, Discrete Math. 61 (1986) 181–188.
[24] P. P. Greenough, R. Hill, Optimal ternary quasi–cyclic codes, Des. Codes Crypt. 2 (1992) 81–91.
[25] T. A. Gulliver, Quasi–twisted codes over F11, Ars Combinatoria 99 (2011) 3–17.
[26] T. A. Gulliver, Quasi–cyclic codes over F13, In Combinatorial Algorithms, Lecture Notes in Computer Science 7056 (2011) 236–246.
[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] M. Grassl, Bounds on the minimum distances of linear codes, available at http://www.codetables.de
[29] F. Ruskey, C. Savage, T. Wang, Generating necklaces, Journal of Algorithms 13 (1992) 414–430.
[30] A. Vardy, The intractability of computing the minimum distance of a code, IEEE Trans. Inform. Theory 43 (1997) 1757–1766.
[31] V. Venkaiah, T. A.Gulliver, Quasi–cyclic codes over F13 and enumeration of definining polynomials, Journal Discrete Algorithms 16 (2012) 249–257.
[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.
[2] N. Aydin, I. Siap, New quasi–cyclic codes over F5 , Appl. Math. Lett. 15 (2002) 833–836.
[3] N. Aydin, J. Murphree, New linear codes from constacyclic codes, J. Franklin Inst. 351(3) (2014) 1691–1699.
[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] 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] 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] 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] 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] E. Z. Chen, Database of Quasi–twisted codes, available at http://www.tec.hkr.se/chen/research/codes/
[10] E. Z. Chen, A new iterative computer search algorithm for good quasi–twisted codes,Des. Codes Cryptogr. 76(2) (2015) 307–323.
[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] E. Z. Chen, N. Aydin, New quasi–twisted codes over F11 minimum distance bounds and a new database, J. Inf. Optim. Sci. 36(1–2) (2015) 129–157.
[13] E. Z. Chen, N. Aydin, A database of linear codes over F13 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] R. Daskalov, E. Metodieva, The nonexistence of some 5–dimensional quaternary linear codes, IEEE Trans. Inform. Theory 41(2) (1995) 581–583.
[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] 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] 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] R. Daskalov, P. Hristov, Some new quasi–twisted ternary linear codes, J. Algebra Comb. Discrete Struct. Appl. 2(3) (2016) 211–216.
[19] R. Daskalov, P. Hristov, Some new ternary linear codes, J. Algebra Comb. Discrete Struct. Appl. 4(3) (2017) 227–234.
[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] R. Daskalov, E. Metodieva, The nonexistence of ternary [105,6,68] and [230,6,152] codes, Discrete Math. 286(3) (2004) 225–232.
[22] H. Fredricksen, J. Maiorana, Necklaces of beads in k colors and k–ary de Bruijn sequences, Discrete Math. 23 (1978) 207–210.
[23] H. Fredricksen, I. J. Kessler, An algorithm for generating necklaces of beads in two colors, Discrete Math. 61 (1986) 181–188.
[24] P. P. Greenough, R. Hill, Optimal ternary quasi–cyclic codes, Des. Codes Crypt. 2 (1992) 81–91.
[25] T. A. Gulliver, Quasi–twisted codes over F11, Ars Combinatoria 99 (2011) 3–17.
[26] T. A. Gulliver, Quasi–cyclic codes over F13, In Combinatorial Algorithms, Lecture Notes in Computer Science 7056 (2011) 236–246.
[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] M. Grassl, Bounds on the minimum distances of linear codes, available at http://www.codetables.de
[29] F. Ruskey, C. Savage, T. Wang, Generating necklaces, Journal of Algorithms 13 (1992) 414–430.
[30] A. Vardy, The intractability of computing the minimum distance of a code, IEEE Trans. Inform. Theory 43 (1997) 1757–1766.
[31] V. Venkaiah, T. A.Gulliver, Quasi–cyclic codes over F13 and enumeration of definining polynomials, Journal Discrete Algorithms 16 (2012) 249–257.
[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.
