Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Efficient Run-Length Encoding of Binary Sources with Unknown Statistics

Max H.M. Costa and Henrique S. Malvar

Abstract

We present a new binary entropy coder of the Golomb family, with an adaptation strategy that is nearly optimum in a maximum-likelihood sense. This new encoder can be implemented efficiently in practice, since uses only integer arithmetic and no divisions. That way, the proposed encoder has a complexity nearly identical to that of popular adaptive Rice coders. However, whereas Golomb-Rice coders have an excess rate with respect to the source entropy of up to 4.2% for binary sources with unknown statistics, the proposed encoder has an excess rate of less than 2%.

Details

Publication typeTechReport
NumberMSR-TR-2003-95
Pages12
InstitutionMicrosoft Research
> Publications > Efficient Run-Length Encoding of Binary Sources with Unknown Statistics