Faster sequential universal coding via block partitioning

Research output: Contribution to journalArticle

Abstract

Rissanen provided a sequential universal coding algorithm based on a block partitioning scheme, where the source model is estimated at the beginning of each block. This approach asymptotically approaches the entropy at the fastest possible rate of 1/2 log (n) bits per unknown parameter. We show that the complexity of this algorithm is Ω (n log (n)), which is comparable to existing sequential universal algorithms. We provide a sequential O(n log (log (n))) algorithm by modifying Rissanen's block partitioning scheme. The redundancy with our approach is greater than with Rissanen's block partitioning scheme by a multiplicative factor 1+ O (1/log(log (n))), hence it asymptotically approaches the entropy at the fastest possible rate.

Original languageEnglish (US)
Pages (from-to)1708-1710
Number of pages3
JournalIEEE Transactions on Information Theory
Volume52
Issue number4
DOIs
StatePublished - Apr 2006

Keywords

  • Lossless source coding
  • Redundancy
  • Sequential coding
  • Universal coding

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Information Systems

Fingerprint Dive into the research topics of 'Faster sequential universal coding via block partitioning'. Together they form a unique fingerprint.

Cite this