TY - GEN

T1 - Optimal lossless compression

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

AU - Kontoyiannis, Ioannis

AU - Verdu, Sergio

PY - 2013/12/19

Y1 - 2013/12/19

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.

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 -