Asymmetric Binary Covering Codes |
| |
Authors: | Joshua N Cooper Robert B Ellis Andrew B Kahng |
| |
Institution: | a Department of Mathematics, University of California, San Diego, 9500, Gilman Drive 0112, La Jolla, California, 92093-0112, f1, f2;b Department of Computer Science and Engineering, University of California, San Diego, La Jolla, California, f3 |
| |
Abstract: | An asymmetric binary covering code of length n and radius R is a subset
of the n-cube Qn such that every vector xQn can be obtained from some vector 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−
)=
+1 for constant coradius
iff n
(
+1)/2. These two results are extended to near-constant R and
, 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. |
| |
Keywords: | covering code binary code minimal code probabilistic method |
本文献已被 ScienceDirect 等数据库收录! |
|