Minimum expected length of fixed-to-variable lossless compression without prefix constraints

Wojciech Szpankowski, Sergio Verdú

Research output: Contribution to journalArticle

31 Scopus citations

Abstract

The minimum expected length for fixed-to-variable length encoding of an n -block memoryless source with entropy H grows as n H + O(1), where the term O(1) lies between 0 and 1. However, this well-known performance is obtained under the implicit constraint that the code assigned to the whole n-block is a prefix code. Dropping the prefix constraint, which is rarely necessary at the block level, we show that the minimum expected length for a finite-alphabet memoryless source with known distribution grows as n H - 1\2 log n +O(1) unless the source is equiprobable. We also refine this result up to o(1) for those memoryless sources whose log probabilities do not reside on a lattice.

Original languageEnglish (US)
Article number5895099
Pages (from-to)4017-4025
Number of pages9
JournalIEEE Transactions on Information Theory
Volume57
Issue number7
DOIs
StatePublished - Jul 1 2011

All Science Journal Classification (ASJC) codes

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

Keywords

  • Analytic information theory
  • Shannon theory
  • fixed-to-variable lossless compression
  • memoryless sources
  • one-to-one codes
  • source coding

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

  • Cite this