Almost Cover-Free Codes and Designs

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\)-subs...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2015-03
Main Authors: D'yachkov, Arkadii, Vorobyev, Ilya, Polyanskii, Nikita, Shchukin, Vladislav
Format: Article
Language:English
Subjects:
Binary codes
Binary system
Codes
Combinatorial analysis
Lower bounds
Weight
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422