TY - JOUR
T1 - Universal lossless compression of erased symbols
AU - Yu, Jiming
AU - Verdú, Sergio
N1 - Funding Information:
Manuscript received June 20, 2007; revised March 30, 2008. Current version published November 21, 2008. This work was supported by the National Science Foundation under Grant CCF-0728445. The authors are with with the Department of Electrical Engineering, Princeton University, Princeton, NJ 08544, USA (e-mail: jimingyu@princeton. edu; [email protected]). Communicated by W. Szpankowski, Associate Editor for Source Coding. Color versions of Figures 2–4 in this paper are available online at http://iee-explore.ieee.org. Digital Object Identifier 10.1109/TIT.2008.2006387
PY - 2008
Y1 - 2008
N2 - A source X goes through an erasure channel whose output is Ζ. The goal is to compress losslessly X when the compressor knows X and Z and the decompressor knows Z. We propose a universal algorithm based on context-tree weighting (CTW), parameterized by a memory-length parameter ℓ. We show that if the erasure channel is stationary and memoryless, and X is stationary and ergodic, then the proposed algorithm achieves a compression rate of H(X0 X-ℓ-1, Zℓ) bits per erasure.
AB - A source X goes through an erasure channel whose output is Ζ. The goal is to compress losslessly X when the compressor knows X and Z and the decompressor knows Z. We propose a universal algorithm based on context-tree weighting (CTW), parameterized by a memory-length parameter ℓ. We show that if the erasure channel is stationary and memoryless, and X is stationary and ergodic, then the proposed algorithm achieves a compression rate of H(X0 X-ℓ-1, Zℓ) bits per erasure.
KW - Context-tree weighting
KW - Discrete memoryless erasure channel
KW - Entropy
KW - Erasure entropy
KW - Side information
KW - Universal lossless compression
UR - http://www.scopus.com/inward/record.url?scp=57349103121&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=57349103121&partnerID=8YFLogxK
U2 - 10.1109/TIT.2008.2006387
DO - 10.1109/TIT.2008.2006387
M3 - Article
AN - SCOPUS:57349103121
SN - 0018-9448
VL - 54
SP - 5563
EP - 5574
JO - IEEE Transactions on Information Theory
JF - IEEE Transactions on Information Theory
IS - 12
ER -