The role of the asymptotic equipartition property in noiseless source coding

Sergio Verdú, Te Sun Han

Research output: Contribution to journalArticle

18 Scopus citations

Abstract

The (noiseless) fixed-length source coding theorem states that, except for outcomes in a set of vanishing probability, a source can be encoded at its entropy but not more efficiently. It is well known that the Asymptotic Equipartition Property (AEP) is a sufficient condition for a source to be encodable at its entropy. This paper shows that the AEP is necessary for the source coding theorem to hold for nonzero-entropy finite-alphabet sources. Furthermore, we show that a nonzero-entropy finite-alphabet source satisfies the direct coding theorem if and only if it satisfies the strong converse. In addition, we introduce the more general setting of nonserial information sources which need not put out strings of symbols. In this context, which encompasses the conventional serial setting, the AEP is equivalent to the validity of the strong coding theorem. Fundamental limits for data compression of nonserial information sources are shown based on the flat-top property - a new sufficient condition for the AEP.

Original languageEnglish (US)
Pages (from-to)847-857
Number of pages11
JournalIEEE Transactions on Information Theory
Volume43
Issue number3
DOIs
StatePublished - Dec 1 1997

All Science Journal Classification (ASJC) codes

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

Keywords

  • Asymptotic equipartition property
  • Entropy
  • Fixed-length source coding
  • Noiseless data compression
  • Shannon theory
  • Source coding theorem

Fingerprint Dive into the research topics of 'The role of the asymptotic equipartition property in noiseless source coding'. Together they form a unique fingerprint.

  • Cite this