Bounds on the rate of superimposed codes

• Published in: arXiv.org 2016-05
• Main Authors: D'yachkov, Arkady, Vorobyev, Ilya, Polianskii, Nikita, Shchukin, Vladislav
• Format: Article
• Language: English
• Subjects: Binary codes; Binary system; Codes; Decoding; Incidence; Lower bounds; Upper bounds; Weight
• ISSN: 2331-8422
• DOI: 10.48550/arxiv.1401.0050

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 given codes. The most interesting result is a lower bound on the rate of superimposed cover-free \((s,\ell)\)-code based on the ensemble of constant-weight binary codes. If parameter \(\ell\ge1\) is fixed and \(s\to\infty\), 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 \(\ell=1\) and \(s\ge2\), the given Statement means that our recurrent upper bound on the rate of superimposed \(s\)-codes obtained in 1982 is attained to within a constant factor \(a\), \(0,271\le a\le1\)