## Abstract

We say that an s-subset of codewords of a binary code X is s_{L}-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 s_{L}-LD code) if it does not contain sL-bad subsets of codewords. We consider a probabilistic generalization of s_{L}-LD codes; namely, we say that a code X is an almost disjunctive s_{L}-LD code if the fraction of s_{L}-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 s_{L}-LD codes. For this ensemble, the obtained lower bounds are tight and show that the capacity of almost disjunctive s_{L}-LD codes is greater than the zero-error capacity of disjunctive s_{L}-LD codes.

Original language | English |
---|---|

Article number | A004 |

Pages (from-to) | 110-131 |

Number of pages | 22 |

Journal | Problems of information transmission |

Volume | 51 |

Issue number | 2 |

DOIs | |

Publication status | Published - 1 Apr 2015 |

Externally published | Yes |