Slepian-Wolf Coding

Core Idea

The Slepian-Wolf theorem characterizes the achievable rate region for distributed lossless compression of correlated sources. Two encoders observe correlated sources X and Y respectively and compress them independently (no communication between encoders), while a joint decoder reconstructs both. The achievable rate region is R_X >= H(X|Y), R_Y >= H(Y|X), and R_X + R_Y >= H(X,Y). Remarkably, the sum rate H(X,Y) matches what is achievable with joint encoding — distributed compression loses nothing in total rate compared to centralized compression. This surprising result shows that correlation can be exploited even without encoder cooperation.

Explainer

Consider two sensors monitoring correlated data — say, temperature sensors at nearby locations. If both sensors could share their data before compression, they could jointly compress to H(X,Y) bits total. But what if they must compress independently and only a central server sees both compressed streams? Intuitively, you might expect a penalty for the lack of coordination. The Slepian-Wolf theorem says there is none: the sum rate achievable with distributed compression equals H(X,Y), the same as joint compression.

The achievable rate region is a pentagon defined by three constraints: R_X >= H(X|Y), R_Y >= H(Y|X), and R_X + R_Y >= H(X,Y). The corner point (H(X|Y), H(Y)) represents encoder X sending only the information in X that Y does not have, while encoder Y sends its full entropy. The other corner (H(X), H(Y|X)) reverses the roles. All points on the dominant face R_X + R_Y = H(X,Y) are achievable by time-sharing or random binning.

The proof uses random binning, one of the most important techniques in information theory. Each typical X-sequence is randomly assigned to a bin (index). The encoder for X sends only the bin index, using about nH(X|Y) bits. The decoder receives the bin index and the full (or binned) Y-sequence. Among all X-sequences in the bin, the decoder finds the unique one that is jointly typical with Y. This works because the bin contains about 2^(n(H(X)-H(X|Y))) = 2^(nI(X;Y)) sequences, but only one is jointly typical with Y — the correct one. The correlation acts as "side information" at the decoder that disambiguates the bin.

Slepian-Wolf coding has practical applications in distributed sensor networks, video coding (where multiple camera views have correlation but are encoded independently), and genomic compression (where related genomes have high correlation). The Wyner-Ziv extension handles lossy distributed compression with decoder side information. These results demonstrate a recurring theme in network information theory: information-theoretic limits are often more favorable than naive intuition suggests, because joint decoding can exploit structure that separate encoding cannot.