A database of linear codes over $\mathbb{F}_{13}$ with minimum distance bounds and new quasi-twisted codes from a heuristic search algorithm
DOI:
https://doi.org/10.13069/jacodesmath.36947Keywords:
Database of linear codes, Quasi-twisted codes, Heuristic search algorithm, Iterative searchAbstract
Error control codes have been widely used in data communications and storage systems. One central problem in coding theory is to optimize the parameters of a linear code and construct codes with best possible parameters. There are tables of best-known linear codes over finite fields of sizes up to 9. Recently, there has been a growing interest in codes over $\mathbb{F}_{13}$ and other fields of size greater than 9. The main purpose of this work is to present a database of best-known linear codes over the field $\mathbb{F}_{13}$ together with upper bounds on the minimum distances. To find good linear codes to establish lower bounds on minimum distances, an iterative heuristic computer search algorithm is employed to construct quasi-twisted (QT) codes over the field $\mathbb{F}_{13}$ with high minimum distances. A large number of new linear codes have been found, improving previously best-known results. Tables of $[pm, m]$ QT codes over $\mathbb{F}_{13}$ with best-known minimum distances as well as a table of lower and upper bounds on the minimum distances for linear codes of length up to 150 and dimension up to 6 are presented.
Received: 23 July 2014 | Accepted: 11 September 2014
Downloads
References
F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, Amsterdam (1977).
C. L. Chen and W. W. Peterson, Some results on quasi-cyclic codes, Inf. Control 15 (1969) 407-423.
H. C. A. van Tilborg, On quasi-cyclic codes with rate 1/m, IEEE Trans. Inform. Theory 24 (1978) 628-629.
T. A. Gulliver and V. K. Bhargava, Some best rate 1/p and rate (p-1)/p systematic quasi-cyclic codes, IEEE Trans. Inform. Theory 37 (1991) 552-555.
T. A. Gulliver and V. K. Bhargava, Some best rate 1/p and rate (p-1)/p systematic quasi-cyclic codes over GF(3) and GF(4), IEEE Trans. Inform. Theory 38 (1992) 1369-1374.
P. P. Greenough and R. Hill, Optimal ternary quasi-cyclic codes, Des. Codes Cryptogr. 2 (1992) 81-91.
E. Z. Chen, Six new binary quasi-cyclic codes, IEEE Trans. Inform. Theory 40 (1994) 1666-1667.
R. N. Daskalov, T. A. Gulliver, and E. Metodieva, New good quasi-cyclic ternary and quaternary linear codes, IEEE Trans. Inform. Theory 43 (1997) 1647-1650.
T. A. Gulliver and P. R. J. Östergård, Improved bounds for ternary linear codes of dimension 7, IEEE Trans. Inform. Theory 43 (1997) 1377-1388.
R. N. Daskalov, T. A. Gulliver, and E. Metodieva, New ternary linear codes, IEEE Trans. Inform. Theory 45 (1999) 1687-1688.
N. Aydin, I. Siap, and D. K. Ray-Chaudhuri, The structure of 1-generator quasi-twisted codes and new linear codes, Des. Codes Cryptogr. 24 (2001) 313-326.
N. Aydin and I. Siap, New quasi-cyclic codes over $\mathbb{F}_5$, Appl. Math. Lett. 15 (2002) 833-836.
V. C. Venkaiah and T. A. Gulliver, Quasi-cyclic codes over $\mathbb{F}_{13}$ and enumeration of defining polynomials, J. Discrete Algorithms 16 (2012) 249-257.
E. R. Berlekamp, Algebraic Coding Theory, Aegean Park Press (1984).
E. Z. Chen, A new iterative computer search algorithm for good quasi-twisted codes, Des. Codes Cryptogr. 77 (2015) 17-31.
M. A. de Boer, Almost MDS codes, Des. Codes Cryptogr. 9 (1996) 143-155.
S. Ball, Table of bounds on three dimensional linear codes or (n, r) arcs in PG(2, q), available at http://www-ma4.upc.es/~simeon/codebounds.html.
A. R. Calderbank and W. M. Kantor, The geometry of two-weight codes, Bull. London Math. Soc. 18 (1986) 97-122.
A. Vardy, The intractability of computing the minimum distance of a code, IEEE Trans. Inform. Theory 43 (1997) 1757-1766.
W. Bosma, J. Cannon, and C. Playoust, The Magma algebra system I, The user language, J. Symbolic Comput. 24 (1997) 235-265.
M. Grassl, Bounds on the minimum distances of linear codes, Online available at http://www.codetables.de.
N. Aydin and J. Murphree, New linear codes from constacyclic codes, J. Franklin Inst. 351 (2014) 1691-1699.
R. Hill, Optimal linear codes, in Cryptography and Coding II, C. Mitchell (Ed.), Oxford University Press (1992) 74-104.
E. Z. Chen, Database of quasi-twisted codes, Online available at http://moodle.tec.hkr.se/~chen/research/codes/searchqt.htm.
K. Betsumiya, S. Georgiou, T. A. Gulliver, M. Harada, and C. Koukouvinos, On self-dual codes over some prime fields, Discrete Math. 262 (2003) 37-58.
D. W. Newhart, On minimum weight codewords in QR codes, J. Combin. Theory Ser. A 48 (1988) 104-119.
I. S. Kotsireas, C. Koukouvinos, and D. E. Simos, MDS and near-MDS self-dual codes over large prime fields, Adv. Math. Commun. 3 (2009) 349-361.
M. Grassl and T. A. Gulliver, On self-dual MDS codes, in Proc. IEEE Int. Symp. Inform. Theory (2008) 1954-1957.
T. A. Gulliver, J.-L. Kim, and Y. Lee, New MDS or near-MDS self-dual codes, IEEE Trans. Inform. Theory 54 (2008) 4354-4360.
