46.05.01 · information-theory / side-information

Slepian-Wolf Coding: Distributed Lossless Compression

shipped3 tiersLean: none

Anchor (Master): Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §15.1-15.8; Slepian & Wolf 1973 Noiseless Coding of Correlated Information Sources; Csiszar & Korner 2011 Information Theory: Coding Theorems for Discrete Memoryless Systems 2e (Cambridge) §3.2-3.3

Intuition Beginner

Two weather stations in nearby cities record the daily temperature. The readings are correlated — if it is hot in one city, it is almost certainly hot in the other. Each station wants to send its temperature log to a central server, but they cannot talk to each other. How efficiently can they compress their data?

If the stations could cooperate, they would compress jointly, using a rate equal to the joint entropy $H (X_{1}, X_{2})$ — the total uncertainty of both temperature records together. This is the fundamental limit for joint compression.

The surprise is: even without cooperating, they can still achieve the joint entropy rate. Each station encodes independently, and the central server decodes both records jointly. The total number of bits sent equals $H (X_{1}, X_{2})$ — the same as if they had worked together. This is the Slepian-Wolf theorem.

How is this possible? Each station sends slightly more than its conditional entropy (given the other station's data). Station 1 sends $H (X_{1} ∣ X_{2})$ bits, station 2 sends $H (X_{2} ∣ X_{1})$ bits, and the sum is $H (X_{1}, X_{2})$ . The decoder, seeing both compressed streams, can reconstruct both records because the correlation structure is strong enough to resolve ambiguities.

The key constraint is that each station must send at least its conditional entropy, and the total must be at least the joint entropy. These three inequalities define a pentagonal region in the rate plane, and any rate pair inside it is achievable.

This result has enormous practical importance for sensor networks, distributed databases, and any system where correlated data is collected at multiple locations and must be compressed locally before transmission.

Visual Beginner

Figure: the Slepian-Wolf rate region for two correlated sources. The axes are $R_{1}$ (rate of encoder 1) and $R_{2}$ (rate of encoder 2). The achievable region is a pentagon with vertices at $(H (X_{1} ∣ X_{2}), H (X_{2}))$ , $(H (X_{1}), H (X_{2} ∣ X_{1}))$ , and the corner point $(H (X_{1} ∣ X_{2}), H (X_{2} ∣ X_{1}))$ . The sum-rate bound $R_{1} + R_{2} \geq H (X_{1}, X_{2})$ cuts diagonally across the rate plane.

Rate constraint	Meaning
$R_1 \geq H(X_1	X_2)$
$R_2 \geq H(X_2	X_1)$
$R_{1} + R_{2} \geq H (X_{1}, X_{2})$	Together they must send at least the joint entropy
$R_{1} + R_{2} = H (X_{1}, X_{2})$	Optimal sum rate (same as joint coding)

Worked example Beginner

Two correlated binary sources: $X_{1}$ is a fair coin flip, and $X_{2} = X_{1}$ with probability 0.9 and $1 - X_{1}$ with probability 0.1 (a "noisy copy").

The joint entropy is $H (X_{1}, X_{2}) = H (X_{1}) + H (X_{2} ∣ X_{1}) = 1 + H (0.1) \approx 1 + 0.469 = 1.469$ bits. The individual entropies are $H (X_{1}) = 1$ and $H (X_{2}) = 1$ (both are fair coins marginally). The conditional entropies are $H (X_{1} ∣ X_{2}) \approx 0.469$ and $H (X_{2} ∣ X_{1}) \approx 0.469$ .

Without cooperation, the Slepian-Wolf theorem says encoder 1 can use rate $R_{1} = 0.469$ bits and encoder 2 can use rate $R_{2} = 0.469$ bits (at the symmetric corner), for a total of $0.938$ bits per symbol pair. Wait — that violates the sum-rate constraint. Let us recalculate: the sum-rate requires $R_{1} + R_{2} \geq 1.469$ . At the symmetric point, both send $H (X_{1} ∣ X_{2}) = 0.469$ , but $0.469 + 0.469 = 0.938 < 1.469$ . This violates the sum constraint.

The correct symmetric point is on the sum-rate line: $R_{1} = R_{2} = H (X_{1}, X_{2}) /2 = 0.735$ bits each. Or one encoder can send more: encoder 1 sends $R_{1} = 1$ (its full entropy) and encoder 2 sends $R_{2} = 0.469$ (its conditional entropy), totaling 1.469. Either way, the sum equals the joint entropy.

Check your understanding Beginner

Formal definition Intermediate+

Let $(X_{1}, X_{2})$ be a pair of discrete random variables with joint distribution $p (x_{1}, x_{2})$ on $X_{1} \times X_{2}$ . The sources are i.i.d. across time: $(X_{1, i}, X_{2, i}) \sim p (x_{1}, x_{2})$ for $i = 1, 2, \dots$ .

Definition (Distributed source code). A $(2^{n R_{1}}, 2^{n R_{2}}, n)$ distributed source code consists of:

Two encoders: $f_{1} : X_{1}^{n} \to {1, \dots, 2^{n R_{1}}}$ and $f_{2} : X_{2}^{n} \to {1, \dots, 2^{n R_{2}}}$ , each mapping its source sequence to an index.
A joint decoder: $g : {1, \dots, 2^{n R_{1}}} \times {1, \dots, 2^{n R_{2}}} \to \hat{X}_{1}^{n} \times \hat{X}_{2}^{n}$ mapping the index pair to estimates.

The probability of error is $P_{e}^{(n)} = Pr [(\hat{X}_{1}^{n}, \hat{X}_{2}^{n}) \neq = (X_{1}^{n}, X_{2}^{n})]$ .

Definition (Achievable rate pair). A rate pair $(R_{1}, R_{2})$ is achievable if there exists a sequence of $(2^{n R_{1}}, 2^{n R_{2}}, n)$ codes with $P_{e}^{(n)} \to 0$ as $n \to \infty$ .

Theorem (Slepian-Wolf 1973). The achievable rate region for the distributed lossless compression of correlated i.i.d. sources $(X_{1}, X_{2})$ is:

R_{S W} = {(R_{1}, R_{2}) : R_{1} \geq H (X_{1} ∣ X_{2}), R_{2} \geq H (X_{2} ∣ X_{1}), R_{1} + R_{2} \geq H (X_{1}, X_{2})} .

Key theorem with proof Intermediate+

Theorem (Slepian-Wolf achievability). Any rate pair $(R_{1}, R_{2})$ in the region $R_{S W}$ is achievable.

Proof (random binning). We prove achievability for the corner point $(R_{1}, R_{2}) = (H (X_{1} ∣ X_{2}) + ϵ, H (X_{2}))$ . The full region follows by time-sharing and symmetry.

Random binning. Independently assign each $x_{1}^{n} \in X_{1}^{n}$ uniformly at random to one of $2^{n R_{1}}$ bins. Similarly assign each $x_{2}^{n} \in X_{2}^{n}$ to one of $2^{n R_{2}} = 2^{n H (X_{2})}$ bins. Denote the bin indices by $b_{1} (x_{1}^{n})$ and $b_{2} (x_{2}^{n})$ .

Encoder. Encoder 1 sends $b_{1} (X_{1}^{n})$ . Encoder 2 sends $b_{2} (X_{2}^{n})$ .

Decoder. Given bin indices $(i, j)$ , the decoder looks for the unique pair $(\tilde{x}_{1}^{n}, \tilde{x}_{2}^{n}) \in T_{ϵ}^{(n)}$ (jointly typical set) such that $b_{1} (\tilde{x}_{1}^{n}) = i$ and $b_{2} (\tilde{x}_{2}^{n}) = j$ . If there is exactly one such pair, output it. Otherwise, declare error.

Error analysis. An error occurs if:

$(X_{1}^{n}, X_{2}^{n}) \in / T_{ϵ}^{(n)}$ : probability $\to 0$ by the AEP.
There exists another jointly typical pair in the same bins: for a fixed $(\tilde{x}_{1}^{n}, \tilde{x}_{2}^{n}) \neq = (X_{1}^{n}, X_{2}^{n})$ in $T_{ϵ}^{(n)}$ , the probability that $b_{1} (\tilde{x}_{1}^{n}) = b_{1} (X_{1}^{n})$ is $2^{- n R_{1}}$ . Given $R_{1} = H (X_{1} ∣ X_{2}) + ϵ$ , the expected number of "impostor" pairs in the same bins is approximately $∣ T_{ϵ}^{(n)} ∣ \cdot 2^{- n (R_{1} + R_{2})} \approx 2^{n H (X_{1}, X_{2})} \cdot 2^{- n (H (X_{1} ∣ X_{2}) + ϵ + H (X_{2}))} = 2^{- n ϵ} \to 0$ .

By the union bound, $P_{e}^{(n)} \to 0$ as $n \to \infty$ . $□$

Bridge. The Slepian-Wolf theorem builds toward the entire network information theory framework by introducing random binning as the central tool for distributed coding. This is exactly the technique that reappears in Wyner-Ziv coding 46.05.02 for lossy compression with side information, where the binning rate is determined by the rate-distortion function rather than the conditional entropy. The result appears again in the Gelfand-Pinsker theorem 46.05.03, where binning is used in the channel coding context to pre-cancel known interference. The foundational reason binning works is that joint typicality provides a high-probability unique identification: with enough bins, the decoder can resolve the correct source pair from the bin indices alone. Putting these together, the Slepian-Wolf theorem is the central insight that correlation is a resource that can be exploited even without encoder cooperation, and the binning technique is the universal mechanism for exploiting it. The result generalises to multiple sources and provides the lossless foundation for the entire side-information strand of information theory.

Exercises Intermediate+

Exercise (medium, short answer).

For the Slepian-Wolf problem with $H (X_{1} ∣ X_{2}) = 0.5$ , $H (X_{2} ∣ X_{1}) = 0.5$ , $H (X_{1}, X_{2}) = 1.5$ , sketch the achievable rate region by listing its corner points.

Hint

The region is defined by three inequalities: $R_{1} \geq 0.5$ , $R_{2} \geq 0.5$ , $R_{1} + R_{2} \geq 1.5$ .

Answer

The corner points of the pentagonal region are:

$(R_{1}, R_{2}) = (1.0, 0.5)$ where $R_{1} = H (X_{1})$ and $R_{2} = H (X_{2} ∣ X_{1})$ .
$(R_{1}, R_{2}) = (0.5, 1.0)$ where $R_{1} = H (X_{1} ∣ X_{2})$ and $R_{2} = H (X_{2})$ .
The sum-rate corner: $(R_{1}, R_{2}) = (1.0, 0.5)$ and $(0.5, 1.0)$ are connected by the line $R_{1} + R_{2} = 1.5$ .

The full pentagon has vertices at $(1.0, 0.5)$ , $(1.0, \infty)$ — but bounded by practicality, the region extends upward and rightward. The key corners are where the sum-rate constraint is active: $(1.0, 0.5)$ and $(0.5, 1.0)$ .

Exercise (medium, short answer).

Explain the random binning argument in one paragraph. Why does the decoder succeed with high probability?

Hint

Think about how many sequences share a bin and how joint typicality resolves ambiguity.

Answer

Each source sequence is assigned to a random bin. The number of bins is chosen so that, for typical sequences, the expected number of jointly typical pairs sharing the same pair of bins is exponentially small. Specifically, there are about $2^{n H (X_{1}, X_{2})}$ jointly typical pairs but $2^{n (R_{1} + R_{2})}$ bin-pair combinations. When $R_{1} + R_{2} > H (X_{1}, X_{2})$ , the number of bin pairs exceeds the number of typical pairs, so each jointly typical pair is likely the unique one in its bin pair. The decoder finds it by searching for the unique jointly typical pair matching the received indices.

Exercise (hard, short answer).

Prove the Slepian-Wolf converse: if $(R_{1}, R_{2})$ is achievable, then $R_{1} \geq H (X_{1} ∣ X_{2})$ , $R_{2} \geq H (X_{2} ∣ X_{1})$ , and $R_{1} + R_{2} \geq H (X_{1}, X_{2})$ .

Hint

Use Fano's inequality and the chain rule for entropy, noting that $f_{1} (X_{1}^{n})$ is a function of $X_{1}^{n}$ only and $f_{2} (X_{2}^{n})$ is a function of $X_{2}^{n}$ only.

Answer

By Fano's inequality, $H (X_{1}^{n}, X_{2}^{n} ∣ f_{1} (X_{1}^{n}), f_{2} (X_{2}^{n})) \leq 1 + n P_{e} lo g ∣ X_{1} ∣∣ X_{2} ∣$ . When $P_{e} \to 0$ , this vanishes. Now:

$n H (X_{1}, X_{2}) = H (X_{1}^{n}, X_{2}^{n}) = I (X_{1}^{n}, X_{2}^{n}; f_{1}, f_{2}) + H (X_{1}^{n}, X_{2}^{n} ∣ f_{1}, f_{2}) .$

The mutual information term splits as:

$I (X_{1}^{n}, X_{2}^{n}; f_{1}, f_{2}) \leq H (f_{1}) + H (f_{2}) \leq n R_{1} + n R_{2} .$

So $n H (X_{1}, X_{2}) \leq n R_{1} + n R_{2} + 1 + n P_{e} lo g ∣ X_{1} ∣∣ X_{2} ∣$ , giving $R_{1} + R_{2} \geq H (X_{1}, X_{2})$ as $P_{e} \to 0$ .

For the individual bounds: $n R_{1} \geq H (f_{1}) \geq H (f_{1} ∣ X_{2}^{n}) \geq I (X_{1}^{n}; f_{1} ∣ X_{2}^{n})$ . Since $f_{1}$ is a function of $X_{1}^{n}$ only and $X_{2}^{n}$ is independent of $f_{1}$ given $X_{1}^{n}$ , we get $I (X_{1}^{n}; f_{1} ∣ X_{2}^{n}) = H (X_{1}^{n} ∣ X_{2}^{n}) - H (X_{1}^{n} ∣ f_{1}, X_{2}^{n}) \to n H (X_{1} ∣ X_{2})$ as $P_{e} \to 0$ . Hence $R_{1} \geq H (X_{1} ∣ X_{2})$ . Similarly for $R_{2}$ .

Exercise (hard, short answer).

Show that time-sharing between two achievable rate pairs yields another achievable rate pair. Why does this complete the achievability proof for the entire Slepian-Wolf region?

Hint

Use codes for different blocklengths and interleave them.

Answer

Let $(R_{1}^{(a)}, R_{2}^{(a)})$ and $(R_{1}^{(b)}, R_{2}^{(b)})$ be achievable via codes of blocklength $n$ . For time-sharing parameter $λ \in [0, 1]$ : use code $(a)$ for the first $λn$ symbols and code $(b)$ for the remaining $(1 - λ) n$ symbols. The resulting rate pair is $λ (R_{1}^{(a)}, R_{2}^{(a)}) + (1 - λ) (R_{1}^{(b)}, R_{2}^{(b)})$ , and the error probability is bounded by the maximum of the two codes' error probabilities. Since the Slepian-Wolf region is convex (it is a polytope), and we prove achievability at the corner points (where one rate equals the full entropy and the other equals the conditional entropy), time-sharing fills in the entire region.

Lean formalization Intermediate+

Mathlib does not define distributed source codes, random binning, or the Slepian-Wolf achievable region. The joint typicality predicate (needed for the decoder) is absent. The entropy inequalities defining the region — $R_{1} \geq H (X_{1} ∣ X_{2})$ , $R_{2} \geq H (X_{2} ∣ X_{1})$ , $R_{1} + R_{2} \geq H (X_{1}, X_{2})$ — require a formalized entropy calculus that does not exist. The random binning argument requires defining a random partition of $X^{n}$ into $2^{n R}$ bins and analyzing the probability that the decoder finds a unique jointly typical pair, which involves concentration arguments not available in the current Mathlib framework. This unit ships without formalization.

Advanced results Master

The strong converse

The strong converse for the Slepian-Wolf theorem, proved by Csiszar and Korner, shows that for rate tuples outside the achievable region, the error probability $P_{e}^{(n)} \to 1$ as $n \to \infty$ (not merely bounded away from zero). This strengthens the weak converse ( $P_{e}$ bounded below by a positive constant) and establishes that the Slepian-Wolf region is the exact boundary between vanishing and non-vanishing error.

The proof uses the method of types: the type class of a sequence constrains the possible codewords, and outside the achievable region, the number of sequences in each type class exceeds the number of distinguishable bin pairs by an exponential factor.

Slepian-Wolf for continuous sources

For continuous correlated sources (e.g., jointly Gaussian), the Slepian-Wolf theorem does not directly apply because the differential entropy can be negative and the notion of "lossless" reconstruction is not well-defined for continuous variables. However, the quantized version — where the sources are first quantized and then Slepian-Wolf coded — achieves the quantized conditional entropy rates in the limit of fine quantization.

For lossy reconstruction, the problem becomes the Berger-Tung inner bound (see 46.05.02), which provides an achievable region for distributed lossy compression that generalizes both Slepian-Wolf (at zero distortion) and Wyner-Ziv (when one source is available at the decoder).

Duality with the multiple-access channel

The Slepian-Wolf theorem has a remarkable duality with the multiple-access channel (MAC) capacity region. In the MAC, multiple transmitters send independent messages over a shared channel. The capacity region is:

R_{1} \leq I (X_{1}; Y ∣ X_{2}), R_{2} \leq I (X_{2}; Y ∣ X_{1}), R_{1} + R_{2} \leq I (X_{1}, X_{2}; Y) .

Comparing with Slepian-Wolf:

R_{1} \geq H (X_{1} ∣ X_{2}), R_{2} \geq H (X_{2} ∣ X_{1}), R_{1} + R_{2} \geq H (X_{1}, X_{2}) .

The inequalities reverse direction, and mutual information replaces conditional entropy. This duality reflects the complementary nature of source coding (compression, rates above entropy) and channel coding (communication, rates below capacity).

Practical Slepian-Wolf codes

The random binning argument is non-constructive. Practical Slepian-Wolf codes use channel codes (LDPC, turbo codes, polar codes) as binning functions. The idea: treat the correlation between $X_{1}$ and $X_{2}$ as a "virtual channel" $X_{2} = X_{1} \oplus Z$ , and use a syndrome-based channel code for $X_{1}$ . The syndrome of $X_{1}^{n}$ (with respect to a linear code parity-check matrix) serves as the bin index, and the decoder uses $X_{2}^{n}$ as "side information" to decode $X_{1}^{n}$ from the syndrome.

This approach achieves the Slepian-Wolf bound with practical, implementable codes and is the basis for distributed video coding, distributed compression in sensor networks, and the DISCUS (Distributed Source Coding Using Syndromes) system.

Synthesis. The Slepian-Wolf theorem is the foundational result of distributed source coding: two correlated sources encoded separately and decoded jointly achieve the same total rate as joint encoding. The achievable region is a pentagonal polytope defined by three entropy inequalities — $R_{1} \geq H (X_{1} ∣ X_{2})$ , $R_{2} \geq H (X_{2} ∣ X_{1})$ , $R_{1} + R_{2} \geq H (X_{1}, X_{2})$ — and the central insight is that random binning exploits correlation without encoder cooperation. The binning technique generalises to Wyner-Ziv coding 46.05.02 for lossy compression with side information and to Gelfand-Pinsker 46.05.03 for channels with state known at the transmitter. The result builds toward the multiple-access channel 46.06.01 through a source-channel duality: the Slepian-Wolf region and the MAC capacity region are mirror images with reversed inequalities and complementary information quantities. Putting these together, the Slepian-Wolf theorem is the central insight that correlation is a free resource that can be harvested even without communication between encoders, and the binning technique is the universal mechanism for doing so.

Full proof set Master

Proposition (Achievability at the corner point). The rate pair $(R_{1}, R_{2}) = (H (X_{1} ∣ X_{2}) + ϵ, H (X_{2}))$ is achievable.

Proof. Define $2^{n R_{1}}$ bins for $X_{1}^{n}$ and $2^{n R_{2}}$ bins for $X_{2}^{n}$ uniformly at random. Encoder 1 sends the bin index of $X_{1}^{n}$ ; encoder 2 sends the bin index of $X_{2}^{n}$ .

The decoder searches for the unique jointly typical pair in the received bins. By the AEP, $(X_{1}^{n}, X_{2}^{n}) \in T_{ϵ}^{(n)}$ with high probability. The number of jointly typical pairs is approximately $2^{n H (X_{1}, X_{2})}$ . The number of bin pairs is $2^{n (R_{1} + R_{2})} = 2^{n (H (X_{1} ∣ X_{2}) + ϵ + H (X_{2}))} = 2^{n (H (X_{1}, X_{2}) + ϵ)}$ . Since the number of bin pairs exceeds the number of typical pairs by a factor $2^{n ϵ}$ , each typical pair is unique in its bin pair with high probability.

The probability that an impostor pair (different from the true one) is jointly typical and shares the same bins is bounded by:

(\tilde{x}_{1}, \tilde{x}_{2}) \neq = (X_{1}, X_{2}) \sum 2^{- n (R_{1} + R_{2})} \cdot 2^{- n (I (X_{1}; X_{2}) - δ)} \leq 2^{n (H (X_{1}, X_{2}))} \cdot 2^{- n (R_{1} + R_{2})} \cdot 2^{- n (I (X_{1}; X_{2}) - δ)} .

Substituting $R_{1} + R_{2} = H (X_{1}, X_{2}) + ϵ$ and $I (X_{1}; X_{2}) = H (X_{1}, X_{2}) - H (X_{1} ∣ X_{2}) - H (X_{2} ∣ X_{1}) + H (X_{1}, X_{2})$ , the bound becomes $2^{- n (ϵ - δ)} \to 0$ for $δ < ϵ$ . $□$

Connections Master

46.02.02 — The source coding theorem is the single-source limit of Slepian-Wolf: when the sources are independent, the region collapses to two independent entropy bounds.
46.01.02 — Mutual information $I (X_{1}; X_{2}) = H (X_{1}) - H (X_{1} ∣ X_{2})$ quantifies the correlation that Slepian-Wolf exploits; the gap between independent and joint coding equals the mutual information.
46.05.02 — Wyner-Ziv coding extends Slepian-Wolf to lossy compression with decoder side information, using the same binning technique.
46.05.03 — Gelfand-Pinsker coding uses binning in the channel coding context, where the transmitter knows channel state non-causally.
46.06.01 — The MAC capacity region is dual to the Slepian-Wolf region, with mutual information replacing conditional entropy and inequalities reversed.
46.05.04 — Common information (Wyner and Gacs-Korner) quantifies how much of the correlation between $X_{1}$ and $X_{2}$ must be shared for distributed coding to match joint coding.

Historical & philosophical context Master

David Slepian and Jack Wolf published "Noiseless Coding of Correlated Information Sources" in the IEEE Transactions on Information Theory (IT-19, 1973, 471-480). The result was initially considered surprising because the naive expectation was that independent encoding would require each source to be compressed at its full entropy rate $H (X_{i})$ , yielding a total rate $H (X_{1}) + H (X_{2}) \geq H (X_{1}, X_{2})$ . Slepian and Wolf showed that the total rate could be reduced to the joint entropy $H (X_{1}, X_{2})$ without any communication between encoders.

The proof technique — random binning — was novel and has since become one of the most important tools in network information theory. The idea of randomly partitioning the space of source sequences into bins and using joint typicality for decoding appears repeatedly in the field: in Wyner-Ziv coding (1976), Gelfand-Pinsker coding (1980), the multiple-access channel, and the broadcast channel.

The practical relevance of Slepian-Wolf coding was not fully appreciated until the rise of sensor networks in the late 1990s and early 2000s. Pradhan and Ramchandran's DISCUS system (2003) demonstrated that practical Slepian-Wolf codes could be built using channel coding techniques (syndrome-based compression), connecting the theoretical binning argument to implementable systems.

Aarons El Gamal and Young-Han Kim's 2011 textbook Network Information Theory (Cambridge) provides the definitive modern treatment, showing that Slepian-Wolf coding sits at the foundation of the entire distributed source coding framework.

Bibliography Master

@article{slepian-wolf1973,
  author  = {Slepian, D. and Wolf, J. K.},
  title   = {Noiseless Coding of Correlated Information Sources},
  journal = {IEEE Transactions on Information Theory},
  volume  = {IT-19},
  pages   = {471--480},
  year    = {1973},
}
@book{cover-thomas2006,
  author    = {Cover, T. M. and Thomas, J. A.},
  title     = {Elements of Information Theory},
  edition   = {2nd},
  publisher = {Wiley},
  year      = {2006},
}
@book{csiszar-korner2011,
  author    = {Csisz{\'a}r, I. and K{\"o}rner, J.},
  title     = {Information Theory: Coding Theorems for Discrete Memoryless Systems},
  edition   = {2nd},
  publisher = {Cambridge University Press},
  year      = {2011},
}
@article{pradhan-ramchandran2003,
  author  = {Pradhan, S. S. and Ramchandran, K.},
  title   = {Distributed Source Coding Using Syndromes ({DISCUS}): Design and Construction},
  journal = {IEEE Transactions on Communications},
  volume  = {51},
  pages   = {1473--1481},
  year    = {2003},
}
@book{elgamal-kim2011,
  author    = {El Gamal, A. and Kim, Y.-H.},
  title     = {Network Information Theory},
  publisher = {Cambridge University Press},
  year      = {2011},
}

Prerequisites

46.02.02
46.01.02

Tier anchors

beginner: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §15.1-15.2 (two correlated sources compressed separately, the surprising result that separate encoding achieves the joint entropy rate)
intermediate: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §15.2-15.4 (the Slepian-Wolf achievable region, random binning argument, converse via the Slepian-Wolf theorem)
master: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §15.1-15.8; Slepian & Wolf 1973 Noiseless Coding of Correlated Information Sources; Csiszar & Korner 2011 Information Theory: Coding Theorems for Discrete Memoryless Systems 2e (Cambridge) §3.2-3.3

References

Slepian, D. & Wolf, J. K. — Noiseless Coding of Correlated Information Sources · IEEE Transactions on Information Theory IT-19 (1973) 471-480; the original paper establishing the achievable rate region for two correlated sources $(X_{1}, X_{2})$ encoded separately and decoded jointly: the set of rate pairs $(R_{1}, R_{2})$ satisfying $R_{1} \geq H (X_{1} ∣ X_{2})$ , $R_{2} \geq H (X_{2} ∣ X_{1})$ , and $R_{1} + R_{2} \geq H (X_{1}, X_{2})$ , proved via random binning for achievability and a strong converse.
Cover, T. M. & Thomas, J. A. — Elements of Information Theory (2nd ed.) · Wiley (2006). Section 15.1: the distributed source coding problem, motivation via sensor networks. Section 15.2: the Slepian-Wolf theorem statement and the achievable rate region. Section 15.3: achievability via random binning — assign each $x_{1}^{n}$ sequence to one of $2^{n R_{1}}$ bins uniformly at random, similarly for $x_{2}^{n}$ ; the decoder finds the unique jointly typical pair within the declared bins. Section 15.4: the converse.
Csiszar, I. & Korner, J. — Information Theory: Coding Theorems for Discrete Memoryless Systems (2nd ed.) · Cambridge University Press (2011). Section 3.2: the Slepian-Wolf theorem for multiple sources, the method of types proof of achievability. Section 3.3: the strong converse for the Slepian-Wolf problem, showing that rate pairs outside the achievable region have error probability bounded away from zero.

Estimated time

beginner: 20m
intermediate: 50m
master: 100m