Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published July 2014 | Submitted
Book Section - Chapter Open

Variable-Length Compression Allowing Errors

Abstract

This paper studies the fundamental limits of the minimum average length of variable-length compression when a nonzero error probability ε is tolerated. We give non-asymptotic 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-ε)kH(S) - √kV(S)/2π e – (Q^(-1)(ε))^2/2 where Q-1 (·) is the functional inverse of the Q-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 also this asymptotic limit is approached from below, i.e. a larger source dispersion and shorter blocklengths are beneficial. Further, we show that variable-length lossy compression under excess distortion constraint also exhibits similar properties.

Additional Information

© 2015 IEEE. This work was supported in part by the Center for Science of Information (CSoI), an NSF Science and Technology Center, under Grant CCF-0939370.

Attached Files

Submitted - 1402.0608.pdf

Files

1402.0608.pdf
Files (415.5 kB)
Name Size Download all
md5:046c24a9e4ea3cee60c0675c0b2b7801
415.5 kB Preview Download

Additional details

Created:
August 20, 2023
Modified:
October 23, 2023