2014/10/30 by A.G. D'yachkov, Arkadii D'yachkov, D'yachkov, Arkadii +7
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · Mathematics · #DNA and Biological Computing #Limits and Structures in Graph Theory #cs.IT #graph theory and CDMA systems #math.IT
paper · pdf · doi:10.48550/arxiv.1410.8566
18 pages, conference paper
arxiv created 2015/03/25 · arxiv updated 2015/03/26
An s-subset of codewords of a binary code X is said to be an \em (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 said to be an \em (s,ℓ)-good in~X.mA binary code X is said to be a cover-free (s,ℓ)-code if the code X does not contain (s,ℓ)-bad subsets. In this paper, we introduce a natural \em probabilistic generalization of cover-free (s,ℓ)-codes, namely: a binary code is said to be an almost cover-free (s,ℓ)-code if \em almost all s-subsets of its codewords are (s,ℓ)-good. We discuss the concept of almost cover-free (s,ℓ)-codes arising in combinatorial group testing problems connected with the nonadaptive search of defective supersets (complexes). 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.