Optimal lossless compression: Source varentropy and dispersion

Ioannis Kontoyiannis; Sergio Verdu

doi:10.1109/ISIT.2013.6620525

Optimal lossless compression: Source varentropy and dispersion

Ioannis Kontoyiannis, Sergio Verdu

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

15 Scopus citations

Abstract

This work¹ 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 language	English (US)
Title of host publication	2013 IEEE International Symposium on Information Theory, ISIT 2013
Pages	1739-1743
Number of pages	5
DOIs	https://doi.org/10.1109/ISIT.2013.6620525
State	Published - 2013
Event	2013 IEEE International Symposium on Information Theory, ISIT 2013 - Istanbul, Turkey Duration: Jul 7 2013 → Jul 12 2013

Publication series

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

Other

Other	2013 IEEE International Symposium on Information Theory, ISIT 2013
Country/Territory	Turkey
City	Istanbul
Period	7/7/13 → 7/12/13

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Information Systems
Applied Mathematics
Modeling and Simulation

Keywords

Lossless data compression
Markov sources
entropy rate
fundamental limits
minimal source coding rate
source coding

Access to Document

10.1109/ISIT.2013.6620525

Cite this

@inproceedings{1c6f5580ecb44c0ba61de95c34fa7036,

title = "Optimal lossless compression: Source varentropy and dispersion",

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.",

keywords = "Lossless data compression, Markov sources, entropy rate, fundamental limits, minimal source coding rate, source coding",

author = "Ioannis Kontoyiannis and Sergio Verdu",

year = "2013",

doi = "10.1109/ISIT.2013.6620525",

language = "English (US)",

isbn = "9781479904464",

series = "IEEE International Symposium on Information Theory - Proceedings",

pages = "1739--1743",

booktitle = "2013 IEEE International Symposium on Information Theory, ISIT 2013",

note = "2013 IEEE International Symposium on Information Theory, ISIT 2013 ; Conference date: 07-07-2013 Through 12-07-2013",

}

Kontoyiannis, I & Verdu, S 2013, Optimal lossless compression: Source varentropy and dispersion. in 2013 IEEE International Symposium on Information Theory, ISIT 2013., 6620525, IEEE International Symposium on Information Theory - Proceedings, pp. 1739-1743, 2013 IEEE International Symposium on Information Theory, ISIT 2013, Istanbul, Turkey, 7/7/13. https://doi.org/10.1109/ISIT.2013.6620525

TY - GEN

T1 - Optimal lossless compression

T2 - 2013 IEEE International Symposium on Information Theory, ISIT 2013

AU - Kontoyiannis, Ioannis

AU - Verdu, Sergio

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

KW - Lossless data compression

KW - Markov sources

KW - entropy rate

KW - fundamental limits

KW - minimal source coding rate

KW - source coding

UR - http://www.scopus.com/inward/record.url?scp=84890403315&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84890403315&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2013.6620525

DO - 10.1109/ISIT.2013.6620525

M3 - Conference contribution

AN - SCOPUS:84890403315

SN - 9781479904464

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 1739

EP - 1743

BT - 2013 IEEE International Symposium on Information Theory, ISIT 2013

Y2 - 7 July 2013 through 12 July 2013

ER -

Optimal lossless compression: Source varentropy and dispersion

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this