A Strictly Improved Achievable Region for Multiple Descriptions Using Combinatorial Message Sharing

We recently proposed a new coding scheme for the L-channel multiple descriptions (MD) problem for general sources and distortion measures involving `Combinatorial Message Sharing' (CMS) [7] leading to a new achievable rate-distortion region. Our objective in this paper is to establish that this coding scheme strictly subsumes the most popular region for this problem due to Venkataramani, Kramer and Goyal (VKG) [3]. In particular, we show that for a binary symmetric source under Hamming distortion measure, the CMS scheme provides a strictly larger region for all L>2. The principle of the CMS coding scheme is to include a common message in every subset of the descriptions, unlike the VKG scheme which sends a single common message in all the descriptions. In essence, we show that allowing for a common codeword in every subset of descriptions provides better freedom in coordinating the messages which can be exploited constructively to achieve points outside the VKG region.