Distributed Source CodingHyun Sung ChangMay 17, 20061 IntroductionHaving multiple sources, correlated with each other, to transmit, do we need more bits if theyare separated than when they are together? This question was first raised in a seminal paper ofSlepian and Wolf [1]. The answer is surprisingly “No,” and what is even more interesting is thatan important role of source compression is played by channel coding. This amazing result has beenknown as Slepian-Wolf theorem and followed by a fair amount of research works, e.g., extended byWyner and Ziv [2] to lossy encoding of continuous-valued sources.Unfortunately, however, the theorem has hardly found its place in practical applications forquite a long time. “Despite the existence of potential applications, the conceptual importance ofdistributed source coding has not been mirrored in practical data compression,” said an articlecommemorating fifty years of information theory [3]. In fact, even a simple constructive codingexample, beyond the theoretical and asymptotic result, had been unavailable until very recently apractical coding scheme was proposed by Pradhan and Ramchandran [4].Since triggered by the work of Pradhan and Ramchandran, however, the Slepian-Wolf theoremhas successfully redrawn attentions as a promising coding technique, particularly useful for modernapplications such as distributed sensor network and low-power video coding, due to its capabilityof compressing distributed sources with low complexity at still high compression rates. This trendis well captured by the fact that the distributed source coding (DSC) solely comprises a regularsession at many recent signal processing conferences.2 Slepian-Wolf TheoremThe key result of Slepian-Wolf theorem can be summarized by the following: The minimal but stillachievable amount of bits to represent two correlated sources X1and X2with little decoding errorprobability is equal to their joint entropy, H(X1, X2), not increased by the separation between thesources. More precisely, a pair of rates (R1, R2), each required to represent X1and X2, respectively,is achievable if and only ifR1≥ H(X1|X2) AND R2≥ H(X2|X1) AND R1+ R2≥ H(X1, X2),as illustrated on the R1R2plane in Figure 1.The achievability can be proven using the idea of “random encoding” and “jointly typical setdecoding,” while the proof for the converse part is quite straightforward [5]. Let us consider a cornerpoint, (R1, R2) = (H(X1), H(X2|X1)), in Figure 1. First, X1can be encoded, with R1bits, using a1good insightIs there practical DSC that covers the dominant face?Suggestions:Pointed out the significance of furthering the researchand the research objective6.441 Transmission of Information Project Report 21R2R1 2( , )H X X1 2( , )H X X1( )H X1 2( | )H X X2 1( | )H X X2( )H X0No errorsVanishing error probability for long sequencesFigure 1: Slepian-Wolf theorem: admissible rate region for distributed compression of two statisti-cally dependent i.i.d. sources X1and X2. (Reproduced from [6])single source compression scheme. Next, what the random encoding on X2actually does is to share2nR2codewords among the typical X2sequences distinguishable if X1is additionally available atthe decoder. In other words, the encoder decomposes X2into (X′2,˜X2) and encodes only˜X2withR2bits, discarding X′2. Then, the decoder should guess X′2, with little error probability, using thecorrelation between X1and X′2. This is possible from the channel coding theorem if we considera virtual channel (X′2, p(x1|x′2), X1) because the input sequence whose rate is below the channelcapacity, I(X1; X′2), can be recovered reliably. Note that I(X1; X′2) ≤ I(X1; X2) and that R2goesminimum, i.e., to H(X2|X1), when I(X1; X′2) = I(X1; X2). This argument suggests that the DSCis closely related to channel coding.However, note that it tells only about the theoretical and asymptotic bound and not much abouthow to encode in practice. A subtle point here is about how to decompose X2into (X′2,˜X2) so thatI(X1; X′2) = I(X1; X2). The next section will present some practical coding examples for specifictypes of correlation between X1and X2and also make the relationship to the channel coding moreexplicit.3 Practical Coding3.1 Modulo EncodingLet X1and X2be scalar random variables correlated by |X1− X2| < ∆1/2 for some integer ∆1.The encoder compresses˜X2:= X2mod ∆1, rather than X2, sharing the same codeword among allx2’s satisfying ˜x2= x2mod ∆1. Then, the required number of bits to encode˜X2is log ∆1, equalto H(X2|X1), if X2is uniformly distributed about X1. The decoder can reconstruct X2, withouterror, to˜X2+jX1−˜X2∆1+12k· ∆1if X1is known.Modulo-encoding fails to reach the Slepian-Wolf bound, i.e., H(X2|X1), for other kinds ofdistribution. For instance, if X2is Gaussian with its mean and variance given by X1and ∆21/36,modulo-encoding falls below the bound by about half a bit [7].Nice arguement. Can you generalize this to the rate pairs on the dominant face?dorminantface(see Fig 1)It may be evenbetter to pointout that thebest encoder ofone problem isfunctionally identical to the best decoder of the other problem, as described by Pradhan in his paper on the duality between source and channel coding.6.441 Transmission of Information Project Report 33.2 Syndrome EncodingLet X1and X2be binary random vectors correlated by dH(X1, X2) ≤ ∆2, where dHdenotesthe Hamming distance. Any group of x2’s which differ from each other by (2∆2+ 1) or more bitscan share the same codeword, say˜X2, because they become distinguishable if combined with X1.In other words, if x(1)2, the actual value of X2, shares the codeword with x(2)2, dH(x1, x(2)2) ≥dH(x(1)2, x(2)2) − dH(x1, x(1)2) ≥ (2∆2+ 1)− (∆2) = ∆2+ 1, by the triangle inequality, and thus x(2)2cannot come along with x1, leaving no room for confusion at the decoder if only x1is available,because it is sufficiently far apart from x(1)2. This notion of “separation” is exactly the same asappearing in the context of error correcting codes, and˜X2corresponds to a coset index, calledsyndrome, in the linear block code [4].Note that the above argument was made on binary sources. For continuous-valued sources, e.g.,Gaussian sources, lossy coding based on rate-distortion theory [2] is used instead. In practice, it isconsidered equivalent to the quantization followed by the lossless Slepian-Wolf encoding.3.3 Convolutional EncodingFor the