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

Nuh Aydin; Nicholas Connolly; Markus Grassl

doi:10.3934/amc.2017016

Article Contents

2017, Volume 11, Issue 1: 245-258. Doi: 10.3934/amc.2017016

This issue Previous Article On the arithmetic autocorrelation of the Legendre sequence Next Article 5-SEEDs from the lifted Golay code of length 24 over Z₄

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: September 30, 2015

Published: May 2017

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

Abstract Full Text(HTML) Figure(0) / Table(1) Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 94B65; Secondary: 11T71.

Citation:

Full Text(HTML)

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
5	4	all $n=4m$	130
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$

| Show Table

DownLoad: CSV

Related Papers

Cited by

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