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 - 14,k -5 0r d(min)-5 are normal, and we determine the covering radius of all proper codes of dimension k-5. Examples of abnormal nonlinear codes are given. In Part I we investigate the general theory of normalized covering radius, while Part II studies codes of dimension k -5, and normal and abnormal codes.