Almost Cover-Free Codes and Designs

Abstract

An $s$-subset of codewords of a binary code $X$ is said to be an {\em $(s,\ell )$-bad} in $X$ if the code $X$ contains a subset of other $\ell$ codewords such that the conjunction of the $\ell$ 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,\ell )$-good} in~$X$.mA binary code $X$ is said to be a cover-free $(s,\ell )$-code if the code $X$ does not contain $(s,\ell )$-bad subsets. In this paper, we introduce a natural {\em probabilistic} generalization of cover-free $(s,\ell )$-codes, namely: a binary code is said to be an almost cover-free $(s,\ell )$-code if {\em almost all} $s$-subsets of its codewords are $(s,\ell )$-good. We discuss the concept of almost cover-free $(s,\ell )$-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.

18 pages, conference paper