Second-order capacities of erasure and list decoding

Vincent Y.F. Tan, Pierre Moulin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We derive the second-order capacities (supremum of second-order coding rates) for erasure and list decoding. Fpor erasure decoding, we show that second-order capacity is √VΦ-1t) where V is the channel dispersion and (εt is the total error probability, i.e. the sum of the erasure and undetected errors. We show numerically that the expected rate at finite blocklength for erasures decoding can exceed the finite blocklength channel coding rate. For list decoding, we consider list codes of deterministic size 2√nl and show that the second-order capacity is l+ √VΦ-1(ε) where ε is the permissible error probability. Both coding schemes use the threshold decoder and converses are proved using variants of the meta-converse.

Original languageEnglish (US)
Title of host publication2014 IEEE International Symposium on Information Theory, ISIT 2014
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1887-1891
Number of pages5
ISBN (Print)9781479951864
DOIs
StatePublished - Jan 1 2014
Event2014 IEEE International Symposium on Information Theory, ISIT 2014 - Honolulu, HI, United States
Duration: Jun 29 2014Jul 4 2014

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8095

Other

Other2014 IEEE International Symposium on Information Theory, ISIT 2014
CountryUnited States
CityHonolulu, HI
Period6/29/147/4/14

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Second-order capacities of erasure and list decoding'. Together they form a unique fingerprint.

  • Cite this

    Tan, V. Y. F., & Moulin, P. (2014). Second-order capacities of erasure and list decoding. In 2014 IEEE International Symposium on Information Theory, ISIT 2014 (pp. 1887-1891). [6875161] (IEEE International Symposium on Information Theory - Proceedings). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT.2014.6875161