General information
Latest issue
Impact factor

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Probl. Peredachi Inf.:

Personal entry:
Save password
Forgotten password?

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

This article is cited in 7 scientific papers (total in 7 papers)

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
Received: 16.09.2014
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
\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
\jour Problems Inform. Transmission
\yr 2015
\vol 51
\issue 2
\pages 110--131

Linking options:

    SHARE: FaceBook Twitter Livejournal

    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  isi
    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  isi
    3. N. A. Polyansky, “Almost cover-free codes”, Problems Inform. Transmission, 52:2 (2016), 142–155  mathnet  crossref  mathscinet  isi  elib  elib
    4. V. Yu. Shchukin, “List decoding for a multiple access hyperchannel”, Problems Inform. Transmission, 52:4 (2016), 329–343  mathnet  crossref  isi  elib
    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  crossref  mathscinet  zmath  isi  scopus
    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  crossref  mathscinet  zmath  isi  scopus
    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  crossref  isi  scopus
  • Проблемы передачи информации Problems of Information Transmission
    Number of views:
    This page:219
    Full text:24
    First page:20

    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020