Authors:
Andrew Klapper, 779A Anderson Hall, Dept. of Computer Science,
University of Kentucky, Lexington, KY, 40506-0046, klapper at cs.uky.edu.
www.cs.uky.edu/~klapper/andy.html
Abstract The multicovering radii of a code are natural generalizations of the covering radius in which the goal is to cover all m-tuples of vectors for some m as cheaply as possible. In this paper describe several techniques for obtaining lower bounds on the sizes of codes achieving a given multicovering radius. Included among these methods is a generalization of the method of linear inequalitie, based on refined weight distributions of the code. For m=2, we also obtain a linear upper bound on the m-covering radius. We further study bounds on the sizes of codes with a given multicovering radius that are subcodes of a fixed code. We find, for example, constraints on parity checks that can hold for codes with small ordinary covering radius.
Index Terms -- Covering radius, error correcting codes, weight distribution, linear inequalities, supercodes.