Asymmetric binary covering codes. (Q1865393): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2001316732 / rank | |||
Normal rank |
Revision as of 02:16, 20 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Asymmetric binary covering codes. |
scientific article |
Statements
Asymmetric binary covering codes. (English)
0 references
26 March 2003
0 references
The authors refer to the ordinary binary \((n,R)\)-covering code as a symmetric binary covering code of length \(n\) and radius \(R\) (i.e. a set of codewords \(C\subseteq Q_n\) \((n\)-cube) with covering radius \(R)\). Recent surveys on covering codes appear in [\textit{R. Brualdi}, \textit{S. Litsyn} and \textit{V. Pless}, Covering radius, in Handbook of coding theory. Vols. 1, 2 (Amsterdam: Elsevier), 755--826 (1998; Zbl 0922.94020)]; \textit{G. Cohen}, \textit{I. Honkala}, \textit{S. Litsyn} and \textit{A. Lobstein}, Covering codes. North-Holland Mathematical Library. 54 (Amsterdam: Elsevier) (1997; Zbl 0874.94001); and \textit{G. Cohen}, \textit{S. Litsyn}, \textit{A. Lobstein} and \textit{H. Mattson} jun., Covering radius 1985--1994, Appl. Algebra Eng. Commun. Comput. 8, 173--239 (1997; Zbl 0873.94025)]. An asymmetric binary covering code of length \(n\) and radius \(R\) is a subset \(C\) of \(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. In this paper, the authors explain several substantial differences and similarities between symmetric and asymmetric binary covering codes. They give the exact asymptotic order of magnitude of the size of minimal codes with constant radius and give exact asymptotics in the case of constant coradius. The bounds they provide are then used to derive somewhat weaker bounds in a completely general setting. Various bounds on \(K^+(n,R)\) are given in terms of the total number of 0's or 1's in a minimal code. The authors give also a table of their best-known bounds for \(K^+(n,R)\).
0 references
covering code
0 references
binary code
0 references
minimal code
0 references
probabilistic method
0 references
bounds
0 references