Variable-length compression allowing errors

Victoria Kostina, Yury Polyanskiy, Sergio Verdú

Research output: Contribution to journalArticlepeer-review

40 Scopus citations


This paper studies the fundamental limits of the minimum average length of lossless and lossy variable-length compression, allowing a nonzero error probability ε, for lossless compression. We give nonasymptotic bounds on the minimum average length in terms of Erokhin's rate-distortion function and we use those bounds to obtain a Gaussian approximation on the speed of approach to the limit, which is quite accurate for all but small blocklengths: (1 - ε) k H(S) - ((V(S)/2π))1/2 exp[-((Q-1 (ε))2/2)], where Q-1(·) is the functional inverse of the standard Gaussian complementary cumulative distribution function, and V(S) is the source dispersion. A nonzero error probability thus not only reduces the asymptotically achievable rate by a factor of 1 - ε, but this asymptotic limit is approached from below, i.e., larger source dispersions and shorter blocklengths are beneficial. Variable-length lossy compression under an excess distortion constraint is shown to exhibit similar properties.

Original languageEnglish (US)
Article number7115096
Pages (from-to)4316-4330
Number of pages15
JournalIEEE Transactions on Information Theory
Issue number8
StatePublished - Aug 2015

All Science Journal Classification (ASJC) codes

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


  • Shannon theory
  • Variable-length compression
  • dispersion
  • finite-blocklength regime
  • lossless compression
  • lossy compression
  • rate-distortion theory
  • single-shot


Dive into the research topics of 'Variable-length compression allowing errors'. Together they form a unique fingerprint.

Cite this