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

Let \ (X₊, Y₊) \^ ₊=₁ be a sequence of independent drawings of a pair of dependent random variables X, Y. Let us say that X takes values in the finite set X. It is desired to encode the sequence \X₊\ in blocks of length n into a binary stream of rate R, which can in turn be decoded as a sequence \ X₊ \, where X₊ X, the reproduction alphabet. The average distortion level is (1/n) ^n₊=₁ ED (X₊, X₊), where D (x, x) 0, x X, x X, is a preassigned distortion measure. The special assumption made here is that the decoder has access to the side information \Y₊\. In this paper we determine the quantity R (d), defined as the infimum ofrates R such that (with > 0 arbitrarily small and with suitably large n) communication is possible in the above setting at an average distortion level (as defined above) not exceeding d +. The main result is that R (d) = I (X;Z) - I (Y;Z), where the infimum is with respect to all auxiliary random variables Z (which take values in a finite set Z) that satisfy: i) Y, Z conditionally independent given X ; ii) there exists a function f: Y Z X, such that ED (X, f (Y, Z) ) d. Let Rₗ | ₘ (d) be the rate-distortion function which results when the encoder as well as the decoder has access to the side information \ Y₊ \. In nearly all cases it is shown that when d > 0 then R (d) > Rₗ|ₘ (d), so that knowledge of the side information at the encoder permits transmission of the \X₊\ 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₊\, i. e. , d = for any >0, knowledge of the side information at the encoder does not allow a reduction of the transmission rate.