A strictly improved achievable region for multiple descriptions using combinatorial message sharing

Abstract—We recently proposed a new coding scheme for the L-channel multiple descriptions (MD) problem for general sources and distortion measures involving ‘Combinatorial Mes-sage 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. Index Terms—Multiple descriptions coding, Source coding, Rate distortion theory I