Locally Optimal (Nonshortening) Linear Covering Codes and Minimal Saturating Sets in Projective Spaces

A concept of locally optimal (LO) linear covering codes is introduced in accordance with the concept of minimal saturating sets in projective spaces over finite fields. An LO code is nonshortening in the sense that one cannot remove any column from a parity-check matrix without increasing the code covering radius. Several q^m-concatenating constructions of LO covering codes are described. Taking a starting LO code as a “seed”, such constructions produce an infinite family of LO codes with the same covering radius. The infinite families of LO codes are designed using minimal saturating sets as starting codes. Newupper bounds on the length function are given. Newextr emal and classification problems for linear covering codes are formulated and investigated, in particular, the spectrum of possible lengths of LO codes including the greatest possible length. The complete computer classification of the minimal saturating sets in small geometries and of the corresponding LO codes is obtained.