A database of linear codes over F_13 with minimum distance bounds and new quasi-twisted codes from a heuristic search algorithm

Abstract

 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.

Keywords

• Database of linear codes, Quasi-twisted codes, Heuristic search algorithm, Iterative search

References

1. F. J. MacWilliams F. J., N. J. A. Sloane, The theory of error-correcting codes, North-Holland, 1977.
2. C. L. ACen and W. W. Peterson, Some Results on Quasi-cyclic Codes, Inf. Contr., 15, 407-423, 1969.
3. H. C. A. van Tilborg, On Quasi-cyclic Codes with rate 1/m, IEEE Trans. Inform. Theory, 24, 628-629, 19 T. A. Gulliver, V. K. Bhargava, Some Best Rate 1/p and Rate (p-1)/p Systematic Quasi-cyclic Codes, IEEE Trans. Inform. Theory, 37, 552-555, 1991.
4. T. A. Gulliver, 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, 1369-1374, 1992.
5. P. P. Greenough, R. Hill, Optimal Ternary Quasi-cyclic Codes, Des. Codes Crypt.,2,81-91, 1992.
6. E. Z. Chen, Six New Binary Quasi-cyclic Codes, IEEE Trans. Inform. Theory, 40, 1666-1667, 1994.
7. R. N. Daskalov, T. A. Gulliver, E. Metodieva, New Good Quasi-cyclic Ternary and Quaternary Linear Codes, IEEE Trans. Inform. Theory, 43, 1647-1650, 1997.
8. T. A. Gulliver, P. R. J. Östergård, Improved Bounds for Ternary Linear Codes of Dimension 7, IEEE Trans. Inform. Theory, 43, 1377-1388, 1997.

9. R. N. Daskalov, T. A. Gulliver, E. Metodieva, New Ternary Linear Codes, IEEE Trans. Inform. Theory, 45, 1687-1688, 1999.
10. N. Aydin, I. Siap, D. K. Ray-Caudhuri, The Structure of 1-generator Quasi-twisted Codes and New Linear Codes, Des. Codes Crypt.,24, 313-326, 2001.
11. N. Aydin, I. Siap, New Quasi-cyclic Codes over F, Appl. Math. Lett., 15, 833-836, 2002.
12. V. C. Venkaiah, T.A. Gulliver, Quasi-cyclic codes over F13and enumeration of defining polynomials, J. of Discrete Algorithms, 16, 249-257, 2012.
13. E. R. Berlekamp, Algebraic Coding Theory, Aegean Park, (1984).
14. E. Z. Chen, A New Iterative Computer Search Algorithm for Good Quasi-twisted Codes, accepted for publication in Des. Codes Crypt., in press. M. A. De Boer, Almost MDS Codes, Des. Codes Crypt., 9, 143-155, 1996.
15. S. Ball, Table of Bounds on Three Dimensional Linear Codes or (n, r) Arcs in P G(2, q), available at http://www-ma4.upc.es/∼ simeon/codebounds.html, Accessed July 22, 2014
16. A. R. Caldebank, W. M. Kantor, The geometry of two-weight codes, Bull. London Math. Soc., 18, 97-122, 1986.
17. A. Vardy, The Intractability of Computing the Minimum Distance of a Code, IEEE Trans. Inform. Theory, 43, 1757-1766, 1997.
18. W. Bosma, L. Cannon, C. Playoust, The Magma Algebra System I, The User Language, J. Symbolic Comput., 24, 235-265, 1997.
19. M. Grassl, Bounds on the minimum distances of linear codes, available at http://www.codetables.de, Accessed July 22, 2014.
20. N. Aydin, J. Murphree, New Linear Codes from Constacyclic Codes, J. Franklin Inst., 351, 1691-1699, 20
21. R. Hill, Optimal Linear Codes, in Cryptography and Coding II, edited by C. Mitchell, Oxford Uni- versity Press, 74-104, 1992.
22. E. Z. Chen, Database of Quasi-twisted codes, available at http://moodle.tec.hkr.se/∼chen/research /codes/searchqt.htm, Accessed July 22, 2014
23. K. Betsumiya, S. Georgiou, T. A. Gulliver, M. Harada, C. Koukouvinos, On Self-dual Codes over Some Prime Fields, Discrete Math. 262, 37-58, 2003.
24. D. W. Newhart, On Minimum Weight Codewords in QR codes, J. Combin. Theory Ser. A 48, 104-119, 19 I. S. Kotsireas C. Koukouvinos, D. E. Simos, MDS and near-MDS Self-dual Codes over Large Prime Fields, Advances in Math. Commun.,3 , 349-361, 2009.
25. M. Grassl, T. A. Gulliver, On Self-dual MDS codes, Proc. IEEE Int. Symp. Inform. Theory, 1954- 1957, 2008.
26. T. A. Gulliver, J-L. Kim, Y. Lee, New MDS or near-MDS Self-dual Codes, IEEE Trans. Inform. Theory, 54, 4354-4360, 2008.