Asymmetric Binary Covering Codes

✍ Scribed by Joshua N Cooper; Robert B Ellis; Andrew B Kahng

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 170 KB
• Volume: 100
• Category: Article
• ISSN: 0097-3165
• DOI: 10.1006/jcta.2002.3290

✦ Synopsis

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 2 Q n can be obtained from some vector c 2 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Þ 2 Yð2 n =n R Þ for constant R; using an asymmetric sphere-covering bound and probabilistic methods. We show

These two results are extended to near-constant R and % R 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 minf0; n À Rg: We conclude by discussing open problems and techniques to compute explicit values for K þ ; giving a table of best-known bounds.