Bounds on the rate of disjunctive codes

DOI10.1134/S0032946014010037MaRDI QIDQ2262991zbMATH OpenOpenAlexFDO

Authors Nikita Polyanskii, V. Yu. Shchukin, Arkadii G. D'yachkov, I. V. Vorob'ev

Publication date 17 March 2015

Published in Problems of Information Transmission (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.0050

zbMATH Keywords

disjunctive \((s,\ell)\) cover-free codes

Mathematics Subject Classification ID

Linear codes (general theory) (94B05) Bounds on codes (94B65)

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 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 $ellge1$ is fixed and $soinfty$, 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 $sge2$, 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,271leale1$

Recommendations

• Bounds on the rate of separating codes
• Erratum to: ``Bounds on the rate of disjunctive codes
• scientific article; zbMATH DE number 1803256
• Random coding bounds for discrete memoryless channels
• A new upper bound on the rate of non-binary codes
• Improved upper bounds for the rate of separating and completely separating codes
• Upper Bounds on Separating Codes
• Threshold Rates for Properties of Random Codes
• Bounds on Separating Redundancy of Linear Codes and Rates of X-Codes
• LATIN 2004: Theoretical Informatics

Cites work

• Asymptotic upper bound for the rate of \((w,r)\) cover-free codes
• Bounds on the average error probability for a code ensemble with fixed composition
• Families of finite sets in which no intersection of sets is covered by the union of s others
• scientific article; zbMATH DE number 3831842 (Why is no real title available?)
• scientific article; zbMATH DE number 4135867 (Why is no real title available?)
• scientific article; zbMATH DE number 4162826 (Why is no real title available?)
• scientific article; zbMATH DE number 3902553 (Why is no real title available?)
• scientific article; zbMATH DE number 3908323 (Why is no real title available?)
• scientific article; zbMATH DE number 4064918 (Why is no real title available?)
• scientific article; zbMATH DE number 1498831 (Why is no real title available?)
• scientific article; zbMATH DE number 2154117 (Why is no real title available?)
• scientific article; zbMATH DE number 3801449 (Why is no real title available?)
• scientific article; zbMATH DE number 1420996 (Why is no real title available?)
• scientific article; zbMATH DE number 3242947 (Why is no real title available?)
• Interval packing and covering in the Boolean lattice
• Key storage in secure networks
• New bounds for union-free families of sets
• New constructions of superimposed codes
• Nonadaptive algorithms for threshold group testing
• Nonrandom binary superimposed codes
• On optimal superimposed codes
• On the construction of \((w,r)\) cover-free codes
• Some new bounds for cover-free families
• Superimposed codes and threshold group testing

Cited in

(19)

• Bounds on the rate of separating codes
• Separable collusion-secure multimedia codes
• Low-weight superimposed codes and related combinatorial structures: bounds and applications
• Sampling schemes and recovery algorithms for functions of few coordinate variables
• List decoding for a multiple access hyperchannel
• Almost cover-free codes
• Erratum to: ``Bounds on the rate of disjunctive codes
• Strict group testing and the set basis problem
• Almost disjunctive list-decoding codes
• Lower bounds for cover-free families
• Exact learning from an honest teacher that answers membership queries
• Cover-free codes and separating system codes
• Symmetric disjunctive list-decoding codes
• Almost cover-free codes and designs
• Almost separable matrices
• Almost optimal cover-free families
• A new kind of selectors and their applications to conflict resolution in wireless multichannels networks
• scientific article; zbMATH DE number 7765404 (Why is no real title available?)
• A survey of cover-free families: constructions, applications, and generalizations

This page was built for publication: Bounds on the rate of disjunctive codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2262991)