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.