Slepian-Wolf Coding

Imagine two weather sensors a kilometer apart. Both measure temperature, so their readings are almost always within a degree of each other — they are correlated. If you want to send both readings to a base station, the naive approach compresses each one independently. But that wastes bandwidth, because the second reading carries almost no new information once you already know the first.

The obvious fix is to let the sensors talk to each other: sensor B sends only the difference from sensor A, and together they need far fewer bits. But what if the sensors have no radio link between them? What if each encoder must compress its stream in complete isolation, without seeing the other source at all?

Common sense says you lose something — if the encoders cannot cooperate, they cannot exploit the correlation. In 1973, David Slepian and Jack Wolf turned common sense on its head. They proved that two correlated sources, each compressed separately, can together achieve the same total bit-rate as if the encoders had a perfect communication link — provided the decoder sees both compressed streams at once.

The theorem is a cornerstone of distributed source coding and information theory. It shows that, for lossless compression, the correlation does not have to be exploited at encoding time. The decoder alone can do all the work, as long as the rates are chosen carefully.

Every pair of correlated binary sources defines a rate region — the set of rate pairs ($R_{1}$, $R_{2}$) that allow lossless recovery of both sources. The Slepian-Wolf theorem pins down this region exactly. Use the demo below to explore it.

<div class="hint">
  {{hint}}
</div>
<div class="controls">
  <label>{{corr_label}} <input type="range" id="corr" min="50" max="99" value="90" step="1"></label>
  <span class="corr-val" id="corr-val">0.90</span>
</div>
<canvas id="chart" width="320" height="280"></canvas>
<div class="rates">
  <div class="rate-row">
    <span class="rate-name">H(X)</span>
    <div class="bar-wrap"><div class="bar bar-x" id="bar-hx"></div></div>
    <span class="rate-num" id="num-hx">1.000</span> {{bits_sym}}
  </div>
  <div class="rate-row">
    <span class="rate-name">H(Y)</span>
    <div class="bar-wrap"><div class="bar bar-y" id="bar-hy"></div></div>
    <span class="rate-num" id="num-hy">1.000</span> {{bits_sym}}
  </div>
  <div class="rate-row">
    <span class="rate-name">H(X|Y)</span>
    <div class="bar-wrap"><div class="bar bar-cond" id="bar-hxy"></div></div>
    <span class="rate-num" id="num-hxy">0.469</span> {{bits_sym}}
  </div>
  <div class="rate-row">
    <span class="rate-name">H(Y|X)</span>
    <div class="bar-wrap"><div class="bar bar-cond" id="bar-hyx"></div></div>
    <span class="rate-num" id="num-hyx">0.469</span> {{bits_sym}}
  </div>
  <div class="rate-row">
    <span class="rate-name">H(X,Y)</span>
    <div class="bar-wrap"><div class="bar bar-joint" id="bar-joint"></div></div>
    <span class="rate-num" id="num-joint">1.469</span> {{bits_sym}}
  </div>
</div>
<div class="point-controls">
  <b>{{pick_rate}}</b>
  <label>R₁ <input type="range" id="r1" min="0" max="100" value="55" step="1"></label>
  <label>R₂ <input type="range" id="r2" min="0" max="100" value="70" step="1"></label>
  <div class="verdict" id="verdict">{{verdict_inside}}</div>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.hint { font-size: .88rem; color: #444; margin-bottom: .7rem; line-height: 1.45; }
.controls { display: flex; align-items: center; gap: .6rem; margin-bottom: .6rem; flex-wrap: wrap; }
.controls label { display: flex; align-items: center; gap: .4rem; font-size: .88rem; }
.controls input[type=range] { width: 120px; }
.corr-val { font-weight: 700; color: #1d3557; min-width: 2.2rem; }
canvas { border: 1px solid #cdd9e3; border-radius: 8px; display: block; margin: .5rem 0; background: #f8fafc; max-width: 100%; }
.rates { display: flex; flex-direction: column; gap: .3rem; margin: .5rem 0; }
.rate-row { display: flex; align-items: center; gap: .4rem; }
.rate-name { min-width: 4.2rem; font-size: .82rem; color: #555; font-family: ui-monospace, monospace; }
.bar-wrap { flex: 1; height: 12px; background: #e8eef3; border-radius: 6px; overflow: hidden; }
.bar { height: 100%; border-radius: 6px; transition: width .3s; }
.bar-x { background: #457b9d; }
.bar-y { background: #1d3557; }
.bar-cond { background: #e63946; }
.bar-joint { background: #2a9d8f; }
.rate-num { font-size: .82rem; font-family: ui-monospace, monospace; min-width: 3.4rem; color: #333; }
.point-controls { margin-top: .6rem; display: flex; flex-direction: column; gap: .3rem; }
.point-controls b { font-size: .88rem; }
.point-controls label { display: flex; align-items: center; gap: .4rem; font-size: .85rem; }
.point-controls input[type=range] { width: 150px; }
.verdict { font-weight: 700; font-size: .95rem; margin-top: .25rem; padding: .3rem .6rem; border-radius: 6px; }
.verdict.ok { background: #d4f7e7; color: #0a7d33; }
.verdict.bad { background: #fde8e8; color: #c92f3c; }

// Code not found

Move the correlation slider to change how similar the two sources are. The gray region in the plot is all the rate pairs that are achievable — the encoder for source X needs at least $H(X \mid Y)$ bits per symbol, the encoder for Y needs at least $H(Y \mid X)$, and together they need at least $H(X,Y)$. The remarkable fact is that each encoder can achieve its corner of this region without knowing the other source at all.

Let X and Y be two correlated discrete memoryless sources. An encoder for X sees only $X^{n}$ (n copies of X); an encoder for Y sees only $Y^{n}$. A single decoder sees both compressed streams and must recover both $X^{n}$ and $Y^{n}$ perfectly (with vanishing error probability as n grows).

The Slepian-Wolf rate region (proved in 1973, exact — not just an achievability result):

A rate pair ($R_{1}$, $R_{2}$) is achievable if and only if

• $R_{1} \ge H(X \mid Y)$
• $R_{2} \ge H(Y \mid X)$
• $R_{1} + R_{2} \ge H(X, Y)$

The three inequalities carve out a corner-shaped region in the $R_{1}$–$R_{2}$ plane. The achievability proof uses random binning: each encoder assigns each possible length-n sequence independently and uniformly at random to one of $2^{nR}$ bins, then transmits the bin index. The decoder receives both bin indices and uses joint typicality to find the unique pair ($x^{n}$, $y^{n}$) that is jointly typical and consistent with both bin indices. With high probability — when n is large and rates satisfy the conditions — only the true pair is jointly typical.

The converse (you cannot do better) follows from standard entropy inequalities and Fano's inequality.

What makes this stunning: when $R_{1} = H(X \mid Y)$, encoder 1 uses only $H(X \mid Y)$ bits per symbol — exactly what it would use if it could see Y. Yet it cannot. The decoder reconstructs both sources jointly, effectively doing the cooperation that the encoders skipped.

This is the distributed analogue of Shannon's source coding theorem: just as a single source can be compressed to its entropy, two correlated sources can each be compressed to their conditional entropy — just not decoded alone.

The Slepian-Wolf theorem is not just beautiful theory — it shapes the design of real systems wherever correlated data must be compressed without encoder cooperation:

• Sensor networks: A field of wireless sensors monitoring the same phenomenon can each compress independently and transmit to a base station. The Slepian-Wolf limit tells engineers the minimum rates needed without requiring the sensors to sync with each other.
• Distributed video coding (Wyner-Ziv coding): The lossy generalization — proved by Wyner and Ziv (1976) — shows that a video encoder need not see previous frames to achieve the rate-distortion bound, as long as the decoder has them. This underpins distributed video coding schemes used in low-power cameras.
• Multi-view video: Adjacent cameras in a video array capture correlated scenes. Slepian-Wolf principles allow each camera to compress without communicating with its neighbors.
• DNA storage and genomic compression: Genomic sequences from related individuals are highly correlated. Distributed coding reduces the cost of archiving large genomic databases.
• Network coding: Multi-terminal information theory, launched by Slepian and Wolf, became the foundation for network coding and modern distributed storage systems.

The theorem also set the research agenda for decades. The Wyner-Ziv problem (lossy version), the multiple-access channel, the broadcast channel — all were tackled using ideas from the original 1973 paper.

The Slepian-Wolf theorem carries a counterintuitive message: cooperation at the encoder is free. Two sources that are deeply correlated can each be compressed by an encoder that is completely blind to the other, and together they hit the same total rate as if the encoders had shared every bit — as long as the decoder sees both streams.

The proof idea is elegant: random binning turns the decoder's problem into a search for the uniquely jointly typical pair, and the math guarantees that search succeeds when the rates satisfy the three corner inequalities.

This insight cascades through information theory. Every distributed system that compresses correlated data — sensor networks, multi-view video, genomic archives — borrows from the lesson Slepian and Wolf taught in 1973: the decoder, not the encoder, is where correlation should be exploited.

For more on the compression of a single source, see Shannon's source coding theorem. For the lossy generalization, look up Wyner-Ziv coding.