On optimal linear codes of dimension 4

Abstract

In coding theory, the problem of finding the shortest linear codes for a fixed set of parameters is central. Given the dimension $k$, the minimum weight $d$, and the order $q$ of the finite field $\bF_q$ over which the code is defined, the function $n_q(k, d)$ specifies the smallest length $n$ for which an $[n, k, d]_q$ code exists. The problem of determining the values of this function is known as the problem of optimal linear codes. Using the geometric methods through projective geometry, we determine $n_q(4,d)$ for some values of $d$ by constructing new codes and by proving the nonexistence of linear codes with certain parameters.

Keywords

• Optimal linear codes
• Griesmer bound
• Geometric method

References

1. [1] S. Ball, Table of bounds on three dimensional linear codes or (n; r)-arcs in PG(2; q), available at https://web.mat.upc.edu/people/simeon.michael.ball/codebounds.html.
2. [2] A. Betten, E. J. Cheon, S. J. Kim, T. Maruta, The classification of (42; 6)8 arcs, Adv. Math. Commun. 5 (2011) 209–223.
3. [3] I. Bouyukliev, Y. Kageyama, T. Maruta, On the minimum length of linear codes over F5, Discrete Math. 338 (2015) 938–953.
4. [4] A. E. Brouwer, M. van Eupen, The correspondence between projective codes and 2-weight codes, Des. Codes Cryptogr. 11 (1997) 261–266.
5. [5] M. van Eupen, R. Hill, An optimal ternary [69; 5; 45]3 codes and related codes, Des. Codes Cryptogr. 4 (1994) 271–282.
6. [6] M. Fujii, Nonexistence of some Griesmer codes of dimension 4, Master Thesis, Osaka Prefecture University (2019).
7. [7] M. Grassl, "Bounds on the minimum distance of linear codes and quantum codes." Online available at http://www.codetables.de.
8. [8] J. H. Griesmer, A bound for error-correcting codes, IBM J. Res. Develop. 4 (1960) 532–542.

9. [9] N. Hamada, A characterization of some [n; k; d; q]-codes meeting the Griesmer bound using a minihyper in a finite projective geometry, Discrete Math., 116 (1993) 229–268.
10. [10] R. Hill, Optimal linear codes, In: C. Mitchell(Ed.), Cryptography and Coding II, Oxford Univ. Press, Oxford (1992) 75–104.
11. [11] R. Hill, E. Kolev, A survey of recent results on optimal linear codes, In: Combinatorial Designs and their Applications, F.C. Holroyd et al. Ed., Chapman and Hall/CRC Press Research Notes in Mathematics, CRC Press. Boca Raton (1999) 127–152.
12. [12] J. W. P. Hirschfeld, Finite Projective Spaces of Three Dimensions, Clarendon Press, Oxford (1985).
13. [13] J. W. P. Hirschfeld, Projective Geometries over Finite Fields, Clarendon Press, Oxford, second edition (1998).
14. [14] C. Jones, A. Matney, H. Ward, Optimal four-dimensional codes over GF(8), Electron. J. Combin. 13 (2006) #R43, .
15. [15] Y. Kageyama, T. Maruta, On the geometric constructions of optimal linear codes, Des. Codes Cryptogr., 81 (2016) 469–480.
16. [16] R. Kanazawa, T. Maruta, On optimal linear codes over F8, Electronic J. Combin., 18(1) (2011) #P34
17. [17] K. Kumegawa, T. Okazaki, T. Maruta, On the minimum length of linear codes over the field of 9 elements, Electron. J. Combin. 24(1) (2017) #P1.50.
18. [18] K. Kumegawa, T. Maruta, Nonexistence of some Griesmer codes over Fq, Discrete Math. 339 (2016) 515–521.
19. [19] K. Kumegawa, T. Maruta, Non-existence of some 4-dimensional Griesmer codes over finite fields, J. Algebra Comb. Discrete Struct. Appl. 5 (2018) 101–116.
20. [20] I. Landjev, L. Storme, A study of (x(q + 1); x; 2; q)-minihypers, Des. Codes Cryptogr. 54 (2010) 135–147.
21. [21] T. Maruta, On the minimum length of q-ary linear codes of dimension four, Discrete Math., 208/209 (1999) 427–435.
22. [22] T. Maruta, On the nonexistence of q-ary linear codes of dimension five, Des. Codes Cryptogr. 22 (2001) 165–177.
23. [23] T. Maruta, A new extension theorem for linear codes, Finite Fields Appl. 10 (2004) 674–685.
24. [24] T. Maruta, Optimal 4-dimensional linear codes over F8, Proceedings of 13th International Workshop on Algebraic and Combinatorial Coding Theory (ACCT 2012), Pomorie, Bulgaria (2012) 257–262.
25. [25] T. Maruta, Construction of optimal linear codes by geometric puncturing, Serdica J. Computing 7 (2013) 73–80.
26. [26] T. Maruta, Griesmer bound for linear codes over finite fields, available at http://mars39.lomo.jp/opu/griesmer.htm.
27. [27] T. Maruta, Y. Oya, On optimal ternary linear codes of dimension 6, Adv. Math. Commun. 5 (2011) 505–520.
28. [28] T. Maruta, M. Shinohara, M. Takenaka, Constructing linear codes from some orbits of projectivities,Discrete Math. 308 (2008) 832–841.
29. [29] T. Maruta, T. Tanaka, H. Kanda, Some generalizations of extension theorems for linear codes over finite fields, Australas. J. Combin. 60 (2014) 150–157.
30. [30] T. Maruta, Y. Yoshida, A generalized extension theorem for linear codes, Des. Codes Cryptogr. 62 (2012) 121–130.
31. [31] M. Takenaka, K. Okamoto, T. Maruta, On optimal non-projective ternary linear codes, Discrete Math. 308 (2008) 842–854.
32. [32] Y. Yoshida, T. Maruta, An extension theorem for [n; k; d]q codes with gcd(d; q) = 2, Australas. J. Combin. 48 (2010) 117–131.