Bounds on the rate of disjunctive codes (in Russian)

Abstract

A binary code is called a superimposed cover-free $(s,\ell )$-code if the code is identified by the incidence matrix of a family of finite sets in which no intersection of $\ell$ sets is covered by the union of $s$ others. A binary code is called a superimposed list-decoding $s_L$-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. For $L=\ell =1$, both of the definitions coincide and the corresponding binary code is called a superimposed $s$-code. Our aim is to obtain new lower and upper bounds on the rate of the given codes. In particular, we derive lower bounds on the rates of a superimposed cover-free $(s,\ell )$-code and list-decoding $s_L$-code based on the ensemble of constant weight binary codes. Also, we establish an upper bound on the rate of superimposed list-decoding $s_L$-code.

36 pages, Original Russian Text published in Problemy Peredachi Informatsii, 2014, Vol. 50, No. 1, pp. 31-63