2014/07/09 by A. G. Dyachkov, I. V. Vorobyev, Dyachkov, A. G. +5 · 1 citation
Computer Science · Mathematics · #FOS: Computer and information sciences #Information Theory (cs.IT) #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.1407.2482
17 pages, 1 table
arxiv created 2014/07/09 · arxiv updated 2014/07/10
A binary code is said to be a disjunctive list-decoding sL-code, s≥1, L≥1, (briefly, LD sL-code) if the code is identified by the incidence matrix of a family of finite sets in which the union of any s sets can cover not more than L-1 other sets of the family. In this paper, we introduce a natural \em probabilistic generalization of LD sL-code when the code is said to be an almost disjunctive LD sL-code if the unions of \em almost all s sets satisfy the given condition. We develop a random coding method based on the ensemble of binary constant-weight codes to obtain lower bounds on the capacity and error probability exponent of such codes. For the considered ensemble our lower bounds are asymptotically tight.