Back to Search
Start Over
Variable-Length Compression Allowing Errors.
- Source :
-
IEEE Transactions on Information Theory . Aug2015, Vol. 61 Issue 8, p4316-4330. 15p. - Publication Year :
- 2015
-
Abstract
- This paper studies the fundamental limits of the minimum average length of lossless and lossy variable-length compression, allowing a nonzero error probability \epsilon , 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 - \epsilon ) k H(\mathsf S) - {({({k V(\mathsf S)}/{2 \pi })})}^{1/2} \mathop {\rm exp}[- ({( Q^{-1}\left ({\epsilon }\right ))^{2}}/{2})] , where Q^{-1}\left ({\cdot }\right )$ is the functional inverse of the standard Gaussian complementary cumulative distribution function, and $V(\mathsf S)$ is the source dispersion. A nonzero error probability thus not only reduces the asymptotically achievable rate by a factor of $1 - \epsilon $ , 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. [ABSTRACT FROM PUBLISHER]
Details
- Language :
- English
- ISSN :
- 00189448
- Volume :
- 61
- Issue :
- 8
- Database :
- Academic Search Index
- Journal :
- IEEE Transactions on Information Theory
- Publication Type :
- Academic Journal
- Accession number :
- 108358187
- Full Text :
- https://doi.org/10.1109/TIT.2015.2438831