Asymmetric binary covering codes

An asymmetric binary covering code of length n and radius R is a subset C, of the n-cube Q(n) such that every vector x epsilon Q(n) can be obtained from some vector c epsilon 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. We show K+(n, R) epsilon Theta(2"/n(R)) for constant R, using an asymmetric sphere-covering bound-and probabilistic methods. We show K+(n, n - R) = R + 1 for constant coradius R iff n greater than or equal to R(R +1)/2. These two results are extended to near-constant R and R, respectively. Various bounds on K+ are given in terms of the total number of 0's or 1's in a minimal code. The dimension of a minimal asymmetric linear binary code ([n,R](+)-code) is determined to be min{0, n - R}. We conclude by discussing open problems and techniques to compute explicit values for K+, giving a table of best-known bounds. (C) 2002 Elsevier Science (USA).