Asymmetric Binary Covering Codes

AbstractAn asymmetric binary covering code of length n and radius R is a subset C of the n-cube Qn such that every vector x∈Qn can be obtained from some vector c∈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)∈Θ(2n/nR) 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⩾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