A Calculation of the Heegard-Berger Rate-distortion Function for a Binary Source

We provide an explicit calculation of the rate-distortion function for the doubly-symmetric binary source (DSBS), when the side information may be absent at the decoder. The rate-distortion function for general discrete memoryless source was characterized by Heegard and Berger in 1985 [IT-31(6)], who showed that a two-stage coding structure is in fact optimal. However, an explicit characterization of the rate-distortion function for DSBS, and more importantly the optimal forward testing channel structure for this source, was not found despite several attempts. In this work, we resolve this open problem. It is shown that in the two-stage coding structure, the optimal testing channel for the first stage decoder (who does not have side information) is the same as the optimal testing channel for the ordinary symmetric binary source, and this confirms a conjecture made by Fleming and Effros.