New results in binary multiple descriptions

An encoder whose input is a binary equiprobable memoryless source produces one output of rateR₁and another of rateR₂. LetD₁, D₂, and D₀, respectively, denote the average error frequencies with which the source data can be reproduced on the basis of the encoder output of rateRₗonly, the encoder output of rateR₂only, and both encoder outputs. The two-descriptions problem is to determine the regionRof all quintuples(R₁, R₂, D₁, D₂, D₀)that are achievable in thc usual Shannon sense. LetR(D)=1+D log₂ D+(1-D) log₂(1-D)denote the error frequency rate-distortion function of the source. The "no excess rate case" prevails whenR₁ + R₂ = R(D₀), and the "excess rate case" whenR₁ + R₂ > R(D₀). Denote the section ofRat(R₁, R₂, D₀)byD(R₁ R₂, D₀) =\{(D₁,D₂): (R₁, R₂, D₁,D₂,D₀) ∈ R}. In the no excess rate case we show that a portion of the boundary ofD(R₁, R₂, D₀)coincides with the curve(1/2 + D₁-2D₀)(₁₂ + D₂-2D₀)= 1/2(1-2D₀)². This curve is an extension of Witsenhausen's hyperbola bound to the caseD₀ > 0. It follows that the projection ofRonto the(D₁, D₂)-plane at fixedD₀consists of allD₁ ≥ D₀andD₂ ≥ D₀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.