Almost disjunctive list-decoding codes

DOI10.1134/S0032946015020039MaRDI QIDQ259899zbMATH OpenOpenAlexFDO

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

Publication date 18 March 2016

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

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

Mathematics Subject Classification ID

Linear codes (general theory) (94B05)

Abstract: A binary code is said to be a disjunctive list-decoding $s_L$-code, $sge1$, $Lge1$, (briefly, LD $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. In this paper, we introduce a natural {em probabilistic} generalization of LD $s_L$-code when the code is said to be an almost disjunctive LD $s_L$-code if the unions of {em almost all} $s$ sets satisfy the given condition. We develop a random coding method based on the ensemble of binary constant-weight codes to obtain lower bounds on the capacity and error probability exponent of such codes. For the considered ensemble our lower bounds are asymptotically tight.

Recommendations

• Symmetric disjunctive list-decoding codes
• List decoding algorithms for certain concatenated codes
• List-Decoding Algorithms for Lifted Codes
• List Decodability of Symbol-Pair Codes
• Algebraic List-Decoding of Subspace Codes
• List-decoding multiplicity codes
• scientific article; zbMATH DE number 1759459
• List-decoding homomorphism codes with arbitrary codomains
• List decoding of algebraic-geometric codes
• scientific article; zbMATH DE number 7561729

Cites work

• 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 3908323 (Why is no real title available?)
• scientific article; zbMATH DE number 3670354 (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 3316587 (Why is no real title available?)
• Bounds for error probability for a symmetrical model in designing screening experiments
• Bounds on the rate of disjunctive codes
• Error probability bounds for two models of randomized design of elimination experiments
• Families of finite sets in which no intersection of \(\ell\) sets is covered by the union of \(s\) others
• Families of finite sets in which no set is covered by the union of two others
• Multiple-access hyperchannel
• New bounds for union-free families of sets
• New constructions of superimposed codes
• Nonrandom binary superimposed codes
• On a Design Problem for Screening Experiments
• The separating property of random matrices

Cited in

(4)

• Symmetric disjunctive list-decoding codes
• Simplified High-Speed High-Distance List Decoding for Alternant Codes
• Almost cover-free codes
• List decoding for a multiple access hyperchannel

This page was built for publication: Almost disjunctive list-decoding codes

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