The geometric approach to the existence of some quaternary Griesmer codes
- PDF / 353,704 Bytes
- 16 Pages / 439.37 x 666.142 pts Page_size
- 77 Downloads / 149 Views
The geometric approach to the existence of some quaternary Griesmer codes Assia Rousseva1
· Ivan Landjev2,3
Received: 3 September 2019 / Revised: 19 May 2020 / Accepted: 11 June 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract In this paper we prove the nonexistence of the hypothetical arcs with parameters (395, 100), (396, 100), (448, 113), and (449, 113) in PG(4, 4). This rules out the existence of Griesmer codes with parameters [395, 5, 295]4 , [396, 5, 296]4 , [448, 5, 335]4 , [449, 5, 336]4 and solves four instances of the main problem of coding theory for q = 4, k = 5. The proof relies on the characterization of (100, 26)- and (113, 29)-arcs in PG(3, 4) and is entirely computer-free. Keywords Linear codes · Griesmer bound · Griesmer codes · Griesmer arcs · Finite projective geometries · Optimal linear codes Mathematics Subject Classification 94B65 · 51A20 · 51A21 · 51A22
1 Introduction The problem of finding the minimal length of a linear code of fixed dimension k and fixed minimum distance d over a fixed field Fq is known as the main problem in coding theory [13]. It is closely related, and in some sense equivalent, to the problem of distributing points (possibly with multiplicities) in the finite geometry PG(k − 1, q) so that at most a fixed number of them lie on any hyperplane. This approach has been adopted by many researchers,
This is one of several papers published in Designs, Codes and Cryptography comprising the “Special Issue on Coding and Cryptography 2019”.
B
Assia Rousseva [email protected] Ivan Landjev [email protected]
1
Faculty of Mathematics and Informatics, Sofia University “St. Kl. Ohridski”, 5 J. Bourchier Blvd., 1164 Sofia, Bulgaria
2
New Bulgarian University, 21 Montevideo str., 1618 Sofia, Bulgaria
3
Institute of Mathematics and Informatics, Bulgarian Academy of Sciences, 8 Acad G. Bonchev str., 1113 Sofia, Bulgaria
123
A. Rousseva, I. Landjev
notably N. Hamada, R. Hill, T. Helleseth, H. N. Ward, S. Dodunekov, J. Simonis, L. Storme, T. Maruta, A. Brouwer, to mention but a few (cf. [4,19,20,25] and the references there). One of the best known bounds in coding theory is the Griesmer bound [11]. It is a lower bound on the length n of a code of given dimension k, and a given minimum distance d over a given field Fq : k−1 d n≥ . (1) q k−1 i=0
The right hand side in (1) is traditionally denoted by gq (k, d). Linear codes of length n = gq (k, d) are called Griesmer codes. For given k, d and q, we denote by n q (k, d) the minimal length n for which an [n, k, d]q -code does exist. It was noted by various authors [2,13] that for fixed k and q Griesmer codes exist for all sufficiently large d. In the same time, for fixed d and q and large k the Griesmer bounds becomes worse than the sphere-packing bound [5,24] and the optimal value n q (k, d) deviates infinitely from gq (k, d). Hence a reasonable approach is to determine the optimal length of a linear code for a fixed “small” dimension over a fixed field for all possible minimum distance
Data Loading...
