Almost disjunctive list-decoding codes

DOI10.1134/S0032946015020039zbMATH Open1339.94085arXiv1407.2482OpenAlexW1600887176MaRDI QIDQ259899FDOQ259899

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)

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.

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

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

Mathematics Subject Classification ID

Linear codes (general theory) (94B05)

Cites Work

• Title not available (Why is that?)
• New bounds for union-free families of sets
• Error probability bounds for two models of randomized design of elimination experiments
• Bounds for error probability for a symmetrical model in designing screening experiments
• Families of finite sets in which no set is covered by the union of two others
• The separating property of random matrices
• Multiple-access hyperchannel
• Bounds on the rate of disjunctive codes
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On a Design Problem for Screening Experiments
• Title not available (Why is that?)
• New constructions of superimposed codes
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Nonrandom binary superimposed codes
• Families of finite sets in which no intersection of \(\ell\) sets is covered by the union of \(s\) others

Cited In (4)

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

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)