A binary matrix is called an${s}$-separable codefor thedisjunctive multiple-access channel(disj-MAC) if Boolean sums of sets of${s}$columns are all distinct. The well-known issue of the combinatorial coding theory is to obtain upper and lower bounds on the rate of${s}$-separable codes for the${disj}$-MAC. In our paper, we generalize the problem and discuss upper and lower bounds on the rate of${q}$-ary${s}$-separable codes for the models of noiselesssymmetricMAC, i.e., at each time instant the output signal of MAC is a symmetric function of its${s}$input signals.

A binary matrix is called an s-separable code for the disjunctive multiple-access channel (disj-MAC) if Boolean sums of sets of$s$columns are all distinct. The well-known issue of the combinatorial coding theory is to obtain upper and lower bounds on the rate of s-separable codes for the disj-MAC. In our paper, we generalize the problem and discuss upper and lower bounds on the rate of q-ary s-separable codes for models of noiseless symmetric MAC, i.e., at each time instant the output signal of MAC is a symmetric function of its$s$input signals.

Let 1 ≤ s0: the circuit is s-active} versus the alternative hypothesis {H1: the circuit is s-defective}. Along with the conventional decoding algorithm based on the known random set of positive responses and disjunctive s-codes, we consider a T-weight decision rule which is based on the simple comparison of a fixed threshold T, 1 ≤ T <; N, with the known random number of positive responses p, 0 ≤ p ≤ N.

Learning a hidden hypergraph is a natural generalization of the classical group testing problem that consists in detecting unknown hypergraph Hun= H(V, E) by carrying out edge-detecting tests. In the given paper we focus our attention only on a specific family F(t, s, ℓ) of localized hypergraphs for which the total number of vertices |V| = t, the number of edges |E| ≤ s, s ≪ t, and the cardinality of any edge |e| ≤ ℓ, ℓ ≪ t. Our goal is to identify all edges of Hun∈ F(t, s, ℓ) by using the minimal number of tests. We develop an adaptive algorithm that matches the information theory bound, i.e., the total number of tests of the algorithm in the worst case is at most sℓ log2t(1+o(1)). We also discuss a probabilistic generalization of the problem.

Group testing is a well known search problem that consists in detecting up to s, s ≪ t, defective elements of the set [t] = {1, . . . , t} by carrying out tests on properly chosen subsets of [t]. In classical group testing the goal is to find all defective elements by using the minimal possible number of tests. In this paper we consider multistage group testing. We propose a general idea how to use a hypergraph approach to searching defective elements. For the case s = 2 and t → ∞, we design an explicit construction, which makes use of 2 log2t(1 + o(1)) tests in the worst case and consists of 4 stages. For the general case of fixed s > 2 and t → ∞, we provide an explicit construction, which uses (2s - 1) log2t(1+o(1)) tests and consists of 2s - 1 rounds.

In this paper, we consider symmetric disjunctive list-decoding (SLD) codes, which are a class of binary codes based on a symmetric disjunctive sum (SDS) of binary symbols. By definition, the SDS takes values from the ternary alphabet {0; 1; *}, where the symbol * denotes “erasure”. Namely: SDS is equal to 0 (1) if all its binary symbols are equal to 0 (1), otherwise SDS is equal to *. The main purpose of this work is to obtain bounds on the rate of these codes.

We discover some important properties of cover-free (CF) codes, separating system (SS) codes and completely separating system (CSS) codes connected with the concept of constant weight CF codes. New upper and lower bounds on the rate of CF and SS codes based on the known results for CF and CSS codes are obtained. Tables of numerical values for the improved upper and lower bounds are presented.

An s-subset of codewords of a binary code X is said to be (s, ℓ)-bad in X if the code X contains a subset of other ℓ codewords such that the conjunction of the ℓ codewords is covered by the disjunctive sum of the s codewords. Otherwise, the s-subset of codewords of X is called (s, ℓ)-good in X. A binary code X is said to be a cover-free (CF) (s, ℓ)-code if the code X does not contain (s, ℓ)-bad subsets. In this paper, we introduce a natural probabilistic generalization of CF (s, ℓ)-codes, namely: a binary code X is said to be an almost CF (s, ℓ)-code if the relative number of its (s, ℓ)-good s-subsets is close to 1. We develop a random coding method based on the ensemble of binary constant weight codes to obtain lower bounds on the capacity of such codes. Our main result shows that the capacity for almost CF (s, ℓ)-codes is essentially greater than the rate for ordinary CF (s, ℓ)-codes.

A binary code is called a superimposed cover-free (s, ℓ)-code if the code is identified by the incidence matrix of a family of finite sets in which no intersection of ℓ sets is covered by the union of s others. A binary code is called a superimposed list-decoding sL-code if the code is identified by the incidence matrix of a family of finite sets in which the union of any s sets can cover not more than L - 1 other sets of the family. For L = ℓ = 1, both of the definitions coincide and the corresponding binary code is called a superimposed s-code. Our aim is to obtain new lower and upper bounds on the rate of the given codes. The most interesting result is a lower bound on the rate of superimposed cover-free (s, ℓ)-codes based on the ensemble of constant weight binary codes. If the parameter ℓ ≥ 1 is fixed and s → ∞, then the ratio of this lower bound to the best known upper bound converges to the limit 2 e-2= 0.271. For the classical case ℓ = 1 and s ≥ 2, the given statement means that the upper bound on the rate of superimposed s-codes obtained by A.G. Dyachkov and V.V. Rykov (1982) is asymptotically attained to within a constant factor a, 2 e-2≤ a ≤ 1.

The concept of a generalized stem similarity function and the corresponding DNA codes are introduced. We give parameters for some optimal constructions called maximum distance separable DNA codes and obtain bounds on the maximum size of DNA codes.

We consider DNA codes based on the nearest-neighbor (stem) similarity model which adequately reflects the “hybridization potential” of two DNA sequences. Our aim is to present a survey of bounds on the rate of DNA codes with respect to a thermodynamically motivated similarity measure called an additive stem similarity. These results yield a method to analyze and compare known samples of the nearest neighbor “thermo-dynamic weights” associated to stacked pairs that occurred in DNA secondary structures.

We consider DNA codes based on the concept of a weighted 2-stem similarity measure which reflects the ldquohybridization potentialrdquo of two DNA sequences. A random coding bound on the rate of DNA codes with respect to a thermodynamic motivated similarity measure is proved. Ensembles of DNA strands whose sequence composition is restricted in a manner similar to the restrictions in binary Fibonacci sequences are introduced to obtain the bound.

For q-ary n-sequences, we develop the concept of similarity functions that can be used (for q = 4) to model a thermodynamic similarity on DNA sequences. A similarity function is identified by the length of a longest common subsequence between two q-ary n-sequences. Codes based on similarity functions are called DNA codes. DNA codes are important components in biomolecular computing and other biotechnical applications that employ DNA hybridization assays. We present our unpublished results connected with the conventional deletion similarity function used in the theory of error-correcting codes. The main aim of this paper - to obtain lower bounds on the rate of optimal DNA codes for a biologically motivated similarity function called a similarity of blocks. We also present constructions of suboptimal DNA codes based on the parity-check code detecting one error in the Hamming metric

We introduce the distance concept between two q-ary n-sequences, 2/spl les/q

Kautz-Singleton (1964) suggested a class of binary superimposed codes which are based on the q-ary Reed-Solomon codes (RS codes). Applying a concatenation of the binary constant-weight error-correcting codes and the shortened RS codes, we obtain new constructions of superimposed codes. Tables of their parameters are given. From the tables it follows that the rate of obtained codes exceeds the corresponding random coding bound.

We introduce a biologically motivated measure of sequence similarity for quaternary N-sequences, extending Hamming similarity. This measure is the sum over the length of the sequences of "alphabetic" similarities at all positions. Alphabetic similarities are defined, symmetrically, on the Cartesian square of the alphabet. These similarities equal zero whenever the two elements differ. In distinction to Hamming similarity, however, our alphabetic similarities take individual values whenever the two elements are identical. In this correspondence we derive lower and upper bounds on the rate of the corresponding quaternary nonlinear and linear codes called similarity codes and applied to DNA sequences.