Near sufficiency of random coding for two descriptions

We give a single-letter outer bound for the two-descriptions problem for independent and identically distributed (i.i.d.) sources that is universally close to the El Gamal and Cover (EGC) inner bound. The gaps for the sum and individual rates using a quadratic distortion measure are upper-bounded by 1.5 and 0.5 bits/sample, respectively, and are universal with respect to the source being encoded and the desired distortion levels. Variants of our basic ideas are presented, including upper and lower bounds on the second channel's rate when the first channel's rate is arbitrarily close to the rate-distortion funcion; these bounds differ, in the limit as the code block length goes to infinity, by not more than 2 bits/sample. An interesting aspect of our methodology is the manner in which the matching single-letter outer bound is obtained, as we eschew common techniques for constructing single-letter bounds in favor of new ideas in the field of rate loss bounds. We expect these techniques to be generally applicable to other settings of interest. © 2006 IEEE.