Introduction

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.

Try It: The Rate Region

Every pair of correlated binary sources defines a rate region — the set of rate pairs (R1R_{1}, R2R_{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">
  Two correlated binary sources X and Y. Each bit of Y equals the corresponding bit of X
      with probability <b id="p-label">0.90</b> (correlation). The Slepian-Wolf region is the
      gray area below — every rate pair inside it is achievable without encoder cooperation.
</div>
<div class="controls">
  <label>Correlation p(Y=X): <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 a rate point:</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">Inside the achievable region ✓</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Slepian-Wolf rate region demo.
// Model: X ~ Bernoulli(0.5). Y flips X with probability epsilon = 1 - p.
// Joint: P(X=0,Y=0)=p/2, P(X=1,Y=1)=p/2, P(X=0,Y=1)=(1-p)/2, P(X=1,Y=0)=(1-p)/2
// H(X)=H(Y)=1 (uniform marginals), H(X|Y)=H(Y|X)=hb(epsilon), H(X,Y)=1+hb(epsilon)
// where hb(q) = -q*log2(q) - (1-q)*log2(1-q) is binary entropy.
//
// The Slepian-Wolf achievable region:
//   R1 >= H(X|Y) = hb(epsilon)
//   R2 >= H(Y|X) = hb(epsilon)
//   R1 + R2 >= H(X,Y) = 1 + hb(epsilon)
//
// Verification (node test vector, epsilon=0.1 => p=0.9):
//   hb(0.1) = -0.1*log2(0.1)-0.9*log2(0.9) ≈ 0.4690
//   H(X,Y)  = 1.4690   check: R1=0.55, R2=0.70 => sum=1.25 < 1.469 => OUTSIDE
//             R1=0.60, R2=0.90 => sum=1.50 >= 1.469 AND 0.60>=0.469 AND 0.90>=0.469 => INSIDE

const canvas = document.getElementById('chart');
const ctx = canvas.getContext('2d');
const W = canvas.width, H = canvas.height;
const PAD = { top: 20, right: 20, bottom: 40, left: 48 };
const PW = W - PAD.left - PAD.right;
const PH = H - PAD.top - PAD.bottom;

function hb(q) {
  if (q <= 0 || q >= 1) return 0;
  return -q * Math.log2(q) - (1 - q) * Math.log2(1 - q);
}

function getEntropies(p) {
  const eps = 1 - p;
  const hCond = hb(eps);
  const hJoint = 1 + hCond;
  return { hX: 1, hY: 1, hXgY: hCond, hYgX: hCond, hXY: hJoint };
}

// Map rate [0,1.2] to canvas pixel
function toX(r) { return PAD.left + (r / 1.2) * PW; }
function toY(r) { return PAD.top + PH - (r / 1.2) * PH; }

function drawChart(ents, r1Frac, r2Frac) {
  ctx.clearRect(0, 0, W, H);
  const { hXgY, hYgX, hXY } = ents;
  const maxR = 1.2;

  // Draw achievable region (gray fill)
  // The region is defined by R1>=hXgY, R2>=hYgX, R1+R2>=hXY, R1<=1, R2<=1
  // We trace the boundary polygon from the rectangle corners
  ctx.beginPath();
  // Start at (hXgY, hXY-hXgY) = lower-left corner of the full region
  // Actually trace the achievable polygon within [0,maxR]^2:
  // Corner points of the region boundary:
  // (hXgY, hXY - hXgY), then follow R1+R2=hXY up to (hXY-hYgX, hYgX)
  // But since hXgY=hYgX here, the diagonal corner is (hXgY, hYgX).
  // Polygon: (hXgY, hYgX) -> (1, hYgX) -> (1,1) -> (hXgY, 1) -> (hXgY, hYgX)
  // but also the part: if hXgY+hYgX < hXY, there's a "notch"
  // General polygon inside [0,maxR]^2:
  // Start bottom-left corner of achievable = (hXgY, hXY-hXgY) if hXY-hXgY >= hYgX
  //   else (hXY-hYgX, hYgX)
  // We'll just clip to maxR.
  const p1 = [hXgY, Math.max(hYgX, hXY - hXgY)]; // left side of diagonal
  const p2 = [Math.max(hXgY, hXY - hYgX), hYgX]; // bottom of diagonal
  const polygon = [
    p2,
    [Math.min(maxR, maxR), hYgX], // bottom-right
    [Math.min(maxR, maxR), Math.min(maxR, maxR)], // top-right
    [hXgY, Math.min(maxR, maxR)], // top-left
    p1,
  ];
  if (Math.abs(p1[0] - p2[0]) > 0.001 || Math.abs(p1[1] - p2[1]) > 0.001) {
    polygon.splice(4, 0, p1);
  }
  ctx.moveTo(toX(polygon[0][0]), toY(polygon[0][1]));
  for (let i = 1; i < polygon.length; i++) {
    ctx.lineTo(toX(polygon[i][0]), toY(polygon[i][1]));
  }
  ctx.closePath();
  ctx.fillStyle = 'rgba(180,200,220,0.35)';
  ctx.fill();
  ctx.strokeStyle = '#7aaac0';
  ctx.lineWidth = 1.5;
  ctx.stroke();

  // Axes
  ctx.strokeStyle = '#888';
  ctx.lineWidth = 1;
  ctx.beginPath();
  ctx.moveTo(PAD.left, PAD.top); ctx.lineTo(PAD.left, PAD.top + PH);
  ctx.lineTo(PAD.left + PW, PAD.top + PH);
  ctx.stroke();

  // Grid lines and axis labels
  ctx.fillStyle = '#999';
  ctx.font = '10px ui-monospace, monospace';
  ctx.textAlign = 'center';
  for (let v = 0; v <= 1.2; v += 0.3) {
    const vr = Math.round(v * 10) / 10;
    const gx = toX(vr);
    const gy = toY(vr);
    ctx.fillStyle = '#ccc';
    ctx.beginPath(); ctx.moveTo(gx, PAD.top); ctx.lineTo(gx, PAD.top + PH); ctx.stroke();
    ctx.beginPath(); ctx.moveTo(PAD.left, gy); ctx.lineTo(PAD.left + PW, gy); ctx.stroke();
    ctx.fillStyle = '#777';
    ctx.fillText(vr.toFixed(1), gx, PAD.top + PH + 14);
    ctx.textAlign = 'right';
    ctx.fillText(vr.toFixed(1), PAD.left - 4, gy + 4);
    ctx.textAlign = 'center';
  }

  // Axis labels
  ctx.fillStyle = '#444';
  ctx.font = '11px system-ui, sans-serif';
  ctx.fillText('R₁ (bits/sym)', PAD.left + PW / 2, H - 4);
  ctx.save();
  ctx.translate(12, PAD.top + PH / 2);
  ctx.rotate(-Math.PI / 2);
  ctx.fillText('R₂ (bits/sym)', 0, 0);
  ctx.restore();

  // Constraint lines
  ctx.setLineDash([4, 3]);
  ctx.lineWidth = 1.2;

  // R1 = H(X|Y)
  ctx.strokeStyle = '#e63946';
  ctx.beginPath(); ctx.moveTo(toX(hXgY), toY(0)); ctx.lineTo(toX(hXgY), toY(maxR)); ctx.stroke();
  ctx.fillStyle = '#e63946'; ctx.font = '9px system-ui'; ctx.textAlign = 'left';
  ctx.fillText('H(X|Y)', toX(hXgY) + 3, PAD.top + 12);

  // R2 = H(Y|X)
  ctx.strokeStyle = '#e63946';
  ctx.beginPath(); ctx.moveTo(toX(0), toY(hYgX)); ctx.lineTo(toX(maxR), toY(hYgX)); ctx.stroke();
  ctx.textAlign = 'left'; ctx.fillText('H(Y|X)', PAD.left + 3, toY(hYgX) - 4);

  // R1+R2 = H(X,Y) diagonal
  ctx.strokeStyle = '#2a9d8f';
  ctx.beginPath();
  const diagL = hXY; // at R2=0, R1=diagL; at R1=0, R2=diagL
  ctx.moveTo(toX(Math.min(diagL, maxR)), toY(Math.max(0, diagL - maxR)));
  ctx.lineTo(toX(Math.max(0, diagL - maxR)), toY(Math.min(diagL, maxR)));
  ctx.stroke();
  ctx.fillStyle = '#2a9d8f'; ctx.textAlign = 'left';
  const diagMidX = Math.min(diagL * 0.6, maxR * 0.9);
  ctx.fillText('R₁+R₂=H(X,Y)', toX(diagMidX) + 3, toY(diagL - diagMidX) - 5);

  ctx.setLineDash([]);

  // User's chosen rate point
  const r1 = r1Frac * maxR;
  const r2 = r2Frac * maxR;
  const inside = r1 >= hXgY && r2 >= hYgX && (r1 + r2) >= hXY;
  ctx.beginPath();
  ctx.arc(toX(r1), toY(r2), 6, 0, 2 * Math.PI);
  ctx.fillStyle = inside ? '#0a7d33' : '#c92f3c';
  ctx.fill();
  ctx.strokeStyle = '#fff';
  ctx.lineWidth = 2;
  ctx.stroke();

  return inside;
}

function update() {
  const p = parseInt(document.getElementById('corr').value) / 100;
  document.getElementById('corr-val').textContent = p.toFixed(2);
  document.getElementById('p-label').textContent = p.toFixed(2);

  const ents = getEntropies(p);
  const r1Frac = parseInt(document.getElementById('r1').value) / 100;
  const r2Frac = parseInt(document.getElementById('r2').value) / 100;

  // Bar widths (max bar = 100% at 1.2 bits)
  const pct = v => Math.round(v / 1.2 * 100) + '%';
  document.getElementById('bar-hx').style.width = pct(ents.hX);
  document.getElementById('bar-hy').style.width = pct(ents.hY);
  document.getElementById('bar-hxy').style.width = pct(ents.hXgY);
  document.getElementById('bar-hyx').style.width = pct(ents.hYgX);
  document.getElementById('bar-joint').style.width = pct(ents.hXY);
  document.getElementById('num-hx').textContent = ents.hX.toFixed(3);
  document.getElementById('num-hy').textContent = ents.hY.toFixed(3);
  document.getElementById('num-hxy').textContent = ents.hXgY.toFixed(3);
  document.getElementById('num-hyx').textContent = ents.hYgX.toFixed(3);
  document.getElementById('num-joint').textContent = ents.hXY.toFixed(3);

  const inside = drawChart(ents, r1Frac, r2Frac);
  const v = document.getElementById('verdict');
  const r1v = (r1Frac * 1.2).toFixed(3);
  const r2v = (r2Frac * 1.2).toFixed(3);
  if (inside) {
    v.textContent = fmt('(%r1v%, %r2v%) is inside the achievable region ✓', { r1v: r1v, r2v: r2v });
    v.className = 'verdict ok';
  } else {
    v.textContent = fmt('(%r1v%, %r2v%) is outside — lossless recovery impossible ✗', { r1v: r1v, r2v: r2v });
    v.className = 'verdict bad';
  }
}

document.getElementById('corr').addEventListener('input', update);
document.getElementById('r1').addEventListener('input', update);
document.getElementById('r2').addEventListener('input', update);
update();

// Node.js verification (runs silently in browser, used for node test):
// hb(0.1) = -0.1*log2(0.1) - 0.9*log2(0.9)
//         = 0.33219 + 0.13688 = 0.46907  ✓
// H(X,Y) = 1.46907
// (0.55, 0.70): 0.55>=0.469 ✓, 0.70>=0.469 ✓, 0.55+0.70=1.25 < 1.469 => OUTSIDE ✓
// (0.60, 0.90): 0.60>=0.469 ✓, 0.90>=0.469 ✓, 0.60+0.90=1.50 >= 1.469 => INSIDE ✓
// (0.20, 0.90): 0.20 < 0.469 => OUTSIDE ✓
Result
Console

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∣Y)H(X \mid Y) bits per symbol, the encoder for Y needs at least H(Y∣X)H(Y \mid X), and together they need at least H(X,Y)H(X,Y). The remarkable fact is that each encoder can achieve its corner of this region without knowing the other source at all.

The Real Theorem

Let X and Y be two correlated discrete memoryless sources. An encoder for X sees only XnX^{n} (n copies of X); an encoder for Y sees only YnY^{n}. A single decoder sees both compressed streams and must recover both XnX^{n} and YnY^{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 (R1R_{1}, R2R_{2}) is achievable if and only if

  • R1≥H(X∣Y)R_{1} \ge H(X \mid Y)
  • R2≥H(Y∣X)R_{2} \ge H(Y \mid X)
  • R1+R2≥H(X,Y)R_{1} + R_{2} \ge H(X, Y)

The three inequalities carve out a corner-shaped region in the R1R_{1}–R2R_{2} plane. The achievability proof uses random binning: each encoder assigns each possible length-n sequence independently and uniformly at random to one of 2nR2^{nR} bins, then transmits the bin index. The decoder receives both bin indices and uses joint typicality to find the unique pair (xnx^{n}, yny^{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 R1=H(X∣Y)R_{1} = H(X \mid Y), encoder 1 uses only H(X∣Y)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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/slepian-wolf/Content licensed under CC BY-NC 4.0.