Universal lossless compression of erased symbols

Jiming Yu, Sergio Verdú

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)5563-5574
Number of pages12
JournalIEEE Transactions on Information Theory
Issue number12
StatePublished - 2008

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


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


Dive into the research topics of 'Universal lossless compression of erased symbols'. Together they form a unique fingerprint.

Cite this