Almost disjunctive list-decoding codes

A. G. D’Yachkov, I. V. Vorob’Ev, N. A. Polyansky, V. Yu Shchukin

Research output: Contribution to journalArticlepeer-review

8 Citations (Scopus)


We say that an s-subset of codewords of a binary code X is sL-bad in X if there exists an L-subset of other codewords in X whose disjunctive sum is covered by the disjunctive sum of the given s codewords. Otherwise, this s-subset of codewords is said to be L-good in X. A binary code X is said to be a list-decoding disjunctive code of strength s and list size L (an sL-LD code) if it does not contain sL-bad subsets of codewords. We consider a probabilistic generalization of sL-LD codes; namely, we say that a code X is an almost disjunctive sL-LD code if the fraction of sL-good subsets of codewords in X is close to 1. Using the random coding method on the ensemble of binary constant-weight codes, we establish lower bounds on the capacity and error exponent of almost disjunctive sL-LD codes. For this ensemble, the obtained lower bounds are tight and show that the capacity of almost disjunctive sL-LD codes is greater than the zero-error capacity of disjunctive sL-LD codes.

Original languageEnglish
Article numberA004
Pages (from-to)110-131
Number of pages22
JournalProblems of information transmission
Issue number2
Publication statusPublished - 1 Apr 2015
Externally publishedYes


Dive into the research topics of 'Almost disjunctive list-decoding codes'. Together they form a unique fingerprint.

Cite this