Bounds on the rate of superimposed codes
A.G. D'yachkov, Ilya Vorobyev, Nikita Polyanskii, V. Yu. Shchukin · 2014
A binary code is called a superimposed cover-free (s, ℓ)-code if the code is identified by the incidence matrix of a family of finite sets in which no intersection of ℓ sets is covered by the union of s others. A binary code is called a superimposed list-decoding 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. For L = ℓ = 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. The most interesting result is a lower bound on the rate of superimposed cover-free (s, ℓ)-codes based on the ensemble of constant weight binary codes. If the parameter ℓ ≥ 1 is fixed and s → ∞, then the ratio of this lower bound to the best known upper bound converges to the limit 2 e-2= 0.271. For the classical case ℓ = 1 and s ≥ 2, the given statement means that the upper bound on the rate of superimposed s-codes obtained by A.G. Dyachkov and V.V. Rykov (1982) is asymptotically attained to within a constant factor a, 2 e-2≤ a ≤ 1.