Improved Multicovering Bounds from Linear Inequalities and Supercodes

IEEE Transactions on Information Theory, 50 (2004) 532-536.

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

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.