Variable-Length Compression Allowing Errors

Abstract

This paper studies the fundamental limits of the minimum average length of lossless and lossy variable-length compression, allowing a nonzero error probability ε, 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 − ε)kH(S) − ((kV(S)/2π))^1/2 exp[−((Q−1 (ε))^(2)/2)], where Q^−1 (·) is the functional inverse of the standard Gaussian complementary cumulative distribution 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 this asymptotic limit is approached from below, i.e., larger source dispersions and shorter blocklengths are beneficial. Variablelength lossy compression under an excess distortion constraint is shown to exhibit similar properties.

Files

Additional details