Bounds on the rate of disjunctive codes
A. G. D’yachkov, I. V. Vorob’ev, N. A. Polyansky, V. Yu. Shchukin · Problems of Information Transmission · 2014
A binary code is said to be a disjunctive (s, ℓ) cover-free code if it is an incidence matrix of a family of sets where the intersection of any ℓ sets is not covered by the union of any other s sets of this family. A binary code is said to be a list-decoding disjunctive of strength s with list size L if it is an incidence matrix of a family of sets where the union of any s sets can cover no more that L − 1 other sets of this family. For L = ℓ = 1, both definitions coincide, and the corresponding binary code is called a disjunctive s-code. This paper is aimed at improving previously known and obtaining new bounds on the rate of these codes. The most interesting of the new results is a lower bound on the rate of disjunctive (s, ℓ) cover-free codes obtained by random coding over the ensemble of binary constant-weight codes; its ratio to the best known upper bound converges as s → ∞, with an arbitrary fixed ℓ ≥ 1, to the limit 2e −2 = 0.271 ... In the classical case of ℓ = 1, this means that the upper bound on the rate of disjunctive s-codes constructed in 1982 by D’yachkov and Rykov is asymptotically attained up to a constant factor a, 2e −2 ≤ a ≤ 1.