The Multicovering Radii of Codes

IEEE Transactions on Information Theory 43 (1997) 1372-1377.

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

Abstract The covering radius of a code is the least r such that the set of balls of radius r around codewords covers the entire ambient space. We introduce a generalization of the notion of covering radius. The m-covering radius of a code is the least radius such that the set of balls of the radius covers all m-tuples of elements in the ambient space. We investigate basic properties of m-covering radii. We investigate whether codes exist with given m-covering radii (they don't always). We derive bounds on the size of the smallest code with a given m-covering radius, based on generalizations of the sphere bound and the method of counting excesses.

Index Terms -- Covering radius, coding theory, Hamming distance, binary vectors.