Mathematics – Combinatorics
Scientific paper
2003-09-04
J. Combin. Theory Ser. A 100 (2002), no. 2, 232--249
Mathematics
Combinatorics
16 pages
Scientific paper
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 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. We show K^+(n,R) is of order 2^n/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>=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.
Cooper Joshua N.
Ellis Robert B.
Kahng Andrew B.
No associations
LandOfFree
Asymmetric binary covering codes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Asymmetric binary covering codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Asymmetric binary covering codes will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-357974