Feedback in the non-asymptotic regime

Yury Polyanskiy, H. Vincent Poor, Sergio Verdu

Research output: Contribution to journalArticlepeer-review

120 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 and 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 code (even with noiseless feedback). Virtually all the advantages of noiseless feedback are shown to be achievable, even if the feedback link is used only to send a single signal informing the encoder to terminate the transmission (stop-feedback). 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. Fixed-blocklength codes and related questions concerning communicating with a guaranteed delay are discussed, in which situation feedback is demonstrated to be almost useless even non-asymptotically.

Original languageEnglish (US)
Article number5961844
Pages (from-to)4903-4925
Number of pages23
JournalIEEE Transactions on Information Theory
Volume57
Issue number8
DOIs
StatePublished - Aug 1 2011

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Keywords

  • Achievability bounds
  • Shannon theory
  • channel capacity
  • converse bounds
  • feedback
  • memoryless channels
  • non-asymptotic analysis
  • stop-feedback

Fingerprint Dive into the research topics of 'Feedback in the non-asymptotic regime'. Together they form a unique fingerprint.

Cite this