Efficient Run-Length Encoding of Binary Sources with Unknown Statistics

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%.

tr-2003-95.pdf
PDF file

Details

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