Universal variable-to-fixed length source codes

Karthik Visweswariah, Sanjeev R. Kulkarni, Sergio Verdú

Research output: Contribution to journalArticle

10 Scopus citations

Abstract

A universal variable-to-fixed length algorithm for binary memoryless sources which converges to the entropy of the source at the optimal rate is known. We study the problem of universal variable-to-fixed length coding for the class of Markov sources with finite alphabets. We give an upper bound on the performance of the code for large dictionary sizes and show that the code is optimal in the sense that no codes exist that have better asymptotic performance. The optimal redundancy is shown to be H log log M/log M where H is the entropy rate of the source and M is the code size. This result is analogous to Rissanen's result for fixed-to-variable length codes. We investigate the performance of a variable-to-fixed coding method which does not need to store the dictionaries, either at the coder or the decoder. We also consider the performance of both these source codes on individual sequences. For individual sequences we bound the performance in terms of the best code length achievable by a class of coders. All the codes that we consider are prefix-free and complete.

Original languageEnglish (US)
Pages (from-to)1461-1472
Number of pages12
JournalIEEE Transactions on Information Theory
Volume47
Issue number4
DOIs
StatePublished - May 2001

All Science Journal Classification (ASJC) codes

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

Keywords

  • Data compression
  • Entropy
  • Minimum description length
  • Tunstall algorithm
  • Universal coding
  • Variable-fixed length codes

Fingerprint Dive into the research topics of 'Universal variable-to-fixed length source codes'. Together they form a unique fingerprint.

Cite this