RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Probl. Peredachi Inf.: Year: Volume: Issue: Page: Find

 Probl. Peredachi Inf., 2015, Volume 51, Issue 2, Pages 27–49 (Mi ppi2168)

Coding Theory

Almost disjunctive list-decoding codes

A. G. D'yachkov, I. V. Vorob'ev, N. A. Polyansky, V. Yu. Shchukin

Probability Theory Chair, Faculty of Mechanics and Mathematics, Lomonosov Moscow State University, Moscow, Russia

Abstract: We say that an $s$-subset of codewords of a binary code $X$ is $s_L$-bad in $X$ if there exists an $L$-subset of other codewords in $X$ whose disjunctive sum is covered by the disjunctive sum of the given $s$ codewords. Otherwise, this $s$-subset of codewords is said to be $s_L$-good in $X$. A binary code $X$ is said to be a list-decoding disjunctive code of strength $s$ and list size $L$ (an $s_L$-LD code) if it does not contain $s_L$-bad subsets of codewords. We consider a probabilistic generalization of $s_L$-LD codes; namely, we say that a code $X$ is an almost disjunctive $s_L$-LD code if the fraction of $s_L$-good subsets of codewords in $X$ is close to 1. Using the random coding method on the ensemble of binary constant-weight codes, we establish lower bounds on the capacity and error exponent of almost disjunctive $s_L$-LD codes. For this ensemble, the obtained lower bounds are tight and show that the capacity of almost disjunctive $s_L$-LD codes is greater than the zero-error capacity of disjunctive $s_L$-LD codes.

Full text: PDF file (334 kB)
References: PDF file   HTML file

English version:
Problems of Information Transmission, 2015, 51:2, 110–131

Bibliographic databases:

UDC: 621.391.15
Revised: 28.01.2015

Citation: A. G. D'yachkov, I. V. Vorob'ev, N. A. Polyansky, V. Yu. Shchukin, “Almost disjunctive list-decoding codes”, Probl. Peredachi Inf., 51:2 (2015), 27–49; Problems Inform. Transmission, 51:2 (2015), 110–131

Citation in format AMSBIB
\Bibitem{DyaVorPol15} \by A.~G.~D'yachkov, I.~V.~Vorob'ev, N.~A.~Polyansky, V.~Yu.~Shchukin \paper Almost disjunctive list-decoding codes \jour Probl. Peredachi Inf. \yr 2015 \vol 51 \issue 2 \pages 27--49 \mathnet{http://mi.mathnet.ru/ppi2168} \elib{http://elibrary.ru/item.asp?id=24959164} \transl \jour Problems Inform. Transmission \yr 2015 \vol 51 \issue 2 \pages 110--131 \crossref{https://doi.org/10.1134/S0032946015020039} \isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000357472800003} \scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84943244613} 

• http://mi.mathnet.ru/eng/ppi2168
• http://mi.mathnet.ru/eng/ppi/v51/i2/p27

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. A. D'yachkov, I. Vorobyev, N. Polyanskii, V. Shehukin, “Hypothesis Test For Upper Bound on the Size of Random Defective Set”, 2017 IEEE International Symposium on Information Theory, ISIT 2017, IEEE, 978–982
2. J. Scarlett, V. Cevher, “How Little Does Non-Exact Recovery Help in Group Testing?”, 2017 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2017, IEEE, 6090–6094
3. N. A. Polyansky, “Almost cover-free codes”, Problems Inform. Transmission, 52:2 (2016), 142–155
4. V. Yu. Shchukin, “List decoding for a multiple access hyperchannel”, Problems Inform. Transmission, 52:4 (2016), 329–343
5. A. G. D'yachkov, I. V. Vorobyev, N. A. Polyanskii, V. Yu. Shchukin, “Symmetric Disjunctive List-Decoding Codes”, Designs Codes Cryptogr., 82:1-2, SI (2017), 211–229
6. A. G. D'yachkov, I. V. Vorobyev, N. A. Polyanskii, V. Yu. Shchukin, “Almost Cover-Free Codes and Designs”, Designs Codes Cryptogr., 82:1-2, SI (2017), 231–247
7. J. Scarlett, V. Cevher, “Near-optimal noisy group testing via separate decoding of items”, IEEE J. Sel. Top. Signal Process., 12:5, SI (2018), 902–915
•  Number of views: This page: 225 Full text: 25 References: 27 First page: 20