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.

[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.

[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.

[4]

N. AydinI. 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.

[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.

[6]

E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, New York, 1968.

[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.

[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.

[9]

Z. Chen, Six new binary quasi-cyclic codes, IEEE Trans. Inform. Theory, 40 (1994), 1666-1667. doi: 10.1109/18.333888.

[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.

[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.

[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.

[13]

R. DaskalovP. 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.

[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.

[15]

M. Grassl, Bounds on the minimum distance of linear codes and quantum codes, available at http://www.codetables.de, 2007.

[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.

[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.

[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.

[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.

[20]

F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, NorthHolland, Amsterdam, 1977.

[21]

Magma computer algebra system web site, http://magma.maths.usyd.edu.au/.

[22]

E. Prange, Cyclic Error-Correcting Codes in Two Symbols, Technical Report TN-57-103, Air Force Cambridge Research Center, Cambridge, 1957.

[23]

E. Prange, Some Cyclic Error-Correcting Codes with Simple Decoding Algorithm, Technical Report TN-58-156, Air Force Cambridge Research Center, Cambridge, 1958.

[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.

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.

[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.

[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.

[4]

N. AydinI. 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.

[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.

[6]

E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, New York, 1968.

[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.

[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.

[9]

Z. Chen, Six new binary quasi-cyclic codes, IEEE Trans. Inform. Theory, 40 (1994), 1666-1667. doi: 10.1109/18.333888.

[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.

[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.

[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.

[13]

R. DaskalovP. 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.

[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.

[15]

M. Grassl, Bounds on the minimum distance of linear codes and quantum codes, available at http://www.codetables.de, 2007.

[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.

[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.

[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.

[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.

[20]

F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, NorthHolland, Amsterdam, 1977.

[21]

Magma computer algebra system web site, http://magma.maths.usyd.edu.au/.

[22]

E. Prange, Cyclic Error-Correcting Codes in Two Symbols, Technical Report TN-57-103, Air Force Cambridge Research Center, Cambridge, 1957.

[23]

E. Prange, Some Cyclic Error-Correcting Codes with Simple Decoding Algorithm, Technical Report TN-58-156, Air Force Cambridge Research Center, Cambridge, 1958.

[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.

Table 1.  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]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

Kamil Otal, Ferruh Özbudak, Wofgang Willems. Self-duality of generalized twisted Gabidulin codes. Advances in Mathematics of Communications, 2018, 12 (4) : 707-721. doi: 10.3934/amc.2018042

[11]

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

[12]

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

[13]

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

[14]

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

[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]

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

[17]

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

[18]

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

[19]

Nigel Boston, Jing Hao. The weight distribution of quasi-quadratic residue codes. Advances in Mathematics of Communications, 2018, 12 (2) : 363-385. doi: 10.3934/amc.2018023

[20]

John Sheekey. A new family of linear maximum rank distance codes. Advances in Mathematics of Communications, 2016, 10 (3) : 475-488. doi: 10.3934/amc.2016019

2017 Impact Factor: 0.564

Metrics

  • PDF downloads (5)
  • HTML views (16)
  • Cited by (1)

Other articles
by authors

[Back to Top]