Optimal linear codes from matrix groups

New linear codes (sometimes optimal) over the finite field with q elements are constructed. In order to do this, an equivalence between the existence of a linear code with a prescribed minimum distance and the existence of a solution of a certain system of Diophantine linear equations is used. To reduce the size of the system of equations, the search for solutions is restricted to solutions with special symmetry given by matrix groups. This allows to find more than 400 new codes for the case q=2,3,4,5,7,9.

I. Introduction

We are interested in the construction of -ary linear -codes. These are -dimensional subspaces of the -dimensional vector space over the finite field with elements. The codewords of length are the elements of the subspace, they are written as row vectors. The weight of a codeword is defined to be the number of nonzero entries of and the minimum distance of a code is the minimum of all weights of the nonzero codewords in . For the purpose of error-correcting codes, we are interested in codes with high minimum distance as these allow the correction of errors. On the other hand, we are interested in codes of small length . High minimum distance and small length are conflicting goals for the optimization of codes. A linear code is called optimal if there is no linear code. There are bounds [9] giving upper limits for the minimum distance of a linear code of fixed length . In most cases, the best upper bound is given by the Griesmer bound [10]. In many cases, there is a gap between the minimum distance of the best known -ary linear -code and the limit given by these upper bounds. In this paper, we shorten the gap in more than 400 cases by constructing codes with a higher minimum distance than previously known.