The rate-distortion function for source coding with side information at the decoder

Let\{(X_{k}, Y_{k}) \}^{ \infty}_{k=1}be a sequence of independent drawings of a pair of dependent random variablesX, Y. Let us say thatXtakes values in the finite set\cal X. It is desired to encode the sequence\{X_{k}\}in blocks of length n into a binary stream of rateR, which can in turn be decoded as a sequence\{ \hat{X}_{k} \}, where\hat{X}_{k} \in \hat{ \cal X}, the reproduction alphabet. The average distortion level is(1/n) \sum^{n}_{k=1} E[D(X_{k},\hat{X}_{k})], whereD(x,\hat{x}) \geq 0, x \in {\cal X}, \hat{x} \in \hat{ \cal X}, is a preassigned distortion measure. The special assumption made here is that the decoder has access to the side information\{Y_{k}\}. In this paper we determine the quantityR \ast (d), defined as the infimum ofratesRsuch that (with\varepsilon > 0arbitrarily small and with suitably largen)communication is possible in the above setting at an average distortion level (as defined above) not exceedingd + \varepsilon. The main result is thatR \ast (d) = \inf [I(X;Z) - I(Y;Z)], where the infimum is with respect to all auxiliary random variablesZ(which take values in a finite set\cal Z) that satisfy: i)Y,Zconditionally independent givenX; ii) there exists a functionf: {\cal Y} \times {\cal Z} \rightarrow \hat{ \cal X}, such thatE[D(X,f(Y,Z))] \leq d. LetR_{X | Y}(d)be the rate-distortion function which results when the encoder as well as the decoder has access to the side information\{ Y_{k} \}. In nearly all cases it is shown that whend > 0thenR \ast(d) > R_{X|Y} (d), so that knowledge of the side information at the encoder permits transmission of the\{X_{k}\}at a given distortion level using a smaller transmission rate. This is in contrast to the situation treated by Slepian and Wolf [5] where, for arbitrarily accurate reproduction of\{X_{k}\}, i.e.,d = \varepsilonfor any\varepsilon >0, knowledge of the side information at the encoder does not allow a reduction of the transmission rate.