(l,s)(l,s)-extension of linear codes

We construct new linear codes with high minimum distance dd. In at least 12 cases these codes improve the minimum distance of the previously known best linear codes for fixed parameters n,kn,k. Among these new codes there is an optimal ternary [88,8,54]3[88,8,54]3 code.We develop an algorithm, which starts with already good codes CC, i.e. codes with high minimum distance dd for given length nn and dimension kk over the field GF(q)GF(q). The algorithm is based on the newly defined (l,s)(l,s)-extension. This is a generalization of the well-known method of adding a parity bit in the case of a binary linear code of odd minimum weight. (l,s)(l,s)-extension tries to extend the generator matrix of CC by adding ll columns with the property that at least ss of the ll letters added to each of the codewords of minimum weight in CC are different from 00. If one finds such columns the minimum distance of the extended code is d+sd+s provided that the second smallest weight in CC was at least d+sd+s. The question whether such columns exist can be settled using a Diophantine system of equations.