deposit_your_work

Faster Sequential Universal Coding via Block Partitioning

Files in this item

Files Size Format View
Bar2006Apr1FasterSequ.PDF 132.0Kb application/pdf Thumbnail

Show full item record

Item Metadata

Title: Faster Sequential Universal Coding via Block Partitioning
Author: Baron, Dror; Baraniuk, Richard G.
Type: Journal Paper
Keywords: Lossless source coding; redundancy; sequential coding; universal coding
Citation: D. Baron and R. G. Baraniuk, "Faster Sequential Universal Coding via Block Partitioning," IEEE Transactions on Information Theory, vol. 52, no. 4, pp. 1708-1710, 2006.
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/2log(n) bits per unknown parameter. We show that the complexity of this algorithm is /spl Omega/(nlog(n)), which is comparable to existing sequential universal algorithms. We provide a sequential O(nlog(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.
Date Published: 2006-04-01

This item appears in the following Collection(s)

  • ECE Publications [1043 items]
    Publications by Rice University Electrical and Computer Engineering faculty and graduate students
  • DSP Publications [508 items]
    Publications by Rice Faculty and graduate students in digital signal processing.