The information lost in erasures

Sergio Verdú, Tsachy Weissman

Research output: Contribution to journalArticle

44 Scopus citations

Abstract

We consider sources and channels with memory observed through erasure channels. In particular, we examine the impact of sporadic erasures on the fundamental limits of lossless data compression, lossy data compression, channel coding, and denoising. We define the erasure entropy of a collection of random variables as the sum of entropies of the individual variables conditioned on all the rest. The erasure entropy measures the information content carried by each symbol knowing its context. The erasure entropy rate is shown to be the minimal amount of bits per erasure required to recover the lost information in the limit of small erasure probability. When we allow recovery of the erased symbols within a prescribed degree of distortion, the fundamental tradeoff is described by the erasure rate-distortion function which we characterize. We show that in the regime of sporadic erasures, knowledge at the encoder of the erasure locations does not lower the rate required to achieve a given distortion. When no additional encoded information is available, the erased information is reconstructed solely on the basis of its context by a denoiser. Connections between erasure entropy and discrete denoising are developed. The decrease of the capacity of channels with memory due to sporadic memoryless erasures is also characterized in wide generality.

Original languageEnglish (US)
Pages (from-to)5030-5058
Number of pages29
JournalIEEE Transactions on Information Theory
Volume54
Issue number11
DOIs
StatePublished - Nov 10 2008

All Science Journal Classification (ASJC) codes

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

Keywords

  • Channel coding
  • Channels with memory
  • Data compression
  • Discrete denoising
  • Entropy
  • Erasure channels
  • Markov processes
  • Rate-distortion theory
  • Shannon theory

Fingerprint Dive into the research topics of 'The information lost in erasures'. Together they form a unique fingerprint.

  • Cite this