THE RATE LOSS IN THE WYNER-ZIV PROBLEM

The rate-distortion function for source coding with side information a t the decoder (the ''Wyner-Ziv problem'') is given in terms of an auxi liary random variable, which forms a Markov chain with the source and the side information, This Markov chain structure, typical to the solu tion of multiterminal source coding problems, corresponds to a loss in coding rate with respect to the conditional rate-distortion function, i.e., to the case where the encoder is fully informed, We show that f or difference (or balanced) distortion measures, this loss is bounded by a universal constant, which is the minimax capacity of a suitable a dditive-noise channel, Furthermore, in the worst case, this loss is eq ual to the maximin redundancy over the rate-distortion function of the additive noise ''test'' channel, For example, the loss in the Wyner-Z iv problem is less than 0.5 bit/sample in the squared-error distortion case, and it is less than 0.22 bit for a binary source with Hamming d istance, These results have implications also in universal quantizatio n with side information, and in more general multiterminal source codi ng problems.