Variable-length coding with feedback in the non-asymptotic regime

Yury Polyanskiy, H. Vincent Poor, Sergio Verdú

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

11 Scopus citations

Abstract

Without feedback, the backoff from capacity due to non-asymptotic blocklength can be quite substantial for blocklengths and error probabilities of interest in many practical applications. In this paper, novel achievability bounds are used to demonstrate that in the non-asymptotic regime, the maximal achievable rate improves dramatically thanks to variable-length coding with feedback. For example, for the binary symmetric channel with capacity 1/2 the blocklength required to achieve 90% of the capacity is smaller than 200, compared to at least 3100 for the best fixed-blocklength, non-feedback code. Virtually all the advantages of noiseless feedback are shown to be achievable with decision-feedback only. It is demonstrated that the non-asymptotic behavior of the fundamental limit depends crucially on the particular model chosen for the "end-of-packet" control signal.

Original languageEnglish (US)
Title of host publication2010 IEEE International Symposium on Information Theory, ISIT 2010 - Proceedings
Pages231-235
Number of pages5
DOIs
StatePublished - Aug 23 2010
Event2010 IEEE International Symposium on Information Theory, ISIT 2010 - Austin, TX, United States
Duration: Jun 13 2010Jun 18 2010

Publication series

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

Other

Other2010 IEEE International Symposium on Information Theory, ISIT 2010
CountryUnited States
CityAustin, TX
Period6/13/106/18/10

All Science Journal Classification (ASJC) codes

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

Keywords

  • Achievability bounds
  • Channel capacity
  • Decision feedback
  • Feedback
  • Memoryless channels
  • Non-asymptotic analysis
  • Shannon theory

Fingerprint Dive into the research topics of 'Variable-length coding with feedback in the non-asymptotic regime'. Together they form a unique fingerprint.

  • Cite this

    Polyanskiy, Y., Poor, H. V., & Verdú, S. (2010). Variable-length coding with feedback in the non-asymptotic regime. In 2010 IEEE International Symposium on Information Theory, ISIT 2010 - Proceedings (pp. 231-235). [5513238] (IEEE International Symposium on Information Theory - Proceedings). https://doi.org/10.1109/ISIT.2010.5513238