Asymmetric binary covering codes.

DOI10.1006/JCTA.2002.3290MaRDI QIDQ1865393zbMATH OpenOpenAlexFDO

Authors Joshua Cooper, Robert B. Ellis, Andrew B. Kahng

Publication date 26 March 2003

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0309081

bounds probabilistic method binary code covering code minimal code

Bounds on codes (94B65) Applications of the theory of convex sets and geometry of numbers (covering radius, etc.) to coding theory (94B75)

Abstract: 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.

Recommendations

Cites work

Cited in

(12)

This page was built for publication: Asymmetric binary covering codes.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1865393)