A new upper bound on the cardinality of codes in the Hamming space with given minimum and maximum distances is proved. The bound is compared to some known bounds, and some classes of codes for which the new bound is tight are given

Traditional problems of coding theory consist of finding, for a given graph (in particular, for the Hamming and Johnson graphs), a maximum subset of vertices whose metric balls of a given radius do not intersect and a minimum subset of vertices whose metric balls of a given radius cover all vertices of the graph. In the paper another problem formulated in terms of metric balls of vertices is considered. We investigate conditions under which an unknown graph can be uniquely reconstructible if metric balls of a given radius around each vertex are known

We consider the problem to construct a code of the maximum cardinality which consists of binary vectors of length n with three ones and has the following property: a matrix of size 3 times n from any cyclic shifts of any three different code vectors contains the identity matrix of size 3 times 3 (with accuracy up to a permutation of columns). This property (in more general form) was considered in the connection with the problem to avoid conflicts in the channels of multiple access under a restriction to the number of active users (see L. A. Bassalygo and M. S. Pinsker, Problemy Peredachi Informatsii, 1983; J. L. Massey and P. Mathys, IEEE Trans. Inform. Theory , 1985; B.S. Tsybakov and A.R. Rubinov, Problems of Information Transmission , 2002). The cardinality of such a code corresponds to the number of all users, and this property means that each from any three active users can successfully transmit a packet of information in one of three attempts to do it during n slots of time without a collision with other active users. In particular, cyclic Steiner triple systems give examples of such conflict-avoiding codes if we choose representatives of the cyclic classes as code vectors. In the paper we present some constructions of conflict-avoiding codes of triples which are better as compared with those obtained from the cyclic Steiner triple systems

The monotone structure of correctable and uncorrectable errors given by the complete decoding for a binary linear code is investigated. New bounds on the error-correction capability of linear codes beyond half the minimum distance are presented, both for the best codes and for arbitrary codes under some restrictions on their parameters. It is proved that some known codes of low rate are as good as the best codes in an asymptotic sense.

It is known that polynomials f(t), such that the matrix f(rho(x,y)) with the Hamming distance rho(x,y) between vectors x=(x1,...,xn) and y=(y1,...,yn) is nonnegative definite, are described with the help of the system of Krawtchouk polynomials. In the paper the question on the existence of a similar system of polynomials is considered when the function rho(x,y) is not the Hamming distance

The probability of correct decoding on the binary-symmetric channel is studied. In particular, a class of codes with the same lengths and dimensions as the linear simplex codes, but with larger probability of correct decoding for all parameters p, 0 < p < 1/2, is given.

The number of cosets of weight 2/sup k-2/ or less are determined for the [2/sup k/-1, k, 2/sup k-1/] simplex code and a [2/sup k/-1, k, 2/sup k-1/-1] code obtained by a simple modification of the simplex code. The result proves that the [2/sup k/-1, k] simplex codes are not optimal for error correction on the binary symmetric channel with small bit error probability, p, (for k/spl ges/3). A proof that the modified code is better for all p, 0<p<1/2, is sketched.

We adapt methods originally developed in information and coding theory to solve some testing problems. The efficiency of two-stage pool testing of n items is characterized by the minimum expected number E(n, p) of tests for the Bernoulli p-scheme, where the minimum is taken over a matrix that specifies the tests that constitute the first stage. An information-theoretic bound implies that the natural desire to achieve E(n, p) = o(n) as n /spl rarr/ /spl infin/ can be satisfied only if p(n) /spl rarr/ 0. Using random selection and linear programming, we bound some parameters of binary matrices, thereby determining up to positive constants how the asymptotic behavior of E(n, p) as n /spl rarr/ /spl infin/ depends on the manner in which p(n) /spl rarr/ 0. In particular, it is shown that for p(n) = n/sup -/spl beta/+o(1)/, where 0 < /spl beta/ < 1, the asymptotic efficiency of two-stage procedures cannot be improved upon by generalizing to the class of all multistage adaptive testing algorithms.

We introduce and solve some new problems of efficient reconstruction of an unknown sequence from its versions distorted by errors of a certain type. These erroneous versions are considered as outputs of repeated transmissions over a channel, either a combinatorial channel defined by the maximum number of permissible errors of a given type, or a discrete memoryless channel. We are interested in the smallest N such that N erroneous versions always suffice to reconstruct a sequence of length n, either exactly or with a preset accuracy and/or with a given probability. We are also interested in simple reconstruction algorithms. Complete solutions for combinatorial channels with some types of errors of interest in coding theory, namely, substitutions, transpositions, deletions, and insertions of symbols are given. For these cases, simple reconstruction algorithms based on majority and threshold principles and their nontrivial combination are found. In general, for combinatorial channels the considered problem is reduced to a new problem of reconstructing a vertex of an arbitrary graph with the help of the minimum number of vertices in its metrical ball of a given radius. A certain sufficient condition for solution of this problem is presented. For a discrete memoryless channel, the asymptotic behavior of the minimum number of repeated transmissions which are sufficient to reconstruct any sequence of length n within Hamming distance d with error probability /spl epsiv/ is found when d/n and /spl epsiv/ tend to 0 as n/spl rarr//spl infin/. A similar result for the continuous channel with discrete time and additive Gaussian noise is also obtained.

For the minimum aperiodic crosscorrelation /spl theta/(n,M) of binary codes of size M and length n over the alphabet {1,-1} there exists the celebrated Welch bound /spl theta//sup 2/(n,M)/spl ges/(M-1)n/sup 2//2Mn-N-1 which was published in 1974 and remained in this form up to now. In the article this bound is strengthened for all M/spl ges/4 and n/spl ges/2. In particular, it is proved that /spl theta//sup 2/(n,M)/spl ges/n-2n//spl radic/3M, M/spl ges/3 and /spl theta//sup 2/(n,M)/spl ges/n-[/spl pi/n//spl radic/8M], M/spl ges/5. In the asymptotic process when M tends to infinity as n/spl rarr//spl infin/, these bounds are twice as large as the Welch bound and coincide with the corresponding asymptotic bound on the square of the minimum periodic crosscorrelation of binary codes. The main idea of the proof is a new sufficient condition for the mean value of a nonnegative definite matrix over the code to be greater than or equal to the average over the whole space. This allows one to take into account weights of cyclic shifts of code vectors and solve the problem of their optimal choice.

This paper contains a survey of association scheme theory (with its algebraic and analytical aspects) and of its applications to coding theory (in a wide sense). It is mainly concerned with a class of subjects that involve the central notion of the distance distribution of a code. Special emphasis is put on the linear programming method, inspired by the MacWilliams transform. This produces upper bounds for the size of a code with a given minimum distance, and lower bounds for the size of a design with a given strength. The most specific results are obtained in the case where the underlying association scheme satisfies certain well-defined "polynomial properties;" this leads one into the realm of orthogonal polynomial theory. In particular, some "universal bounds" are derived for codes and designs in polynomial type association schemes. Throughout the paper, the main concepts, methods, and results are illustrated by two examples that are of major significance in classical coding theory, namely, the Hamming scheme and the Johnson scheme. Other topics that receive special attention are spherical codes and designs, and additive codes in translation schemes, including Z/sub 4/-additive binary codes.

The information function e/sub h/ of a code is the average amount of information contained in h positions of the codewords. Upper and lower bounds on the information function of binary linear codes are given. The average value and variance of the information function over all [n, k] codes are determined,.

The minimum support weight, d/sub r/(C), of a linear code C over GF(q) is the minimal size of the support of an r-dimensional subcode of C. A number of bounds on d/sub r/(C) are derived, generalizing the Plotkin bound and the Griesmer bound, as well as giving two new existential bounds. As the main result, it is shown that there exist codes of any given rate R whose ratio d/sub rd/sub 1/ is lower bounded by a number ranging from (q/sup r/-1)/(q/sup r/-q/sup r-1/) to r, depending on R.>

Universal bounds for the cardinality of codes in the Hamming space F/sub r//sup n/ with a given minimum distance d and/or dual distance d' are stated. A self-contained proof of optimality of these bounds in the framework of the linear programming method is given. The necessary and sufficient conditions for attainability of the bounds are found. The parameters of codes satisfying these conditions are presented in a table. A new upper bound for the minimum distance of self-dual codes and a new lower bound for the crosscorrelation of half-linear codes are obtained.>

We consider the problem of simultaneous identification and transmission of information by means of superimposed codes. It is assumed that a total population of T users share a common channel. At each time at most in of the T users are active. The output from the channel is the modulo-2 sum of the binary codewords transmitted by the active users, possibly disturbed by errors. A superimposed code is actually a set of codes-one for each user-designed in such a way that both the (at most) m active users and their messages can be identified, even in the presence of a permissible number of errors in the channel. We give several explicit constructions for superimposed codes and analyze in detail their performance. In several of the cases under study we offer codes that are proved to be best possible.>

Codes for the multibit peak-shift recording channel, called (d,k)-codes of reduced length N, are considered. Arbitrary (d,k)- and perfect (d,k)-codes capable of correcting single peak-shifts of given size t are defined. For the construction of perfect codes, a general combinatorial method connected with finding 'good' weight sequences in Abelian groups is used, and the concept of perfect t-shift N-designs is introduced. Explicit constructions of such designs for t=1, t=2, and t=(p-1)/2 are given, where p is a prime. This construction is universal in that it does not depend on the (d,k)-constraints. It also allows automatic correction of those peak-shifts that violate (d,k)-constraints. The construction is extended to (d,k)-codes of fixed binary length and allows the beginning of the next codeword to be determined. The question whether the designed codes can be represented as systematic codes with minimal redundancy is considered as well.>