Two sensors observe correlated data X and Y with H(X) = 4, H(Y) = 3, H(X,Y) = 5 bits. What are the Slepian-Wolf rate constraints?
AR_X >= 4 and R_Y >= 3, totaling at least 7 bits — each source must be compressed independently
BR_X >= H(X|Y) = 2, R_Y >= H(Y|X) = 1, and R_X + R_Y >= H(X,Y) = 5 — the sum rate equals joint encoding, despite no communication between encoders
CR_X = R_Y = H(X,Y)/2 = 2.5 bits each
DR_X >= 0 and R_Y >= 0 with no sum constraint
H(X|Y) = H(X,Y) - H(Y) = 5-3 = 2. H(Y|X) = H(X,Y) - H(X) = 5-4 = 1. The Slepian-Wolf region requires each rate to be at least the conditional entropy and the sum to be at least the joint entropy. The corner points are (R_X, R_Y) = (2, 3) or (4, 1). At (2, 3), encoder X sends only the 'new information' about X given Y, and encoder Y sends H(Y) = 3 bits. At (4, 1), the roles reverse. The sum R_X + R_Y >= 5 = H(X,Y) matches centralized compression — no rate penalty for distributed encoding.
Question 2 True / False
The Slepian-Wolf theorem requires the encoders to know each other's source statistics but NOT each other's actual source realizations.
TTrue
FFalse
Answer: True
The encoders must know the joint distribution p(x,y) to design their codebooks, but they do NOT need to see each other's actual data — they encode independently based only on their own observations. The decoder, which sees both compressed streams, uses knowledge of the correlation to jointly decode. This is the surprising part: the correlation is exploited at the DECODER, not the encoder. Random binning (the proof technique) assigns source sequences to bins, and the joint typicality decoder uses the correlation structure to identify the correct sequences from their bins.
Question 3 Short Answer
Explain the intuition behind why distributed compression (Slepian-Wolf) can achieve the same sum rate as joint compression, despite the encoders not communicating.
Think about your answer, then reveal below.
Model answer: The key insight is that the correlation between X and Y is a property of the SOURCES, not of the encoding. The decoder sees both compressed representations and knows the joint distribution. Even though encoder X does not know Y's realization, encoder X can use random binning to send only H(X|Y) bits — the 'new information' in X that Y does not contain. The decoder, knowing both the bin index of X and the actual value of Y (or Y's bin index), uses joint typicality to uniquely recover X. The decoder effectively provides the 'side information' that each encoder lacks. The total information transmitted is H(X|Y) + H(Y) = H(X,Y), matching joint encoding.
Random binning is the proof technique: each typical sequence of X is randomly assigned to one of 2^(nR_X) bins. With high probability, the joint typicality decoder can identify the unique X-sequence in the bin that is jointly typical with Y. This works because the bin is large enough to contain many X-sequences but only one that is jointly typical with the actual Y.