Optimal lossless compression: Source varentropy and dispersion

Ioannis Kontoyiannis, Sergio Verdu

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

4 Scopus citations

Abstract

This work1 deals with the fundamental limits of strictly-lossless variable-length compression of known sources without prefix constraints. The source dispersion characterizes the time-horizon over which it is necessary to code in order to approach the entropy rate within a pre-specified tolerance. We show that for a large class of sources, the dispersion of the source is equal to the varentropy rate, defined as the asymptotic per-symbol variance of the information random variables. We focus on ergodic Markov chains, whose optimal encodings are shown to be asymptotically normal and to satisfy an appropriate laws of the iterated logarithm.

Original languageEnglish (US)
Title of host publication2013 IEEE International Symposium on Information Theory, ISIT 2013
Pages1739-1743
Number of pages5
DOIs
StatePublished - Dec 19 2013
Event2013 IEEE International Symposium on Information Theory, ISIT 2013 - Istanbul, Turkey
Duration: Jul 7 2013Jul 12 2013

Publication series

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

Other

Other2013 IEEE International Symposium on Information Theory, ISIT 2013
CountryTurkey
CityIstanbul
Period7/7/137/12/13

All Science Journal Classification (ASJC) codes

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

Fingerprint Dive into the research topics of 'Optimal lossless compression: Source varentropy and dispersion'. Together they form a unique fingerprint.

  • Cite this

    Kontoyiannis, I., & Verdu, S. (2013). Optimal lossless compression: Source varentropy and dispersion. In 2013 IEEE International Symposium on Information Theory, ISIT 2013 (pp. 1739-1743). [6620525] (IEEE International Symposium on Information Theory - Proceedings). https://doi.org/10.1109/ISIT.2013.6620525