  This paper presents a new achievable rate-distortion region for the general L
channel multiple descriptions problem. A well known general region for this
problem is due to Venkataramani, Kramer and Goyal (VKG) [1]. Their encoding
scheme is an extension of the El-Gamal-Cover (EC) and Zhang- Berger (ZB) coding
schemes to the L channel case and includes a combinatorial number of refinement
codebooks, one for each subset of the descriptions. As in ZB, the scheme also
allows for a single common codeword to be shared by all descriptions. This
paper proposes a novel encoding technique involving Combinatorial Message
Sharing (CMS), where every subset of the descriptions may share a distinct
common message. This introduces a combinatorial number of shared codebooks
along with the refinement codebooks of [1]. We derive an achievable
rate-distortion region for the proposed technique, and show that it subsumes
the VKG region for general sources and distortion measures. We further show
that CMS provides a strict improvement of the achievable region for any source
and distortion measures for which some 2-description subset is such that ZB
achieves points outside the EC region. We then show a more surprising result:
CMS outperforms VKG for a general class of sources and distortion measures,
including scenarios where the ZB and EC regions coincide for all 2-description
subsets. In particular, we show that CMS strictly improves on VKG, for the
L-channel quadratic Gaussian MD problem, for all L greater than or equal to 3,
despite the fact that the EC region is complete for the corresponding
2-descriptions problem. Using the encoding principles derived, we show that the
CMS scheme achieves the complete rate-distortion region for several asymmetric
cross-sections of the L-channel quadratic Gaussian MD problem.
