Multiple Description Coding:Typical Arguments and Random BinningCharles SwannackAbstractWe reexamine the problem of Multiple Description coding considered last week.We briefly review the import concepts and results. An overview of the basic methodsof proof are provided. We further formulate this problem in the context of distributedsource coding and from this framework examine a practical coding scheme for th esymmetric problem provided by Prad han et. al.IntroductionThe problem of multiple description (MD) coding has roots in both practical andtheoretical communities. This problem while theoretically challenging also provides avaluable framework for reliable transmission over a packet network.Today we will not only overview the methods that are used to prove the achievabilityof the best know MD rate-distortion regions, but also overview a constructive approachto the problem. The MD problem may be roughly described as follows [1]:Suppose that we wish to describe a stochastic process through a communi-cation network. Therefore, we send L descriptions in hopes that a few ofthem will get through. However, due to link failures, only a random subsetof the descriptions get through. What is the region of achievable distortionsfor ev ery possible set of link failures?A depiction of th e general problem may be seen in Figure 1. In general we will considera discrete source that produces a sequence symbols {Xi}∞i=ithat are independent andidentically-distributed (i.i.d.) with respect to the probability mass function p(x), forx ∈ X for some given alphabet X . We will denote the set of received descriptionindices as K and denote the corresponding decoder and reconstruction space as gKandˆXK. Note that the decoder and the reconstruction space depend on the set of receiveddescription indices K and that the set K is unknown to the encoder.As noted last week it is not possible in general to achieve the rate-distortion functionfor every possible subset of indices. Indeed, we saw in Ozarow’s Theorem [2] (the threereceiver case with a Gaussian source and mean squared distortion) if the distortionon the side decoders is equal to the distortion-rate function D(R) = exp −2R thenthe joint decoder can not achieve a distortion that is better than D(R)/2. This is farfrom D2(R) = D(R + R) if D(R) ≪ 1. Intuitively, this is due to the fact that if theside decoders achieve the optimal distortion-rate then they must be highly correlatedand thus the extra description provides very little inf ormation. However, a pr ecisequantitative statement for the general L-channel problem for either a Gaussian or ageneral source is still not known.1Sourcep(x)XnSourceEncoderx1x2x3xL−1xLPacketErasureChannelXKDecoderˆxnFigure 1: The MD ProblemSourcep(x)XnSourceEncoderx1x2Decoder 1Decoder 2Decoder {1, 2}ˆx1ˆx2ˆx{1,2}Figure 2: The 2-User Multiple Description ProblemWe will reexamine the general rate-distortion regions that were discussed last time.Today, we will more closely examine the proofs of the theorem’s of El Gamal andCover [1], Zhang and Berger [3] as well as the region of Venkataramani, Kramer, andGoyal [4]. T his time we will focus on the perspective of deco ding with side information.Additionally, we will consider the more pr actically motivated question of finding “good”achievable methods of encoding to achieve an arbitrary distortion specification. Wewill first consider th e common methods for proving the achievability of a given rate-distortion vector. Then we will consider a new constructive method that uses channelerasure codes as well as distributed source coding to encod e for links with a symmetricrate.2-Description MD RegionsThe most basic problem in multiple description coding is the 2-description with threereceiver problem. As discussed last time the exact region of achievable rates is known inthe case of a Gaussian source. In deed, this is the result of Ozarow [2]. The exact prob-lem setup can be seen in Figure 2. We now recall one of the earliest characterizationsof the 2-description coding problems.Theorem 1. (The EGC Region) The quintuple (R1, R2, d1, d2, d{1,2}) is achievable ifthere exist random variablesˆX1,ˆX2,ˆX{1,2}jointly distributed with a g eneric sourcerandom variable X such that:Ri≥ I(X;ˆXi) for i ∈ {1, 2} (1)R1+ R2≥ I(X;ˆX1,ˆX2,ˆX{1,2}) + I(ˆX1;ˆX2) (2)DK≥ EndX,ˆXKofor K ∈ {1, 2, {1, 2}} (3)The proof of this theorem follows for what is now a quite standard argum ent usingrandom codes and typical sets. We refer the reader to [5] for a complete discussionon typical sets and their properties. We now provide a brief sketch of the proof ofTheorem 1.Sketch of Proof. We sketch th e proof with the following steps:0) Given:a) X1and X2such that X1covers Xnwith distortion D1and X2covers Xnwithdistortion D2.b) A collection of code books that X0conditionally cover Xnwith distortion d0.1) Random Code Generationa) Draw 2nR′1vectors uniformly from Tǫ(X1).b) Draw 2nR′2vectors uniformly from Tǫ(X2).c) For each jointly typical (x1(i), x2(j)) construct at codebook by drawing 2n∆vectors from Tǫ(x0|x1(i), x2(j)).2) Encoding:Given an x ∈ Xnfind an (i, j, k) such th at (x, x0(k), x1(i), x2(j)) arein the set of all jointly typical sequences if possible. Otherwise, set (i, j, k) =(0, 0, 0). Split, k in to two so that k = (k1, k2). Description 1 is then (i, k1),description 2 is (j, k2).3) Decoding:a) Decoder 1: Receives (i, k1) and announces x1(i)b) Decoder 2: Receives (j, k2) and announces x2(j)c) Decoder {1, 2}: Receives (i, j, k) and announces x0(i, j, k)3) Distortion:Can show,E {d} = (1 − Pe)(D + ǫ) + Pedmaxwhere u nder the conditions of the theorem Pe→ 0.This region is the optimal region for a Gaussian source with square error distortionand was conjectured to be th e optimal region in general. However, note that in thedecoding s tage of th e above proof the descriptions k1and k2are thrown away whensingle description is received. While, this does not matter in the case of a Gaussiansource with square err or distortion, a slight modification to the proof above led Zhangand Berger to show that the EGC region is not in general optimal by examining thecase of a binary source with a Hamming distortion. The region of Zhang and Berger(ZB) is described in the f ollowing.Theorem 2. (The ZB Region) The quintuple (R1, R2, d1, d2, d{1,2}) is achievable ifthere exist random variablesˆX1,ˆX2,ˆX2jointly distributed with a generic source randomvariable X such