A subset C of vertices in an undirected graph G=(V,E) is called a 1-identifying code if the sets I(v)={u/spl isin/C:d(u,v)/spl les/1}, v/spl isin/V, are nonempty and no two of them are the same set. It is natural to consider classes of codes that retain the identification property under various conditions, e.g., when the sets I(v) are possibly slightly corrupted. We consider two such classes of robust codes. We also consider dynamic identifying codes, i.e., walks in G whose vertices form an identifying code in G.

It is shown that in the infinite square grid the density of every $(r, \leq 2)$-identifying code is at least 1/8 and that there exists a sequence $C_r$ of $(r, \leq 2)$-identifying codes such that the density of C r tends to 1/8 when $r \rightarrow \infty$. In the infinite triangular grid a sequence $C'_r$ of $(r, \leq 2)$-identifying codes is given such that the density of $C'_r$ tends to 0 when $r \rightarrow \infty$.

The multicovering radii of a code are recently introduced natural generalizations of the covering radius measuring the smallest radius of balls around codewords that cover all m-tuples of vectors. In this paper we prove a new identity relating the multicovering radii of a code to a relativized notion of ordinary covering radius. This identity is used to prove new bounds on the multicovering radii of particular codes.

A motivation for identifying codes comes from quality control in multiprocessor systems, that is, we are able, with the aid of these codes, to find faulty processors in such a system. We give a construction of two infinite families of optimal codes, which identify up to two malfunctioning processors in Hamming spaces.

Fault diagnosis of multiprocessor systems motivates the following graph-theoretic definition. A subset C of points in an undirected graph G=(V, E) is called an identifying code if the sets B(v)/spl cap/C consisting of all elements of C within distance one from the vertex v are different. We also require that the sets B(v)/spl cap/C are all nonempty. We take G to be the infinite square lattice with diagonals and show that the density of the smallest identifying code is at least 2/9 and at most 4/17.

In an undirected graph G=(V,E), a subset $C \subseteq V$ is called an identifying code if the sets $B_1(v) \cap C$ consisting of all elements of C within distance one from the vertex v are nonempty and different. We take G to be the infinite hexagonal grid and show that the density of any identifying code is at least 16/39 and that there is an identifying code of density 3/7.

The covering radius of a code tells us how far in the sense of Hamming distance an arbitrary word of the ambient space can be from the code. For a few decades this parameter has been widely studied. We estimate the covering ratios of a code when the dual distance is known. We derive a new bound on covering radii of linear codes. It improves essentially on the previously known estimates in a certain wide range. We also study asymptotic bounds on the cardinality of constant weight codes.

We show that for a code used for error detection in the binary-symmetric channel (BSC), the probability of an undetected error can have several local maxima. In particular, we construct a code with three local maxima in (0, 1/2), a code with five local maxima in (0, 1); and a linear code with two local maxima in (0, 1/2) and a linear code with three local maxima in (0, 1).

We study geometrically the domain of linear binary codes and of unrestricted binary codes in the plane (normalized covering radius, normalized minimal distance).

A binary code $C \subseteq \mathbb{F}_2^n$ with M codewords is called an $( n,M,r,u )$ multiple covering of the farthest-off points (MCF) if the Hamming spheres of radius r centered at the codewords cover the whole space $\mathbb{F}_2^n $ and every $x \in \mathbb{F}_2^n $ such that $d( x,C ) = r$ is covered by at least $\mu $ codewords. The minimum possible cardinality $F( n,r,\mu )$ of such a code is studied and tables of upper bounds on $F ( n,r,\mu )$ for $n \leq 16,r \leq 4,\mu \leq 4$ are given.

Introduces a generalization of the concepts of coverings and packings in Hamming space called weighted coverings and packings. This allows to formulate a number of well-known coding theoretical problems in a uniform manner. The authors study the existence of perfect weighted codes, discuss connections between weighted coverings and packings, and present many constructions for them.

It is proved that codes of length n, covering radius R, and minimum Hamming distance 2R-1 are normal if R does not divide n. Constructions for abnormal codes with covering radius R and minimum Hamming distance at least R-1 are given.>

The covering radius of binary codes is studied. Bounds on K(n,R), the minimum cardinality of any binary code of length n and covering radius R, are found. Modifications of the van Wee lower bounds are proved for K(n,R), the minimal number of codewords in any binary code of length n and covering radius R. The first of the two van Wee bounds is based on studying the Hamming spheres of radius 1 centered at the points which have distance R to the code C. The points covered by more than one codeword are divided into several classes and better estimates for some of these classes are obtained. Using a suitable averaging process, the lower bound for K(n,R) when R>or=2 is improved. The second van Wee bound studies spheres of radius 2 centered at the points which have distance R-1 or R to the code C. These points are divided essentially into two classes: the points that are covered by only one codeword of C, and the points that are covered by more than one codeword.>

The concept of a (k, t)-subnormal covering code is defined. It is discussed how an amalgamated-direct-sumlike construction can be used to combine such codes. The existence of optimal (q, n, M) 1 codes C is discussed such that by puncturing the first coordinate of C one obtains a code with (q, 1)-subnorm 2.>

The normality of binary codes is studied. The minimum cardinality of a binary code of length n with covering radius R is denoted by K(n,R). It is assumed that C is an (n,M)R code, that is, a binary code of length n with M codewords and covering radius R. It is shown that if C is an (n,M)1 code, then it is easy to find a normal (n,M)1 code by changing C in a suitable way, and that all the optimal (n,M)1 codes (i.e. those for which M=K(n,1)) are normal and their every coordinate is acceptable. It is shown that if C is an abnormal (n,M) code, then n>or=9, and an abnormal (9118)1 code which is the smallest abnormal code known at present, is constructed. Lower bounds on the minimum cardinality of a binary abnormal code of length n with covering radius 1 are derived, and it is shown that if an (n,M)1 code is abnormal, then M>or=96.>

The authors prove combinatorial lower bounds for K/sub q/(n,R), the minimal cardinality of any q-ary code of length n and covering radius R. Tables of lower bounds for K/sub q/(n,R) are presented for q=3, 4, 5.>

G.D. Chen et al. (ibid., vol.IT-32, p.680-94, 1986) presented two new lower bounds for K(n,R), where K(n,R) denotes the minimum cardinality of a binary code of length n and covering radius R. The author shows that a slight modification gives further improvements and some examples are given to confirm the argument. Codes that have a certain partitioning property are considered.>

A novel method for constructing normal binary nonlinear covering codes is presented. The construction improves several upper bounds on K(n,R), the minimum cardinality of a binary code of length n and covering radius R.>