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 language | English (US) |
---|---|
Pages (from-to) | 1708-1710 |
Number of pages | 3 |
Journal | IEEE Transactions on Information Theory |
Volume | 52 |
Issue number | 4 |
DOIs | |
State | Published - Apr 2006 |
Keywords
- Lossless source coding
- Redundancy
- Sequential coding
- Universal coding
ASJC Scopus subject areas
- Electrical and Electronic Engineering
- Information Systems