This paper introduces a problem in additive number theory which is motivated by optimization of hardware implementation of QC-LDPC codes. For a fixed subset S, S ⊂ℤq, of residue classes modulo q the object of interest is a basis set G, G ⊂ℤq, of minimal size, such that every element of S is representable as a sum of several elements from G. For a fixed number k, k ≤⌈log2q⌉, the object of interest is a function ζ(q,k) defined as a maximum number such that, for every set of cardinality <; ζ(q,k), there exists a basis set of cardinality <; k.

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.