Further Results on the Covering Radius of Codes
IEEE Transactions on Information Theory, Vol. IT-32, pp. 680-694, September 1986.
Gérard COHEN, Antoine LOBSTEIN
Centre National de la Recherche Scientifique
Ecole Nationale Supérieure des Télécommunications
46 rue Barrault, 75634 Paris cédex 13, France
& N.J.A. SLOANE
AT & T Bell Laboratories, Murray Hill
NJ 07974, Etats-Unis d'Amérique
Abstract. A number of upper and lower bounds are obtained for K(n,R), the minimal number of codewords in any binary code of length n and covering radius R. Several new constructions are used to derive the upper bounds, including an amalgamated direct sum construction for nonlinear codes. This construction works best when applied to normal codes, and we give some new and stronger conditions which imply that a linear code is normal. An upper bound is given for the density of a covering code over any alphabet, and it is shown that K(n+2,R+1) =< K(n,R) holds for sufficiently large n.