# American Institute of Mathematical Sciences

February  2017, 11(1): 245-258. doi: 10.3934/amc.2017016

## Some results on the structure of constacyclic codes and new linear codes over GF(7) from quasi-twisted codes

 1 Department of Mathematics, Kenyon College, Gambier, OH 43022, USA 2 Max Planck Institute for the Science of Light, 91058 Erlangen, Germany

Received  October 2015 Published  February 2017

Fund Project: The work of the first two authors is supported by Kenyon College Summer Science Scholars program.

One of the most important and challenging problems in coding theory is to construct codes with good parameters. There are various methods to construct codes with the best possible parameters. A promising and fruitful approach has been to focus on the class of quasi-twisted (QT) codes which includes constacyclic codes as a special case. This class of codes is known to contain many codes with good parameters. Although constacyclic codes and QT codes have been the subject of numerous studies and computer searches over the last few decades, we have been able to discover a new fundamental result about the structure of constacyclic codes which was instrumental in our comprehensive search method for new QT codes over GF(7). We have been able to find 41 QT codes with better parameters than the previously best known linear codes. Furthermore, we derived a number of additional new codes via Construction X as well as standard constructions, such as shortening and puncturing.

Citation: Nuh Aydin, Nicholas Connolly, Markus Grassl. Some results on the structure of constacyclic codes and new linear codes over GF(7) from quasi-twisted codes. Advances in Mathematics of Communications, 2017, 11 (1) : 245-258. doi: 10.3934/amc.2017016
##### References:
 [1] R. Ackerman and N. Aydin, New quinary linear codes from quasi-twisted codes and their duals, Appl. Math. Lett., 24 (2011), 512-515.  doi: 10.1016/j.aml.2010.11.003.  Google Scholar [2] N. Aydin and J. M. Murphee, New linear codes from constacyclic codes, J. Franklin Inst., 351 (2014), 1691-1699.  doi: 10.1016/j.jfranklin.2013.11.019.  Google Scholar [3] N. Aydin and I. Siap, New quasi-cyclic codes over $\mathbb{F}_5$, Appl. Math. Lett., 15 (2002), 833-836.  doi: 10.1016/S0893-9659(02)00050-2.  Google Scholar [4] N. Aydin, I. Siap and D. K. Ray-Chaudhuri, The structure of 1-generator quasi-twisted codes and new linear codes, Des. Codes Crypt., 24 (2001), 313-326.  doi: 10.1023/A:1011283523000.  Google Scholar [5] T. S. Baicheva, On the covering radius of ternary negacyclic codes with length up to 26, IEEE Trans. Inform. Theory, 47 (2001), 413-416.  doi: 10.1109/18.904549.  Google Scholar [6] E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, New York, 1968.  Google Scholar [7] E. Chen and N. Aydin, A database of linear codes over $\mathbb{F}_13$ with minimum distance bounds and new quasi-twisted codes from a heuristic search algorithm, J. Algebra Combin. Discrete Struct. Appl., 2 (2015), 1-16.  doi: 10.13069/jacodesmath.36947.  Google Scholar [8] E. Chen and N. Aydin, New quasi-twisted codes over $\mathbb{F}_11$-minimum distance bounds and a new database, J. Inform. Optim. Sci., 36 (2015), 129-157.  doi: 10.1080/02522667.2014.961788.  Google Scholar [9] Z. Chen, Six new binary quasi-cyclic codes, IEEE Trans. Inform. Theory, 40 (1994), 1666-1667.  doi: 10.1109/18.333888.  Google Scholar [10] R. Daskalov and T. A. Gulliver, New quasi-twisted quaternary linear codes, IEEE Trans. Inform. Theory, 46 (2000), 2642-2643.  doi: 10.1109/18.887874.  Google Scholar [11] R. Daskalov and P. Hristov, New binary one-generator quasi-cyclic codes, IEEE Trans. Inform. Theory, 49 (2003), 3001-3005.  doi: 10.1109/TIT.2003.819337.  Google Scholar [12] R. Daskalov and P. Hristov, New quasi-twisted degenerate ternary linear codes, IEEE Trans. Inform. Theory, 49 (2003), 2259-2263.  doi: 10.1109/TIT.2003.815798.  Google Scholar [13] R. Daskalov, P. Hristov and E. Metodieva, New minimum distance bounds for linear codes over GF (5), Discrete Math., 275 (2004), 97-110.  doi: 10.1016/S0012-365X(03)00126-2.  Google Scholar [14] M. Grassl, Searching for linear codes with large minimum distance, in Discovering Mathematics with Magma -Reducing the Abstract to the Concrete Springer, Heidelberg, 2006,287-313. doi: 10.1007/978-3-540-37634-7_13.  Google Scholar [15] M. Grassl, Bounds on the minimum distance of linear codes and quantum codes, available at http://www.codetables.de, 2007. Google Scholar [16] M. Grassl and S. Han, Computing extensions of linear codes using a greedy algorithm, in Proc. 2012 IEEE Int. Symp. Inf. Theory (ISIT 2012), Cambridge, 2012,1568-1572. doi: 10.1109/ISIT.2012.6283537.  Google Scholar [17] M. Grassl and G. White, New good linear codes by special puncturings, in Proc. 2004 IEEE Int. Symp. Inf. Theory (ISIT 2004), Chicago, 2004,454. doi: 10.1109/ISIT.2004.1365491.  Google Scholar [18] M. Grassl and G. White, New codes from chains of quasi-cyclic codes, in Proc. 2005 IEEE Int. Symp. Inf. Theory (ISIT 2005), Adelaide, 2005,2095-2099. doi: 10.1109/ISIT.2005.1523715.  Google Scholar [19] T. A. Gulliver and V. K. Bhargava, New good rate (m -1)/pm ternary and quaternary quasi-cyclic codes, Des. Codes Crypt., 7 (1996), 223-233.  doi: 10.1007/BF00124513.  Google Scholar [20] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, NorthHolland, Amsterdam, 1977. Google Scholar [21] Magma computer algebra system web site, http://magma.maths.usyd.edu.au/. Google Scholar [22] E. Prange, Cyclic Error-Correcting Codes in Two Symbols, Technical Report TN-57-103, Air Force Cambridge Research Center, Cambridge, 1957. Google Scholar [23] E. Prange, Some Cyclic Error-Correcting Codes with Simple Decoding Algorithm, Technical Report TN-58-156, Air Force Cambridge Research Center, Cambridge, 1958. Google Scholar [24] A. Vardy, The intractability of computing the minimum distance of a code, IEEE Transactions on Information Theory, 43 (1997), 1757-1766.  doi: 10.1109/18.641542.  Google Scholar

show all references

##### References:
 [1] R. Ackerman and N. Aydin, New quinary linear codes from quasi-twisted codes and their duals, Appl. Math. Lett., 24 (2011), 512-515.  doi: 10.1016/j.aml.2010.11.003.  Google Scholar [2] N. Aydin and J. M. Murphee, New linear codes from constacyclic codes, J. Franklin Inst., 351 (2014), 1691-1699.  doi: 10.1016/j.jfranklin.2013.11.019.  Google Scholar [3] N. Aydin and I. Siap, New quasi-cyclic codes over $\mathbb{F}_5$, Appl. Math. Lett., 15 (2002), 833-836.  doi: 10.1016/S0893-9659(02)00050-2.  Google Scholar [4] N. Aydin, I. Siap and D. K. Ray-Chaudhuri, The structure of 1-generator quasi-twisted codes and new linear codes, Des. Codes Crypt., 24 (2001), 313-326.  doi: 10.1023/A:1011283523000.  Google Scholar [5] T. S. Baicheva, On the covering radius of ternary negacyclic codes with length up to 26, IEEE Trans. Inform. Theory, 47 (2001), 413-416.  doi: 10.1109/18.904549.  Google Scholar [6] E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, New York, 1968.  Google Scholar [7] E. Chen and N. Aydin, A database of linear codes over $\mathbb{F}_13$ with minimum distance bounds and new quasi-twisted codes from a heuristic search algorithm, J. Algebra Combin. Discrete Struct. Appl., 2 (2015), 1-16.  doi: 10.13069/jacodesmath.36947.  Google Scholar [8] E. Chen and N. Aydin, New quasi-twisted codes over $\mathbb{F}_11$-minimum distance bounds and a new database, J. Inform. Optim. Sci., 36 (2015), 129-157.  doi: 10.1080/02522667.2014.961788.  Google Scholar [9] Z. Chen, Six new binary quasi-cyclic codes, IEEE Trans. Inform. Theory, 40 (1994), 1666-1667.  doi: 10.1109/18.333888.  Google Scholar [10] R. Daskalov and T. A. Gulliver, New quasi-twisted quaternary linear codes, IEEE Trans. Inform. Theory, 46 (2000), 2642-2643.  doi: 10.1109/18.887874.  Google Scholar [11] R. Daskalov and P. Hristov, New binary one-generator quasi-cyclic codes, IEEE Trans. Inform. Theory, 49 (2003), 3001-3005.  doi: 10.1109/TIT.2003.819337.  Google Scholar [12] R. Daskalov and P. Hristov, New quasi-twisted degenerate ternary linear codes, IEEE Trans. Inform. Theory, 49 (2003), 2259-2263.  doi: 10.1109/TIT.2003.815798.  Google Scholar [13] R. Daskalov, P. Hristov and E. Metodieva, New minimum distance bounds for linear codes over GF (5), Discrete Math., 275 (2004), 97-110.  doi: 10.1016/S0012-365X(03)00126-2.  Google Scholar [14] M. Grassl, Searching for linear codes with large minimum distance, in Discovering Mathematics with Magma -Reducing the Abstract to the Concrete Springer, Heidelberg, 2006,287-313. doi: 10.1007/978-3-540-37634-7_13.  Google Scholar [15] M. Grassl, Bounds on the minimum distance of linear codes and quantum codes, available at http://www.codetables.de, 2007. Google Scholar [16] M. Grassl and S. Han, Computing extensions of linear codes using a greedy algorithm, in Proc. 2012 IEEE Int. Symp. Inf. Theory (ISIT 2012), Cambridge, 2012,1568-1572. doi: 10.1109/ISIT.2012.6283537.  Google Scholar [17] M. Grassl and G. White, New good linear codes by special puncturings, in Proc. 2004 IEEE Int. Symp. Inf. Theory (ISIT 2004), Chicago, 2004,454. doi: 10.1109/ISIT.2004.1365491.  Google Scholar [18] M. Grassl and G. White, New codes from chains of quasi-cyclic codes, in Proc. 2005 IEEE Int. Symp. Inf. Theory (ISIT 2005), Adelaide, 2005,2095-2099. doi: 10.1109/ISIT.2005.1523715.  Google Scholar [19] T. A. Gulliver and V. K. Bhargava, New good rate (m -1)/pm ternary and quaternary quasi-cyclic codes, Des. Codes Crypt., 7 (1996), 223-233.  doi: 10.1007/BF00124513.  Google Scholar [20] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, NorthHolland, Amsterdam, 1977. Google Scholar [21] Magma computer algebra system web site, http://magma.maths.usyd.edu.au/. Google Scholar [22] E. Prange, Cyclic Error-Correcting Codes in Two Symbols, Technical Report TN-57-103, Air Force Cambridge Research Center, Cambridge, 1957. Google Scholar [23] E. Prange, Some Cyclic Error-Correcting Codes with Simple Decoding Algorithm, Technical Report TN-58-156, Air Force Cambridge Research Center, Cambridge, 1958. Google Scholar [24] A. Vardy, The intractability of computing the minimum distance of a code, IEEE Transactions on Information Theory, 43 (1997), 1757-1766.  doi: 10.1109/18.641542.  Google Scholar
Shift constants $a$ and lengths $n$ of constacyclic codes to be examined for each finite field $q=3, 4, 5, 7, 8, 9, 11, 13$, where $\alpha\in GF(9)$ is a root of $x^2+2x+2$.
 $q$ $a\neq0, 1$ $n$ maximum $n$ 3 2 all $n=2m$ 243 4 any field element all $n=3m$ 256 5 2 all $n=2m$ 130 4 all $n=4m$ 7 2 all $n=3m$ 100 3 all $n=2m$ or $n=3m$ 6 all $n=2m$ 8 any field element all $n=7m$ 130 9 $\alpha$ all $n=2m$ 130 $\alpha^2$ all $n=4m$ $\alpha^4$ all $n=8m$ 11 2 all $n=2m$ or $n=5m$ 150 3 all $n=5m$ 10 all $n=2m$ 13 2 all $n=2m$ or $n=3m$ 150 3 all $n=3m$ 4 all $n=3m$ or $n=4m$ 5 all $n=2m$ 12 all $n=4m$
 $q$ $a\neq0, 1$ $n$ maximum $n$ 3 2 all $n=2m$ 243 4 any field element all $n=3m$ 256 5 2 all $n=2m$ 130 4 all $n=4m$ 7 2 all $n=3m$ 100 3 all $n=2m$ or $n=3m$ 6 all $n=2m$ 8 any field element all $n=7m$ 130 9 $\alpha$ all $n=2m$ 130 $\alpha^2$ all $n=4m$ $\alpha^4$ all $n=8m$ 11 2 all $n=2m$ or $n=5m$ 150 3 all $n=5m$ 10 all $n=2m$ 13 2 all $n=2m$ or $n=3m$ 150 3 all $n=3m$ 4 all $n=3m$ or $n=4m$ 5 all $n=2m$ 12 all $n=4m$
 [1] Ekkasit Sangwisut, Somphong Jitman, Patanee Udomkavanich. Constacyclic and quasi-twisted Hermitian self-dual codes over finite fields. Advances in Mathematics of Communications, 2017, 11 (3) : 595-613. doi: 10.3934/amc.2017045 [2] Alexis Eduardo Almendras Valdebenito, Andrea Luigi Tironi. On the dual codes of skew constacyclic codes. Advances in Mathematics of Communications, 2018, 12 (4) : 659-679. doi: 10.3934/amc.2018039 [3] T. Aaron Gulliver, Masaaki Harada, Hiroki Miyabayashi. Double circulant and quasi-twisted self-dual codes over $\mathbb F_5$ and $\mathbb F_7$. Advances in Mathematics of Communications, 2007, 1 (2) : 223-238. doi: 10.3934/amc.2007.1.223 [4] Fengwei Li, Qin Yue, Fengmei Liu. The weight distributions of constacyclic codes. Advances in Mathematics of Communications, 2017, 11 (3) : 471-480. doi: 10.3934/amc.2017039 [5] Ranya Djihad Boulanouar, Aicha Batoul, Delphine Boucher. An overview on skew constacyclic codes and their subclass of LCD codes. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020085 [6] Umberto Martínez-Peñas. Rank equivalent and rank degenerate skew cyclic codes. Advances in Mathematics of Communications, 2017, 11 (2) : 267-282. doi: 10.3934/amc.2017018 [7] Kamil Otal, Ferruh Özbudak, Wolfgang Willems. Self-duality of generalized twisted Gabidulin codes. Advances in Mathematics of Communications, 2018, 12 (4) : 707-721. doi: 10.3934/amc.2018042 [8] Aicha Batoul, Kenza Guenda, T. Aaron Gulliver. Some constacyclic codes over finite chain rings. Advances in Mathematics of Communications, 2016, 10 (4) : 683-694. doi: 10.3934/amc.2016034 [9] Somphong Jitman, San Ling, Patanee Udomkavanich. Skew constacyclic codes over finite chain rings. Advances in Mathematics of Communications, 2012, 6 (1) : 39-63. doi: 10.3934/amc.2012.6.39 [10] Anuradha Sharma, Saroj Rani. Trace description and Hamming weights of irreducible constacyclic codes. Advances in Mathematics of Communications, 2018, 12 (1) : 123-141. doi: 10.3934/amc.2018008 [11] Delphine Boucher, Patrick Solé, Felix Ulmer. Skew constacyclic codes over Galois rings. Advances in Mathematics of Communications, 2008, 2 (3) : 273-292. doi: 10.3934/amc.2008.2.273 [12] Olof Heden, Martin Hessler. On linear equivalence and Phelps codes. Advances in Mathematics of Communications, 2010, 4 (1) : 69-81. doi: 10.3934/amc.2010.4.69 [13] Petr Lisoněk, Layla Trummer. Algorithms for the minimum weight of linear codes. Advances in Mathematics of Communications, 2016, 10 (1) : 195-207. doi: 10.3934/amc.2016.10.195 [14] Jean Creignou, Hervé Diet. Linear programming bounds for unitary codes. Advances in Mathematics of Communications, 2010, 4 (3) : 323-344. doi: 10.3934/amc.2010.4.323 [15] Fernando Hernando, Tom Høholdt, Diego Ruano. List decoding of matrix-product codes from nested codes: An application to quasi-cyclic codes. Advances in Mathematics of Communications, 2012, 6 (3) : 259-272. doi: 10.3934/amc.2012.6.259 [16] Ettore Fornasini, Telma Pinho, Raquel Pinto, Paula Rocha. Composition codes. Advances in Mathematics of Communications, 2016, 10 (1) : 163-177. doi: 10.3934/amc.2016.10.163 [17] Fernando Hernando, Diego Ruano. New linear codes from matrix-product codes with polynomial units. Advances in Mathematics of Communications, 2010, 4 (3) : 363-367. doi: 10.3934/amc.2010.4.363 [18] Hai Q. Dinh, Hien D. T. Nguyen. On some classes of constacyclic codes over polynomial residue rings. Advances in Mathematics of Communications, 2012, 6 (2) : 175-191. doi: 10.3934/amc.2012.6.175 [19] Yan Liu, Minjia Shi, Hai Q. Dinh, Songsak Sriboonchitta. Repeated-root constacyclic codes of length $3\ell^mp^s$. Advances in Mathematics of Communications, 2020, 14 (2) : 359-378. doi: 10.3934/amc.2020025 [20] Michael Braun. On lattices, binary codes, and network codes. Advances in Mathematics of Communications, 2011, 5 (2) : 225-232. doi: 10.3934/amc.2011.5.225

2019 Impact Factor: 0.734