Multicovering Bounds from Relative Covering Radii

SIAM Journal on Discrete Math 15 (2002) 228-234.

Andrew Klapper, 779A Anderson Hall, Dept. of Computer Science, University of Kentucky, Lexington, KY, 40506-0046, klapper at
Iiro Honkal, University of Turku.

Abstract The multicovering radii of a code are a recently introduced natural generalizations of the covering radius measuring the smallest radius of balls around codewords that cover all $m$-tuples of vectors. In this paper we prove a new identity relating the multicovering radii of a code to a relativized notion of ordinary covering radius. This identity is used to prove new bounds on the multicovering radii of particular codes.

Index Terms -- Covering radius, multicovering radius, coding theory, Hamming codes.