Asymmetric binary covering codes. (Q1865393)

The authors refer to the ordinary binary \((n,R)\)-covering code as a symmetric binary covering code of length \(n\) and radius \(R\) (i.e. a set of codewords \(C\subseteq Q_n\) \((n\)-cube) with covering radius \(R)\). Recent surveys on covering codes appear in [\textit{R. Brualdi}, \textit{S. Litsyn} and \textit{V. Pless}, Covering radius, in Handbook of coding theory. Vols. 1, 2 (Amsterdam: Elsevier), 755--826 (1998; Zbl 0922.94020)]; \textit{G. Cohen}, \textit{I. Honkala}, \textit{S. Litsyn} and \textit{A. Lobstein}, Covering codes. North-Holland Mathematical Library. 54 (Amsterdam: Elsevier) (1997; Zbl 0874.94001); and \textit{G. Cohen}, \textit{S. Litsyn}, \textit{A. Lobstein} and \textit{H. Mattson} jun., Covering radius 1985--1994, Appl. Algebra Eng. Commun. Comput. 8, 173--239 (1997; Zbl 0873.94025)]. An asymmetric binary covering code of length \(n\) and radius \(R\) is a subset \(C\) of \(Q_n\) such that every vector \(x\in Q_n\) can be obtained from some vector \(c\in C\) by changing at most \(R\) 1's of \(c\) to 0's, where \(R\) is as small as possible. \(K^+(n,R)\) is defined as the smallest size of such a code. In this paper, the authors explain several substantial differences and similarities between symmetric and asymmetric binary covering codes. They give the exact asymptotic order of magnitude of the size of minimal codes with constant radius and give exact asymptotics in the case of constant coradius. The bounds they provide are then used to derive somewhat weaker bounds in a completely general setting. Various bounds on \(K^+(n,R)\) are given in terms of the total number of 0's or 1's in a minimal code. The authors give also a table of their best-known bounds for \(K^+(n,R)\).