Bounds to the Rate Distortion Tradeoff of the Binary Markov Source

We provide bounds to the rate distortion tradeoff of the binary Markov source with the Hamming distance as the distortion measure. The tradeoff has been completely characterized by Gray (1970) for distortions less than a critical value D_c. Our motivation is to examine the tradeoff for values of distortion above D_c. Our inner bound to the tradeoff follows from an achievable scheme that uses conditional codebooks based on decision feedback at the encoder. Our outer bound follows from an extension of the technique of Berger (1977)