Universal lossless compression of erased symbols

Jiming Yu; Sergio Verdú

doi:10.1109/TIT.2008.2006387

Universal lossless compression of erased symbols

Jiming Yu, Sergio Verdú

Research output: Contribution to journal › Article › peer-review

Abstract

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(X₀ X_-ℓ^-1, Z^ℓ) bits per erasure.

Original language	English (US)
Pages (from-to)	5563-5574
Number of pages	12
Journal	IEEE Transactions on Information Theory
Volume	54
Issue number	12
DOIs	https://doi.org/10.1109/TIT.2008.2006387
State	Published - 2008

All Science Journal Classification (ASJC) codes

Information Systems
Computer Science Applications
Library and Information Sciences

Keywords

Context-tree weighting
Discrete memoryless erasure channel
Entropy
Erasure entropy
Side information
Universal lossless compression

Access to Document

10.1109/TIT.2008.2006387

Cite this

@article{b64a73cac6b34b2da8d3f15ee7ff56ae,

title = "Universal lossless compression of erased symbols",

abstract = "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.",

keywords = "Context-tree weighting, Discrete memoryless erasure channel, Entropy, Erasure entropy, Side information, Universal lossless compression",

author = "Jiming Yu and Sergio Verd{\'u}",

note = "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; verdu@princeton.edu). 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",

year = "2008",

doi = "10.1109/TIT.2008.2006387",

language = "English (US)",

volume = "54",

pages = "5563--5574",

journal = "IEEE Transactions on Information Theory",

issn = "0018-9448",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "12",

}

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; verdu@princeton.edu). 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 -

Universal lossless compression of erased symbols

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this