New results in binary multiple descriptions (1987)

An encoder whose input is a binary equiprobable memoryless source produces one output of rate <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">R_{1}</tex> and another of rate <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">R_{2}</tex> . Let <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">D_{1}, D_{2}, and D_{0}</tex> , respectively, denote the average error frequencies with which the source data can be reproduced on the basis of the encoder output of rate <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">R_{l}</tex> only, the encoder output of rate <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">R_{2}</tex> only, and both encoder outputs. The two-descriptions problem is to determine the region <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">R</tex> of all quintuples <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">(R_{1}, R_{2}, D_{1}, D_{2}, D_{0})</tex> that are achievable in thc usual Shannon sense. Let <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">R(D)=1+D \log_{2} D+(1-D) \log_{2}(1-D)</tex> denote the error frequency rate-distortion function of the source. The "no excess rate case" prevails when <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">R_{1} + R_{2} = R(D_{0})</tex> , and the "excess rate case" when <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">R_{1} + R_{2} > R(D_{0})</tex> . Denote the section of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">R</tex> at <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">(R_{1}, R_{2}, D_{0})</tex> by <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">D(R_{1} R_{2}, D_{0}) =\{(D_{1},D_{2}): (R_{1}, R_{2}, D_{1},D_{2},D_{0}) \in R}</tex> . In the no excess rate case we show that a portion of the boundary of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">D(R_{1}, R_{2}, D_{0})</tex> coincides with the curve <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">(\frac{1}{2} + D_{1}-2D_{0})(\frac_{1}_{2} + D_{2}-2D_{0})= \frac{1}{2}(1-2D_{0})^{2}</tex> . This curve is an extension of Witsenhausen's hyperbola bound to the case <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">D_{0} > 0</tex> . It follows that the projection of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">R</tex> onto the <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">(D_{1}, D_{2})</tex> -plane at fixed <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">D_{0}</tex> consists of all <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">D_{1} \geq D_{0}</tex> and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">D_{2} \geq D_{0}</tex> that lie on or above this hyperbola. In the excess rate case we show by counterexample that the achievable region of El Gamal and Cover is not tight.