On the covering radius problem for codes: (I) bounds on normalized covering radius.

In this two-part paper we introduce the notion of a stable code, determine the maximal covering radius of any (n,k) code, and obtain a new upper bound on the normalized covering radius. We show that, for fixed k and large n, the minimal covering radius t(n,k) is realized by a normal code in which all but one of the columns have multiplicity 1. Thus t(n+2,k)=t(n,k)+1 for sufficiently large n. We also show that codes with n