Almost cover-free codes

N. A. Polyansky

Research output: Contribution to journalArticlepeer-review


We say that an s-subset of codewords of a code X is (s, l)-bad if X contains l other codewords such that the conjunction of these l words is covered by the disjunction of the words of the s-subset. Otherwise, an s-subset of codewords of X is said to be (s, l)-bad. A binary code X is called a disjunctive (s, l) cover-free (CF) code if X does not contain (s, l)-bad subsets. We consider a probabilistic generalization of (s, l) CF codes: we say that a binary code is an (s, l) almost cover-free (ACF) code if almost all s-subsets of its codewords are (s, l)-good. The most interesting result is the proof of a lower and an upper bound for the capacity of (s, l) ACF codes; the ratio of these bounds tends as s→∞ to the limit value log2e/(le).

Original languageEnglish
Pages (from-to)142-155
Number of pages14
JournalProblems of information transmission
Issue number2
Publication statusPublished - 1 Apr 2016
Externally publishedYes


Dive into the research topics of 'Almost cover-free codes'. Together they form a unique fingerprint.

Cite this