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

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]

Vito Napolitano, Ferdinando Zullo. Codes with few weights arising from linear sets. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020129

[2]

Dandan Wang, Xiwang Cao, Gaojun Luo. A class of linear codes and their complete weight enumerators. Advances in Mathematics of Communications, 2021, 15 (1) : 73-97. doi: 10.3934/amc.2020044

[3]

Shudi Yang, Xiangli Kong, Xueying Shi. Complete weight enumerators of a class of linear codes over finite fields. Advances in Mathematics of Communications, 2021, 15 (1) : 99-112. doi: 10.3934/amc.2020045

[4]

Jong Yoon Hyun, Boran Kim, Minwon Na. Construction of minimal linear codes from multi-variable functions. Advances in Mathematics of Communications, 2021, 15 (2) : 227-240. doi: 10.3934/amc.2020055

[5]

Tingting Wu, Li Liu, Lanqiang Li, Shixin Zhu. Repeated-root constacyclic codes of length $ 6lp^s $. Advances in Mathematics of Communications, 2021, 15 (1) : 167-189. doi: 10.3934/amc.2020051

[6]

Xiangrui Meng, Jian Gao. Complete weight enumerator of torsion codes. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020124

[7]

Hongwei Liu, Jingge Liu. On $ \sigma $-self-orthogonal constacyclic codes over $ \mathbb F_{p^m}+u\mathbb F_{p^m} $. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020127

[8]

Fengwei Li, Qin Yue, Xiaoming Sun. The values of two classes of Gaussian periods in index 2 case and weight distributions of linear codes. Advances in Mathematics of Communications, 2021, 15 (1) : 131-153. doi: 10.3934/amc.2020049

[9]

Hongming Ru, Chunming Tang, Yanfeng Qi, Yuxiao Deng. A construction of $ p $-ary linear codes with two or three weights. Advances in Mathematics of Communications, 2021, 15 (1) : 9-22. doi: 10.3934/amc.2020039

[10]

Agnaldo José Ferrari, Tatiana Miguel Rodrigues de Souza. Rotated $ A_n $-lattice codes of full diversity. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020118

[11]

San Ling, Buket Özkaya. New bounds on the minimum distance of cyclic codes. Advances in Mathematics of Communications, 2021, 15 (1) : 1-8. doi: 10.3934/amc.2020038

[12]

Hai Q. Dinh, Bac T. Nguyen, Paravee Maneejuk. Constacyclic codes of length $ 8p^s $ over $ \mathbb F_{p^m} + u\mathbb F_{p^m} $. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020123

[13]

Karan Khathuria, Joachim Rosenthal, Violetta Weger. Encryption scheme based on expanded Reed-Solomon codes. Advances in Mathematics of Communications, 2021, 15 (2) : 207-218. doi: 10.3934/amc.2020053

[14]

Nicola Pace, Angelo Sonnino. On the existence of PD-sets: Algorithms arising from automorphism groups of codes. Advances in Mathematics of Communications, 2021, 15 (2) : 267-277. doi: 10.3934/amc.2020065

[15]

Sabira El Khalfaoui, Gábor P. Nagy. On the dimension of the subfield subcodes of 1-point Hermitian codes. Advances in Mathematics of Communications, 2021, 15 (2) : 219-226. doi: 10.3934/amc.2020054

[16]

Shanding Xu, Longjiang Qu, Xiwang Cao. Three classes of partitioned difference families and their optimal constant composition codes. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020120

[17]

Saadoun Mahmoudi, Karim Samei. Codes over $ \frak m $-adic completion rings. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020122

[18]

Ivan Bailera, Joaquim Borges, Josep Rifà. On Hadamard full propelinear codes with associated group $ C_{2t}\times C_2 $. Advances in Mathematics of Communications, 2021, 15 (1) : 35-54. doi: 10.3934/amc.2020041

[19]

Yuan Cao, Yonglin Cao, Hai Q. Dinh, Ramakrishna Bandi, Fang-Wei Fu. An explicit representation and enumeration for negacyclic codes of length $ 2^kn $ over $ \mathbb{Z}_4+u\mathbb{Z}_4 $. Advances in Mathematics of Communications, 2021, 15 (2) : 291-309. doi: 10.3934/amc.2020067

[20]

François Dubois. Third order equivalent equation of lattice Boltzmann scheme. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 221-248. doi: 10.3934/dcds.2009.23.221

2019 Impact Factor: 0.734

Metrics

  • PDF downloads (66)
  • HTML views (62)
  • Cited by (6)

Other articles
by authors

[Back to Top]