Minimum expected length of fixed-to-variable lossless compression of memoryless sources

Wojciech Szpankowski, Sergio Verdú

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

Conventional wisdom states that the minimum expected length for fixed-to-variable length encoding of an n-block memoryless source with entropy H grows as nH+O(1). However, this performance is obtained under the constraint that the code assigned to the whole n-block is a prefix code. Dropping this unnecessary constraint we show that the minimum expected length grows as nH - 1/2 logn + O(1) unless the source is equiprobable.

Original languageEnglish (US)
Title of host publication2009 IEEE International Symposium on Information Theory, ISIT 2009
Pages369-373
Number of pages5
DOIs
StatePublished - Nov 19 2009
Event2009 IEEE International Symposium on Information Theory, ISIT 2009 - Seoul, Korea, Republic of
Duration: Jun 28 2009Jul 3 2009

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8102

Other

Other2009 IEEE International Symposium on Information Theory, ISIT 2009
CountryKorea, Republic of
CitySeoul
Period6/28/097/3/09

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Minimum expected length of fixed-to-variable lossless compression of memoryless sources'. Together they form a unique fingerprint.

  • Cite this

    Szpankowski, W., & Verdú, S. (2009). Minimum expected length of fixed-to-variable lossless compression of memoryless sources. In 2009 IEEE International Symposium on Information Theory, ISIT 2009 (pp. 369-373). [5205737] (IEEE International Symposium on Information Theory - Proceedings). https://doi.org/10.1109/ISIT.2009.5205737