Variable-Length Compression Allowing Errors

DOI10.1109/TIT.2015.2438831MaRDI QIDQ2977340zbMATH OpenOpenAlexFDO

Authors Victoria Kostina, Yury Polyanskiy, Sergio Verdú

Publication date 28 April 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1402.0608

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Coding theorems (Shannon theory) (94A24) Rate-distortion theory in information and communication theory (94A34)

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 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: ${\displaystyle }$(1 - epsilon) k H(mathsf S) - sqrt{frac{k V(mathsf S)}{2 pi} } e^{- frac {(Q^{-1}(epsilon))^2} 2 }${\displaystyle }$ where $Q^{-1}(cdot)$ is the functional inverse of the standard Gaussian complementary cdf, and $V(mathsfS)$ 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.

Recommendations

• Variable-length codes for error correction
• Error-Resilient Optimal Data Compression
• Efficient error-limiting variable-length codes
• Third-Order Asymptotics of Variable-Length Compression Allowing Errors
• Lossless Data Compression Via Error Correction
• scientific article; zbMATH DE number 5170141
• The Effect of Local Decodability Constraints on Variable-Length Compression
• Burrows-Wheeler compression with variable length integer codes

Cited in

(4)

• Variable Compression in ProbLog
• scientific article; zbMATH DE number 5170141 (Why is no real title available?)
• Common Information, Noise Stability, and Their Extensions
• Finite Blocklength Lossy Source Coding for Discrete Memoryless Sources

This page was built for publication: Variable-Length Compression Allowing Errors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2977340)