Optimal adaptation strategies for Golomb codes on correlated sources

For binary two-state Markov sources, we compute the bit-rate for context-independent Golomb coding, sequential coding, and interleaved coding. We also relate these coding methods to image compression work. Sequential coding is a context-dependent method that sequentially codes the source, choosing the order of the elementary Golomb code based on the last bit seen. Interleaved coding codes the even-numbered bits before the odd-numbered bits using elementary Golomb codes of several different orders. Of these methods, we show that no one method is best on all Markov sources.

1. Introduction

Elementary Golomb codes for compressing binary bit sequences have often been used in image compression [6], [7], [8]. They are typically used to compress the bit-planes of the wavelet-transform coefficients of an image. The 1-bits are typically clustered together and thus are correlated; understanding Golomb code performance on correlated sources is necessary for estimating image compression performance. To the best of our knowledge, theoretical performance results for elementary Golomb codes on correlated Markov sources have not been published. Performance on on i.i.d. sources is given in [3].