BibTex RIS Cite

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

Year 2015, Volume: 2 Issue: 1, 1 - 16, 22.01.2015
https://doi.org/10.13069/jacodesmath.36947

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.

References

  • F. J. MacWilliams F. J., N. J. A. Sloane, The theory of error-correcting codes, North-Holland, 1977.
  • C. L. ACen and W. W. Peterson, Some Results on Quasi-cyclic Codes, Inf. Contr., 15, 407-423, 1969.
  • 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.
  • 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.
  • P. P. Greenough, R. Hill, Optimal Ternary Quasi-cyclic Codes, Des. Codes Crypt.,2,81-91, 1992.
  • E. Z. Chen, Six New Binary Quasi-cyclic Codes, IEEE Trans. Inform. Theory, 40, 1666-1667, 1994.
  • 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.
  • 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.
  • R. N. Daskalov, T. A. Gulliver, E. Metodieva, New Ternary Linear Codes, IEEE Trans. Inform. Theory, 45, 1687-1688, 1999.
  • 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.
  • N. Aydin, I. Siap, New Quasi-cyclic Codes over F, Appl. Math. Lett., 15, 833-836, 2002.
  • V. C. Venkaiah, T.A. Gulliver, Quasi-cyclic codes over F13and enumeration of defining polynomials, J. of Discrete Algorithms, 16, 249-257, 2012.
  • E. R. Berlekamp, Algebraic Coding Theory, Aegean Park, (1984).
  • 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.
  • 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
  • A. R. Caldebank, W. M. Kantor, The geometry of two-weight codes, Bull. London Math. Soc., 18, 97-122, 1986.
  • A. Vardy, The Intractability of Computing the Minimum Distance of a Code, IEEE Trans. Inform. Theory, 43, 1757-1766, 1997.
  • W. Bosma, L. Cannon, C. Playoust, The Magma Algebra System I, The User Language, J. Symbolic Comput., 24, 235-265, 1997.
  • M. Grassl, Bounds on the minimum distances of linear codes, available at http://www.codetables.de, Accessed July 22, 2014.
  • N. Aydin, J. Murphree, New Linear Codes from Constacyclic Codes, J. Franklin Inst., 351, 1691-1699, 20
  • R. Hill, Optimal Linear Codes, in Cryptography and Coding II, edited by C. Mitchell, Oxford Uni- versity Press, 74-104, 1992.
  • E. Z. Chen, Database of Quasi-twisted codes, available at http://moodle.tec.hkr.se/∼chen/research /codes/searchqt.htm, Accessed July 22, 2014
  • 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.
  • 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.
  • M. Grassl, T. A. Gulliver, On Self-dual MDS codes, Proc. IEEE Int. Symp. Inform. Theory, 1954- 1957, 2008.
  • T. A. Gulliver, J-L. Kim, Y. Lee, New MDS or near-MDS Self-dual Codes, IEEE Trans. Inform. Theory, 54, 4354-4360, 2008.

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

Year 2015, Volume: 2 Issue: 1, 1 - 16, 22.01.2015
https://doi.org/10.13069/jacodesmath.36947

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.

References

  • F. J. MacWilliams F. J., N. J. A. Sloane, The theory of error-correcting codes, North-Holland, 1977.
  • C. L. ACen and W. W. Peterson, Some Results on Quasi-cyclic Codes, Inf. Contr., 15, 407-423, 1969.
  • 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.
  • 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.
  • P. P. Greenough, R. Hill, Optimal Ternary Quasi-cyclic Codes, Des. Codes Crypt.,2,81-91, 1992.
  • E. Z. Chen, Six New Binary Quasi-cyclic Codes, IEEE Trans. Inform. Theory, 40, 1666-1667, 1994.
  • 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.
  • 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.
  • R. N. Daskalov, T. A. Gulliver, E. Metodieva, New Ternary Linear Codes, IEEE Trans. Inform. Theory, 45, 1687-1688, 1999.
  • 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.
  • N. Aydin, I. Siap, New Quasi-cyclic Codes over F, Appl. Math. Lett., 15, 833-836, 2002.
  • V. C. Venkaiah, T.A. Gulliver, Quasi-cyclic codes over F13and enumeration of defining polynomials, J. of Discrete Algorithms, 16, 249-257, 2012.
  • E. R. Berlekamp, Algebraic Coding Theory, Aegean Park, (1984).
  • 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.
  • 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
  • A. R. Caldebank, W. M. Kantor, The geometry of two-weight codes, Bull. London Math. Soc., 18, 97-122, 1986.
  • A. Vardy, The Intractability of Computing the Minimum Distance of a Code, IEEE Trans. Inform. Theory, 43, 1757-1766, 1997.
  • W. Bosma, L. Cannon, C. Playoust, The Magma Algebra System I, The User Language, J. Symbolic Comput., 24, 235-265, 1997.
  • M. Grassl, Bounds on the minimum distances of linear codes, available at http://www.codetables.de, Accessed July 22, 2014.
  • N. Aydin, J. Murphree, New Linear Codes from Constacyclic Codes, J. Franklin Inst., 351, 1691-1699, 20
  • R. Hill, Optimal Linear Codes, in Cryptography and Coding II, edited by C. Mitchell, Oxford Uni- versity Press, 74-104, 1992.
  • E. Z. Chen, Database of Quasi-twisted codes, available at http://moodle.tec.hkr.se/∼chen/research /codes/searchqt.htm, Accessed July 22, 2014
  • 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.
  • 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.
  • M. Grassl, T. A. Gulliver, On Self-dual MDS codes, Proc. IEEE Int. Symp. Inform. Theory, 1954- 1957, 2008.
  • T. A. Gulliver, J-L. Kim, Y. Lee, New MDS or near-MDS Self-dual Codes, IEEE Trans. Inform. Theory, 54, 4354-4360, 2008.
There are 26 citations in total.

Details

Primary Language English
Journal Section Articles
Authors

Eric Z. Chen This is me

Nuh Aydın

Publication Date January 22, 2015
Published in Issue Year 2015 Volume: 2 Issue: 1

Cite

APA Chen, E. Z., & Aydın, N. (2015). A database of linear codes over F_13 with minimum distance bounds and new quasi-twisted codes from a heuristic search algorithm. Journal of Algebra Combinatorics Discrete Structures and Applications, 2(1), 1-16. https://doi.org/10.13069/jacodesmath.36947
AMA Chen EZ, Aydın N. A database of linear codes over F_13 with minimum distance bounds and new quasi-twisted codes from a heuristic search algorithm. Journal of Algebra Combinatorics Discrete Structures and Applications. March 2015;2(1):1-16. doi:10.13069/jacodesmath.36947
Chicago Chen, Eric Z., and Nuh Aydın. “A Database of Linear Codes over F_13 With Minimum Distance Bounds and New Quasi-Twisted Codes from a Heuristic Search Algorithm”. Journal of Algebra Combinatorics Discrete Structures and Applications 2, no. 1 (March 2015): 1-16. https://doi.org/10.13069/jacodesmath.36947.
EndNote Chen EZ, Aydın N (March 1, 2015) A database of linear codes over F_13 with minimum distance bounds and new quasi-twisted codes from a heuristic search algorithm. Journal of Algebra Combinatorics Discrete Structures and Applications 2 1 1–16.
IEEE E. Z. Chen and N. Aydın, “A database of linear codes over F_13 with minimum distance bounds and new quasi-twisted codes from a heuristic search algorithm”, Journal of Algebra Combinatorics Discrete Structures and Applications, vol. 2, no. 1, pp. 1–16, 2015, doi: 10.13069/jacodesmath.36947.
ISNAD Chen, Eric Z. - Aydın, Nuh. “A Database of Linear Codes over F_13 With Minimum Distance Bounds and New Quasi-Twisted Codes from a Heuristic Search Algorithm”. Journal of Algebra Combinatorics Discrete Structures and Applications 2/1 (March 2015), 1-16. https://doi.org/10.13069/jacodesmath.36947.
JAMA Chen EZ, Aydın N. A database of linear codes over F_13 with minimum distance bounds and new quasi-twisted codes from a heuristic search algorithm. Journal of Algebra Combinatorics Discrete Structures and Applications. 2015;2:1–16.
MLA Chen, Eric Z. and Nuh Aydın. “A Database of Linear Codes over F_13 With Minimum Distance Bounds and New Quasi-Twisted Codes from a Heuristic Search Algorithm”. Journal of Algebra Combinatorics Discrete Structures and Applications, vol. 2, no. 1, 2015, pp. 1-16, doi:10.13069/jacodesmath.36947.
Vancouver Chen EZ, Aydın N. A database of linear codes over F_13 with minimum distance bounds and new quasi-twisted codes from a heuristic search algorithm. Journal of Algebra Combinatorics Discrete Structures and Applications. 2015;2(1):1-16.

Cited By

Some new binary codes with improved minimum distances
Journal of Algebra Combinatorics Discrete Structures and Applications
https://doi.org/10.13069/jacodesmath.404964


New Linear Codes over $GF(3)$, $GF(11)$, and $GF(13)$
Journal of Algebra Combinatorics Discrete Structures and Applications
Nuh Aydin
https://doi.org/10.13069/jacodesmath.508968

Construction of quasi-twisted codes and enumeration of defining polynomials
Journal of Algebra Combinatorics Discrete Structures and Applications
T. Aaron Gulliver
https://doi.org/10.13069/jacodesmath.645015