Network Information Theory · Vaibhav on HTTPS

Motivation: from one wire to a telegraph network

Every result so far had one sender and one receiver. A real telegraph company runs a network:

many offices share one trunk line into the central exchange;
one office broadcasts a market report to every subscriber;
repeater stations relay a weak signal along a long route;
two offices on a party line talk over each other;
two weather stations in neighbouring cities report correlated readings to one headquarters.

Each adds something the single-user theory never faced:

New element	What it means
Interference	Other senders’ signals arrive mixed with yours.
Cooperation	Nodes can help each other, for example by relaying or coordinating.
Feedback	What a node hears can shape what it sends next.
Correlated sources	Separate encoders hold data that partly overlap.

DefinitionGeneral communication network

$m$ nodes. At each time, node $i$ sends a symbol $x^{(i)}$ that depends on its own messages and on what it has received so far. The joint transmission $(x^{(1)}, \ldots, x^{(m)})$ produces received symbols $(Y^{(1)}, \ldots, Y^{(m)})$ according to a channel $p(y^{(1)}, \ldots, y^{(m)} \mid x^{(1)}, \ldots, x^{(m)})$ , which captures both noise and interference. If $p$ takes only the values 0 and 1, the network is deterministic.

WarningThe general problem is unsolved

“Given the sources and the channel, can the sources be delivered?” combines distributed source coding with distributed channel coding, and has no general answer. This note works through the special cases that are solved, and the cut-set upper bound that holds everywhere.

IntuitionInformation is not water

For water in pipes, the maximum flow from $A$ to $B$ equals the minimum capacity of any cut separating them (Ford–Fulkerson). The cut bound is easy because no flow can cross a cut faster than its pipes allow, and it is always achievable. For information, the cut-set bound (General multiterminal networks) still holds, but it is not achievable in general. Some networks, such as the degraded relay channel, do have a max-flow min-cut answer; most don’t. (Compare random flow-network capacity.)

For the pipe network in the book’s figure (edges $C_1, \ldots, C_5$ ), $C = \min\{C_1 + C_2,\ C_2 + C_3 + C_4,\ C_4 + C_5,\ C_1 + C_5\}$ , one term per cut.

NoteBackground from chapters not yet in these notes

This chapter builds on channel capacity and the channel coding theorem (channel-capacity, Chapter 7), the Gaussian channel (gaussian-channel, Chapter 9) and rate distortion theory (rate-distortion-theory, Chapter 10). The only facts used here are their headline results: capacity is $\max I(X;Y)$ , the Gaussian channel has capacity $\frac12\log(1 + P/N)$ , and the rate distortion function is a minimized mutual information.

Gaussian multiple-user channels: the preview

The Gaussian versions give concrete, easily interpreted answers. This section states them without proof; the discrete theorems behind them come later.

DefinitionGaussian channel capacity function

$\mathcal{C}(x) = \frac12\log(1 + x)$

the capacity, in bits per transmission, of an additive white Gaussian noise channel $Y = X + Z$ , $Z \sim \mathcal{N}(0, N)$ , with input power $P$ and signal-to-noise ratio $x = P/N$ .

Single user

RemarkMinimum distance is joint typicality

For $R < \mathcal{C}(P/N)$ , pick a good $(2^{nR}, n)$ codebook of power $P$ , send codeword $X(w)$ , and decode to the codeword nearest the received $Y$ . For Gaussian noise this minimum-distance rule is essentially the same as looking for the codeword that is jointly typical with $Y$ .

Multiple access: $m$ users, one receiver

$Y = \sum_{i=1}^m X_i + Z$

TheoremGaussian multiple-access region (equal powers $P$ )

$\sum_{i \in S} R_i < \mathcal{C}\!\left(\frac{|S|\,P}{N}\right) \quad \text{for every subset } S \text{ of users}$

When all rates are equal, the full-sum constraint $\sum_{i=1}^m R_i < \mathcal{C}(mP/N)$ is the binding one.

IntuitionThe cocktail party

The total rate $\mathcal{C}(mP/N)$ grows without bound as $m$ grows. A listener at a party with $m$ guests, each talking at power $P$ , receives unboundedly much information in total, even though interference grows. The rate per guest, $\frac1m\mathcal{C}(mP/N)$ , goes to 0. And the optimal scheme is not time-division: every sender uses all the bandwidth all the time.

Broadcast: one sender, two receivers

$Y_1 = X + Z_1$ , $Y_2 = X + Z_2$ , noise variances $N_1 < N_2$ (receiver 1 is the better one).

TheoremGaussian broadcast region

$R_1 < \mathcal{C}\!\left(\frac{\alpha P}{N_1}\right), \qquad R_2 < \mathcal{C}\!\left(\frac{(1-\alpha)P}{\alpha P + N_2}\right), \qquad 0 \le \alpha \le 1$

where $\alpha$ is the fraction of power devoted to the good receiver’s private message.

AlgorithmSuperposition and successive cancellation

Two codebooks: rate $R_1$ at power $\alpha P$ , and rate $R_2$ at power $(1-\alpha)P$ .
Send the sum of the codeword for $w_1$ and the codeword for $w_2$ .
Bad receiver: decode its own codeword, treating the other message as noise, which gives effective SNR $\frac{(1-\alpha)P}{\alpha P + N_2}$ .
Good receiver: first decode the bad receiver’s codeword (possible, since its noise is lower), subtract it, then decode its own codeword from what remains.

IntuitionThe good receiver gets everything

A free bonus of optimal degraded broadcast coding: the better receiver always learns the worse receiver’s message too.

Relay: a repeater station

$Y_1 = X + Z_1, \qquad Y = X + Z_1 + X_1 + Z_2$

The relay hears $Y_1$ and transmits $X_{1i} = f_i(Y_{11}, \ldots, Y_{1,i-1})$ , using only the past. The sender has power $P$ , the relay $P_1$ , and the noises $Z_1, Z_2$ are independent with variances $N_1, N_2$ .

TheoremGaussian relay capacity

With $\bar\alpha = 1 - \alpha$ ,

$C = \max_{0 \le \alpha \le 1}\ \min\left\{\mathcal{C}\!\left(\frac{P + P_1 + 2\sqrt{\bar\alpha P P_1}}{N_1 + N_2}\right),\ \mathcal{C}\!\left(\frac{\alpha P}{N_1}\right)\right\}$

If $\frac{P_1}{N_2} \ge \frac{P}{N_1}$ , then $\alpha = 1$ is optimal and $C = \mathcal{C}(P/N_1)$ .

IntuitionThe relay can make the second hop disappear

Without the relay the rate is $\mathcal{C}\big(\frac{P}{N_1 + N_2}\big)$ , which is near 0 when $N_2$ is large. A strong enough relay ( $P_1/N_2 \ge P/N_1$ ) makes the channel look noiseless after the relay, so the rate becomes the rate of the first hop alone, $\mathcal{C}(P/N_1)$ .

IntuitionHow the relay scheme works

Messages are sent in blocks, and the receiver runs one block behind.

In block $i$ the sender sends a fresh codeword (power $\alpha P$ ). The relay can decode it, because $R_1 < \mathcal{C}(\alpha P/N_1)$ . The receiver can’t; it only narrows it down to a list of candidates.
The codebook is randomly partitioned into cells. In block $i+1$ , the sender and relay together send the index of the cell containing the previous codeword, using a second codebook. They send it coherently, so the receiver sees power $(\sqrt{\bar\alpha P} + \sqrt{P_1})^2$ .
The receiver decodes the cell index, intersects that cell with its list from block $i$ , and is left with a single codeword.

The $2\sqrt{\bar\alpha PP_1}$ term in the capacity is the coherent-combining gain.

Interference: two pairs talking over each other

$Y_1 = X_1 + aX_2 + Z_1, \qquad Y_2 = X_2 + aX_1 + Z_2, \qquad Z_i \sim \mathcal{N}(0, N)$

TheoremStrong interference costs nothing

The interference channel is unsolved in general, even for Gaussian noise. But if the interference is strong, $\mathcal{C}\big(\frac{a^2P}{P+N}\big) > \mathcal{C}\big(\frac PN\big)$ , i.e. $a^2 > 1 + \frac PN$ , then each pair achieves $\mathcal{C}(P/N)$ , as if there were no interference at all.

IntuitionDecode the interference first

When the crosstalk is loud enough, receiver 1 can decode sender 2’s codeword (treating its own sender as noise), subtract it, and be left with a clean channel from sender 1. Strong interference is easier than moderate interference, because it can be decoded and removed.

Two-way: a full-duplex line

TheoremThe Gaussian two-way channel decomposes

The two-way channel adds feedback: each sender also hears the line and can adapt. Its capacity region is unknown in general (Shannon gave upper and lower bounds). For Gaussian channels the bounds coincide: each receiver subtracts its own transmitted codeword, which it knows, leaving a clean channel. So

$R_1 < \mathcal{C}(P_1/N_1), \qquad R_2 < \mathcal{C}(P_2/N_2)$

simultaneously. For a general two-way channel the two directions trade off and both can’t run at full rate.

Jointly typical sequences

The single-user typical set of the AEP note now has to handle many variables at once and every subset of them.

Setup. $(X^{(1)}, \ldots, X^{(k)})$ has a fixed joint distribution. For an ordered subset $S$ of these variables, take $n$ i.i.d. copies, so $\Pr\{\mathbf S = \mathbf s\} = \prod_{i=1}^n \Pr\{S_i = s_i\}$ . By the law of large numbers, for every one of the $2^k$ subsets,

$-\frac1n\log p(S_1, \ldots, S_n) \longrightarrow H(S)$

DefinitionJointly $\epsilon$ -typical set

$A_\epsilon^{(n)} = \left\{(\mathbf x_1, \ldots, \mathbf x_k) : \left|-\frac1n\log p(\mathbf s) - H(S)\right| < \epsilon \ \text{ for every subset } S\right\}$

and $A_\epsilon^{(n)}(S)$ is its restriction to the coordinates in $S$ .

ConventionExponential equality with slack

$a_n \doteq 2^{n(b \pm \epsilon)}$ means $\left|\frac1n\log a_n - b\right| < \epsilon$ for $n$ large enough. This is a version of first-order exponential equality that keeps track of the slack.

TheoremJoint AEP

For any $\epsilon > 0$ and $n$ large enough:

$P\big(A_\epsilon^{(n)}(S)\big) \ge 1 - \epsilon$ for every subset $S$ ;
$\mathbf s \in A_\epsilon^{(n)}(S) \Rightarrow p(\mathbf s) \doteq 2^{-n(H(S) \pm \epsilon)}$ ;
$\big|A_\epsilon^{(n)}(S)\big| \doteq 2^{n(H(S) \pm 2\epsilon)}$ ;
if $(\mathbf s_1, \mathbf s_2) \in A_\epsilon^{(n)}(S_1, S_2)$ , then $p(\mathbf s_1 \mid \mathbf s_2) \doteq 2^{-n(H(S_1\mid S_2) \pm 2\epsilon)}$ .

ProofSame arguments as the single-variable AEP

1: the law of large numbers, for each of finitely many subsets. 2: the definition. 3: sum probabilities over the set, using the lower bound on each term ( $\le 1$ ) and the upper bound ( $\ge 1 - \epsilon$ ), as in the AEP size bounds. 4: divide the joint estimate $2^{-n(H(S_1,S_2)\pm\epsilon)}$ by the marginal estimate $2^{-n(H(S_2)\pm\epsilon)}$ ; the errors add.

∎

TheoremConditionally typical sets

Let $A_\epsilon^{(n)}(S_1 \mid \mathbf s_2)$ be the $\mathbf s_1$ sequences jointly typical with a fixed $\mathbf s_2$ . If $\mathbf s_2$ is typical, then for large $n$

$\big|A_\epsilon^{(n)}(S_1 \mid \mathbf s_2)\big| \le 2^{n(H(S_1 \mid S_2) + 2\epsilon)}, \qquad (1-\epsilon)2^{n(H(S_1\mid S_2) - 2\epsilon)} \le \sum_{\mathbf s_2} p(\mathbf s_2)\big|A_\epsilon^{(n)}(S_1 \mid \mathbf s_2)\big|$

TheoremChance that conditionally independent sequences look jointly typical

Draw the three blocks as if $S_1$ and $S_2$ were conditionally independent given $S_3$ , keeping the true pairwise marginals:

$P(\mathbf s_1, \mathbf s_2, \mathbf s_3) = \prod_{i=1}^n p(s_{1i}\mid s_{3i})\,p(s_{2i}\mid s_{3i})\,p(s_{3i})$

Then the probability that they land in the true joint typical set is

$P\{(\mathbf S_1, \mathbf S_2, \mathbf S_3) \in A_\epsilon^{(n)}\} \doteq 2^{-n(I(S_1;S_2\mid S_3) \pm 6\epsilon)}$

ProofCount the set, times the probability of each element

$\sum_{A_\epsilon^{(n)}} p(\mathbf s_3)p(\mathbf s_1 \mid \mathbf s_3)p(\mathbf s_2 \mid \mathbf s_3) \doteq 2^{n(H(S_1,S_2,S_3)\pm\epsilon)}\,2^{-n(H(S_3)\pm\epsilon)}\,2^{-n(H(S_1\mid S_3)\pm2\epsilon)}\,2^{-n(H(S_2\mid S_3)\pm2\epsilon)}$

The exponent is $H(S_1,S_2,S_3) - H(S_3) - H(S_1\mid S_3) - H(S_2 \mid S_3) = -I(S_1;S_2\mid S_3)$ .

∎

ImportantThe engine of every achievability proof

In each random-coding proof below, an error happens when a wrong codeword, generated independently of what was actually sent, happens to look jointly typical with what was received. This theorem says that happens with probability about $2^{-nI}$ . With $2^{nR}$ wrong codewords, the union bound gives an error term $2^{n(R - I)}$ , which vanishes iff $R < I$ . Every rate constraint in this chapter is “number of confusable candidates times $2^{-nI}$ must vanish.”

The multiple-access channel

Two or more senders, one receiver: ground stations to a satellite, phones to a base station, telegraph offices sharing one trunk line. Each sender fights the noise and the other senders.

flowchart LR
  W1["Message W1"] --> X1["Encoder 1: X1"]
  W2["Message W2"] --> X2["Encoder 2: X2"]
  X1 --> C["Channel p of y given x1 and x2"]
  X2 --> C
  C --> Y["Y"] --> D["Decoder: estimates of W1 and W2"]

DefinitionDiscrete memoryless multiple-access channel and its codes

Alphabets $\mathcal X_1, \mathcal X_2, \mathcal Y$ and a transition matrix $p(y \mid x_1, x_2)$ . A $((2^{nR_1}, 2^{nR_2}), n)$ code has message sets $\mathcal W_j = \{1, \ldots, 2^{nR_j}\}$ , encoders $X_j : \mathcal W_j \rightarrow \mathcal X_j^n$ (each sees only its own message), and a decoder $g : \mathcal Y^n \rightarrow \mathcal W_1 \times \mathcal W_2$ . The messages are independent and uniform, and the average error probability is

$P_e^{(n)} = \frac{1}{2^{n(R_1+R_2)}}\sum_{(w_1,w_2)}\Pr\{g(Y^n) \ne (w_1,w_2) \mid (w_1,w_2)\text{ sent}\}$

A rate pair is achievable if some sequence of codes has $P_e^{(n)} \rightarrow 0$ . The capacity region is the closure of the achievable pairs.

TheoremMultiple-access channel capacity (Ahlswede; Liao)

The capacity region is the closure of the convex hull of all $(R_1, R_2)$ with

$R_1 < I(X_1; Y \mid X_2), \qquad R_2 < I(X_2; Y \mid X_1), \qquad R_1 + R_2 < I(X_1, X_2; Y)$

for some product distribution $p_1(x_1)p_2(x_2)$ .

IntuitionOne bound per way the decoder can be wrong

Constraint	Error it prevents
$R_1 < I(X_1;Y\mid X_2)$	Sender 2 decoded correctly, sender 1 wrong. Given $X_2$ , it’s a single-user channel for sender 1.
$R_2 < I(X_2;Y\mid X_1)$	The same with roles swapped.
$R_1 + R_2 < I(X_1,X_2;Y)$	Both wrong. There are $2^{n(R_1+R_2)}$ such pairs to rule out.

Product distributions appear because the senders can’t coordinate: each encodes its own message independently.

Examples

ExampleTwo independent binary symmetric channels

If the two senders use separate BSCs with crossover probabilities $p_1$ and $p_2$ , they don’t interact, and the region is the rectangle $R_1 \le 1 - H(p_1)$ , $R_2 \le 1 - H(p_2)$ .

ExampleBinary multiplier channel, $Y = X_1X_2$

Setting $X_2 = 1$ gives sender 1 a clean bit per use, and vice versa. The output is binary, so $R_1 + R_2 \le 1$ . Time-sharing achieves every point of that triangle, so the region is $\{R_1 + R_2 \le 1\}$ .

ExampleBinary erasure multiple-access channel, $Y = X_1 + X_2$

Binary inputs, output in $\{0, 1, 2\}$ . Outputs 0 and 2 determine both inputs; output 1 could be $(0,1)$ or $(1,0)$ .

Silencing either sender gives the other a full bit: $(1,0)$ and $(0,1)$ .
If sender 1 runs at $R_1 = 1$ , its codewords look like fair coin flips, and sender 2 sees a binary erasure channel with erasure probability $\frac12$ ( $Y = 1$ is an erasure). That has capacity $\frac12$ , so $(1, \frac12)$ is achievable.

The region is $R_1 \le 1$ , $R_2 \le 1$ , $R_1 + R_2 \le \frac32$ . The sum rate $\frac32 = H(Y)$ for uniform inputs beats time-sharing’s 1.

Achievability

ProofRandom codebooks, jointly typical decoding, union bound

Fix $p_1(x_1)p_2(x_2)$ .

Codebooks. Generate $2^{nR_1}$ codewords $\mathbf X_1(i)$ i.i.d. $\sim \prod p_1(x_{1i})$ , and independently $2^{nR_2}$ codewords $\mathbf X_2(j) \sim \prod p_2(x_{2i})$ . Reveal them to everyone.

Encoding / decoding. Sender 1 sends $\mathbf X_1(i)$ , sender 2 sends $\mathbf X_2(j)$ . The receiver outputs the unique $(i,j)$ with $(\mathbf x_1(i), \mathbf x_2(j), \mathbf y) \in A_\epsilon^{(n)}$ , and declares an error if there is none or several.

Error. By symmetry, assume $(1,1)$ was sent, and let $E_{ij} = \{(\mathbf X_1(i), \mathbf X_2(j), \mathbf Y) \in A_\epsilon^{(n)}\}$ . By the union bound,

$P_e^{(n)} \le P(E_{11}^c) + \sum_{i\ne1}P(E_{i1}) + \sum_{j\ne1}P(E_{1j}) + \sum_{i\ne1,j\ne1}P(E_{ij})$

$P(E_{11}^c) \rightarrow 0$ by the joint AEP.
For $i \ne 1$ , $\mathbf X_1(i)$ is independent of $(\mathbf X_2(1), \mathbf Y)$ , so

$P(E_{i1}) \le |A_\epsilon^{(n)}|\,2^{-n(H(X_1)-\epsilon)}2^{-n(H(X_2,Y)-\epsilon)} \le 2^{-n(I(X_1;X_2,Y) - 3\epsilon)} = 2^{-n(I(X_1;Y\mid X_2)-3\epsilon)}$

using $I(X_1; X_2, Y) = I(X_1;X_2) + I(X_1;Y\mid X_2)$ with $I(X_1;X_2) = 0$ (independent inputs).
Likewise $P(E_{1j}) \le 2^{-n(I(X_2;Y\mid X_1)-3\epsilon)}$ and $P(E_{ij}) \le 2^{-n(I(X_1,X_2;Y)-4\epsilon)}$ .

$P_e^{(n)} \le \epsilon + 2^{nR_1}2^{-n(I(X_1;Y\mid X_2)-3\epsilon)} + 2^{nR_2}2^{-n(I(X_2;Y\mid X_1)-3\epsilon)} + 2^{n(R_1+R_2)}2^{-n(I(X_1,X_2;Y)-4\epsilon)}$

Each term vanishes under the theorem’s three conditions. The average over random codebooks is small, so some codebook is good.

∎

The pentagon and its corners

For a fixed product distribution, the region is a pentagon:

Point	Rates	How to achieve it
A	$(I(X_1;Y\mid X_2),\ 0)$	Sender 2 stays silent but helpful: it fixes $X_2 = x_2$ , the value that best serves sender 1.
B	$(I(X_1;Y\mid X_2),\ I(X_2;Y))$	Decode sender 2 first, treating sender 1 as noise; subtract; then decode sender 1.
C	$(I(X_1;Y),\ I(X_2;Y\mid X_1))$	The same with the order reversed.
D	$(0,\ I(X_2;Y\mid X_1))$	Mirror of A.
Edge B–C	Sum rate $I(X_1,X_2;Y)$	Time-sharing between B and C.

DerivationWhy A uses one fixed input of the silent sender

$I(X_1;Y\mid X_2) = \sum_{x_2}p_2(x_2)I(X_1;Y\mid X_2 = x_2) \le \max_{x_2}I(X_1;Y\mid X_2 = x_2)$ , because an average is at most a maximum. So the best thing a silent sender 2 can do is transmit the single symbol most helpful to sender 1.

IntuitionOnion peeling

At corner B, the receiver decodes one user, peels that codeword off, and is left with a single-user channel for the other, averaged over the symbols of the peeled codeword. “Decode some signals, treat the rest as noise, subtract, repeat” recurs throughout this chapter: broadcast decoding, strong interference, Gaussian multiple access.

TheoremThe capacity region is convex

If $\mathbf R$ and $\mathbf R'$ are achievable, so is $\lambda\mathbf R + (1-\lambda)\mathbf R'$ .

ProofUse one code for

\lambda n

symbols and the other for the rest

The combined code has $2^{n\lambda R_1}2^{n(1-\lambda)R_1'}$ codewords for sender 1, which is rate $\lambda R_1 + (1-\lambda)R_1'$ . Its error probability is at most the sum of the two segments’ error probabilities.

∎

WarningConvex hull of regions ≠ region of convex-combined constraints, in general

Take $C_1 = \{x, y \ge 0,\ x \le 10,\ y \le 10,\ x + y \le 100\}$ and $C_2 = \{x, y \ge 0,\ x \le 20,\ y \le 20,\ x + y \le 20\}$ . Averaging the constraints gives $x, y \le 15$ , $x + y \le 60$ , which contains $(15,15)$ . But every point of $C_1 \cup C_2$ has $x + y \le 20$ , so $(15,15)$ is not in the convex hull. The trouble is that $x + y \le 100$ was never active.

LemmaFor multiple-access pentagons, the two operations agree

Write $I_1 = I(X_1;Y\mid X_2)$ , $I_2 = I(X_2;Y\mid X_1)$ , $I_3 = I(X_1,X_2;Y)$ and $C_{\mathbf I} = \{R \ge 0 : R_1 \le I_1,\ R_2 \le I_2,\ R_1 + R_2 \le I_3\}$ . Then for $\mathbf I_\lambda = \lambda\mathbf I^{(1)} + (1-\lambda)\mathbf I^{(2)}$ ,

$C_{\mathbf I_\lambda} = \lambda C_{\mathbf I^{(1)}} + (1-\lambda)C_{\mathbf I^{(2)}}$

ProofThe sum constraint is always active, so the corners mix

Key fact: $I_1 + I_2 \ge I_3$ . With independent inputs, $I_2 = H(X_2) - H(X_2\mid Y, X_1) = I(X_2; Y, X_1) = I(X_2;Y) + I(X_2;X_1\mid Y) \ge I(X_2;Y)$ , so $I_1 + I_2 \ge I_1 + I(X_2;Y) = I_3$ by the chain rule.

$\supseteq$ : a mixture of points satisfying each set of constraints satisfies the mixed constraints.

$\subseteq$ : because $I_1 + I_2 \ge I_3$ , every $C_{\mathbf I}$ is a genuine pentagon (or rectangle) with vertices $(0,0)$ , $(I_1, 0)$ , $(I_1, I_3 - I_1)$ , $(I_3 - I_2, I_2)$ , $(0, I_2)$ . Each vertex of $C_{\mathbf I_\lambda}$ is the $\lambda$ -mixture of the corresponding vertices of the two pentagons, so it lies in the mixture of the regions. Convexity covers the rest.

∎

TheoremCapacity region with a time-sharing variable

The capacity region is the closure of all $(R_1, R_2)$ with

$R_1 < I(X_1;Y\mid X_2,Q), \qquad R_2 < I(X_2;Y\mid X_1,Q), \qquad R_1 + R_2 < I(X_1,X_2;Y\mid Q)$

for some $p(q)p(x_1\mid q)p(x_2\mid q)p(y\mid x_1,x_2)$ with $|\mathcal Q| \le 4$ .

Intuition $Q$ is a shared calendar

$Q$ is a public clock telling both senders which input distribution to use right now. Conditioning on $Q$ averages the three mutual informations, so by the lemma this is the same as taking the convex hull.

TheoremCarathéodory

Any point in the convex hull of a compact set in $\mathbb R^d$ is a convex combination of at most $d + 1$ points of the set.

RemarkWhy $|\mathcal Q| \le 4$

The relevant vector $(I_1, I_2, I_3)$ lives in $\mathbb R^3$ , so 4 points suffice. Without such a bound the region would be uncomputable: we’d never know whether a larger $\mathcal Q$ helped. Points on the boundary need only $d$ points, since they lie on a supporting hyperplane.

Converse

ProofFano, data processing, memorylessness, then a time-sharing variable

Fix a code with $P_e^{(n)} \rightarrow 0$ . The joint distribution is

$p(w_1,w_2,x_1^n,x_2^n,y^n) = 2^{-nR_1}2^{-nR_2}\,p(x_1^n\mid w_1)\,p(x_2^n\mid w_2)\prod_i p(y_i\mid x_{1i},x_{2i})$

Fano: $H(W_1, W_2 \mid Y^n) \le n\epsilon_n$ with $\epsilon_n \rightarrow 0$ , hence also $H(W_1\mid Y^n), H(W_2\mid Y^n) \le n\epsilon_n$ .

Bound on $R_1$ :

$nR_1 = H(W_1) \overset{(a)}{\le} I(W_1;Y^n) + n\epsilon_n \overset{(b)}{\le} I(X_1^n;Y^n) + n\epsilon_n$ $\overset{(c)}{\le} H(X_1^n\mid X_2^n) - H(X_1^n\mid Y^n,X_2^n) + n\epsilon_n = I(X_1^n;Y^n\mid X_2^n) + n\epsilon_n$ $= H(Y^n\mid X_2^n) - \sum_i H(Y_i\mid Y^{i-1},X_1^n,X_2^n) + n\epsilon_n \overset{(e)}{=} H(Y^n\mid X_2^n) - \sum_iH(Y_i\mid X_{1i},X_{2i}) + n\epsilon_n$ $\overset{(f,g)}{\le} \sum_i H(Y_i\mid X_{2i}) - \sum_i H(Y_i\mid X_{1i},X_{2i}) + n\epsilon_n = \sum_i I(X_{1i};Y_i\mid X_{2i}) + n\epsilon_n$

(a) Fano;
(b) data processing;
(c) independent messages give independent codewords, so $H(X_1^n) = H(X_1^n\mid X_2^n)$ , and conditioning can only lower the subtracted term;
(e) the channel is memoryless;
(f, g) chain rule, then drop conditioning.

The same argument gives $R_2 \le \frac1n\sum_iI(X_{2i};Y_i\mid X_{1i}) + \epsilon_n$ , and, starting from $H(W_1,W_2)$ , $R_1 + R_2 \le \frac1n\sum_iI(X_{1i},X_{2i};Y_i) + \epsilon_n$ .

Time-sharing variable. Let $Q$ be uniform on $\{1,\ldots,n\}$ , and set $X_1 = X_{1Q}$ , $X_2 = X_{2Q}$ , $Y = Y_Q$ . Then $\frac1n\sum_iI(X_{1i};Y_i\mid X_{2i}) = I(X_1;Y\mid X_2,Q)$ , and so on. Given $Q = i$ , the inputs are independent (their messages are), so the distribution has the form $p(q)p(x_1\mid q)p(x_2\mid q)p(y\mid x_1,x_2)$ . Let $n \rightarrow \infty$ .

∎

$m$ users

Theorem $m$ -user multiple-access channel

With $R(S) = \sum_{i\in S}R_i$ and $X(S) = \{X_i : i \in S\}$ , the capacity region is the closure of the convex hull of rate vectors satisfying

$R(S) \le I\big(X(S); Y \mid X(S^c)\big) \quad \text{for all } S \subseteq \{1,\ldots,m\}$

for some product distribution $p_1(x_1)\cdots p_m(x_m)$ . There are $2^m - 1$ constraints, one per subset of users who might be decoded wrongly. The region is a “beveled box” (a polymatroid).

The Gaussian multiple-access channel in detail

$Y_i = X_{1i} + X_{2i} + Z_i$ , $Z_i \sim \mathcal N(0,N)$ , with power constraints $\frac1n\sum_ix_{ji}^2(w_j) \le P_j$ .

DerivationIndependent Gaussian inputs maximize every bound at once

$I(X_1;Y\mid X_2) = h(X_1 + X_2 + Z\mid X_2) - h(Z) = h(X_1 + Z \mid X_2) - h(Z) = h(X_1 + Z) - h(Z) \le \tfrac12\log 2\pi e(P_1+N) - \tfrac12\log2\pi eN$

using that $Z$ is independent of the inputs, the inputs are independent of each other, and a Gaussian maximizes entropy for a given second moment. The same inputs, $X_j \sim \mathcal N(0,P_j)$ independent, achieve equality in all three bounds simultaneously.

TheoremGaussian multiple-access capacity region

$R_1 \le \mathcal C\!\left(\frac{P_1}N\right), \qquad R_2 \le \mathcal C\!\left(\frac{P_2}N\right), \qquad R_1 + R_2 \le \mathcal C\!\left(\frac{P_1 + P_2}N\right)$

The corners are $\big(\mathcal C(\frac{P_1}{N}),\ \mathcal C(\frac{P_2}{P_1+N})\big)$ and $\big(\mathcal C(\frac{P_1}{P_2+N}),\ \mathcal C(\frac{P_2}N)\big)$ , reached by onion peeling.

ImportantThe sum rate equals one sender with the pooled power

$R_1 + R_2$ can reach $\mathcal C\big(\frac{P_1+P_2}N\big)$ , exactly what a single transmitter with power $P_1 + P_2$ would get. Splitting the power between two independent senders costs nothing in total throughput. “Gauss’s law” for information flow: for any set $S$ of senders, $\sum_{i\in S}R_i \le \mathcal C\big(\sum_{i\in S}P_i/N\big)$ .

RemarkCDMA versus FDMA and TDMA

Scheme	Rates	Optimal?
CDMA: separate codes, joint or successive decoding	The whole region	Yes. New users can join without recoding existing ones.
FDMA: bandwidths $W_1 + W_2 = W$	$R_j = W_j\log\big(1 + \frac{P_j}{NW_j}\big)$ , with $N$ the noise spectral density	Touches the boundary at one point only, where bandwidth is proportional to power.
Naive TDMA: alternate slots	$\frac12\mathcal C(P/N)$ each	No.
TDMA with power boost: double power in your own slots	$\frac12\mathcal C(2P/N)$ each; variable slots match FDMA	Same curve as FDMA.

FDMA and TDMA systems are simpler and are usually built for a fixed number of users, so slots may go empty or users may be turned away. In practice the capacity gain may not justify CDMA’s complexity.

Encoding of correlated sources (Slepian–Wolf)

The problem. Gotham and Metropolis each record their weather, and the two records are correlated. Each city compresses its own data without seeing the other’s, and headquarters wants both reconstructed. Encoding them together would cost $H(X,Y)$ bits per day; encoding them separately seems to cost $H(X) + H(Y)$ . Slepian and Wolf showed that separate encoders also need only $H(X,Y)$ in total.

flowchart LR
  X["X at location A"] --> E1["Encoder 1, rate R1"]
  Y["Y at location B"] --> E2["Encoder 2, rate R2"]
  E1 --> D["Joint decoder"]
  E2 --> D
  D --> O["Estimates of X and Y"]

DefinitionDistributed source code

For $(X_i, Y_i)$ i.i.d. $\sim p(x,y)$ , a $((2^{nR_1}, 2^{nR_2}), n)$ code is a pair of separate encoders $f_1 : \mathcal X^n \rightarrow \{1,\ldots,2^{nR_1}\}$ and $f_2 : \mathcal Y^n \rightarrow \{1,\ldots,2^{nR_2}\}$ and a joint decoder $g$ . Its error probability is $P_e^{(n)} = P\big(g(f_1(X^n), f_2(Y^n)) \ne (X^n, Y^n)\big)$ , and achievable rates and the rate region are defined as usual.

TheoremSlepian–Wolf

The achievable rate region is

$R_1 \ge H(X\mid Y), \qquad R_2 \ge H(Y\mid X), \qquad R_1 + R_2 \ge H(X,Y)$

ExampleGotham and Metropolis weather

Gotham is sunny with probability $\frac12$ , and Metropolis has the same weather as Gotham with probability $0.89$ :

	Metropolis rain	Metropolis shine
Gotham rain	0.445	0.055
Gotham shine	0.055	0.445

For 100 days: raw or separately compressed, $100 + 100 = 200$ bits. With Slepian–Wolf, $100H(\frac12) + 100H(0.89) \approx 100 + 50 = 150$ bits, although neither city sees the other’s data.

ExampleA three-point source

$(U,V)$ uniform on three of the four binary pairs, one pair impossible. The total rate needed is $H(U,V) = \log 3 \approx 1.58$ bits, rather than 2.

Random binning

IntuitionHash, don’t index

The AEP code indexed the typical set, so the encoder had to know which sequences were typical. Random binning throws every sequence into one of $2^{nR}$ bins at random, like a hash function, and sends only the bin number. The decoder looks for the unique typical sequence in that bin. The encoder needs no model; only the decoder needs to know the typical set. That asymmetry is what lets binning work when encoders are separated.

ProofBinning compresses a single source at any rate above

H(X)

Let $f(\mathbf x)$ be uniform on $\{1,\ldots,2^{nR}\}$ , independently for each $\mathbf x$ . Decode to the unique typical sequence in the bin. An error needs either an atypical source sequence, or another typical sequence in the same bin:

$P(\text{error}) \le \epsilon + \sum_{\mathbf x}p(\mathbf x)\sum_{\mathbf x' \in A_\epsilon^{(n)},\,\mathbf x'\ne\mathbf x}P\big(f(\mathbf x') = f(\mathbf x)\big) \le \epsilon + 2^{n(H(X)+\epsilon)}2^{-nR} \le 2\epsilon$

if $R > H(X) + \epsilon$ and $n$ is large.

∎

Achievability

ProofProduct bins isolate jointly typical pairs

Code. Bin every $\mathbf x$ uniformly into $2^{nR_1}$ bins ( $f_1$ ), and every $\mathbf y$ into $2^{nR_2}$ bins ( $f_2$ ), independently. Each encoder sends its own bin index. Given $(i_0, j_0)$ , the decoder outputs the unique jointly typical $(\mathbf x, \mathbf y)$ with $f_1(\mathbf x) = i_0$ and $f_2(\mathbf y) = j_0$ .

Error events.

$E_0$ : $(\mathbf X, \mathbf Y)$ not jointly typical.
$E_1$ : some $\mathbf x' \ne \mathbf X$ in $\mathbf X$ ‘s bin with $(\mathbf x', \mathbf Y)$ typical.
$E_2$ : likewise for $\mathbf y'$ .
$E_{12}$ : some $(\mathbf x', \mathbf y')$ , both different, in both bins and jointly typical.

Bounds. $P(E_0) \rightarrow 0$ by the AEP. Using the conditional typical set size,

$P(E_1) \le \sum_{(\mathbf x,\mathbf y)}p(\mathbf x,\mathbf y)\,2^{-nR_1}\big|A_\epsilon(X\mid\mathbf y)\big| \le 2^{-nR_1}2^{n(H(X\mid Y)+2\epsilon)}$

which vanishes if $R_1 > H(X\mid Y)$ . Similarly $P(E_2) \rightarrow 0$ if $R_2 > H(Y\mid X)$ , and $P(E_{12}) \le 2^{-n(R_1+R_2)}2^{n(H(X,Y)+\epsilon)} \rightarrow 0$ if $R_1 + R_2 > H(X,Y)$ . The average over bin assignments is small, so a good assignment exists.

∎

Converse

ProofFano on the pair of indices

Let $I_0 = f_1(X^n)$ and $J_0 = f_2(Y^n)$ . By Fano, $H(X^n,Y^n\mid I_0,J_0) \le n\epsilon_n$ .

Sum rate. $n(R_1 + R_2) \ge H(I_0,J_0) = I(X^n,Y^n;I_0,J_0) = H(X^n,Y^n) - H(X^n,Y^n\mid I_0,J_0) \ge nH(X,Y) - n\epsilon_n$ . The middle equality holds because the indices are functions of the sources.

$R_1$ . $nR_1 \ge H(I_0) \ge H(I_0\mid Y^n) = I(X^n;I_0\mid Y^n) = H(X^n\mid Y^n) - H(X^n\mid I_0,J_0,Y^n) \ge nH(X\mid Y) - n\epsilon_n$ . Here $J_0$ is a function of $Y^n$ , so conditioning on it adds nothing. $R_2$ is symmetric.

∎

flowchart LR
  A["R1 at least H of X given Y"] --- R["Slepian-Wolf region: an unbounded region with corners at H of X given Y, H of Y and at H of X, H of Y given X"]
  B["R2 at least H of Y given X"] --- R
  S["R1 plus R2 at least H of X and Y"] --- R

TheoremMany sources

For $(X_{1i},\ldots,X_{mi})$ i.i.d., separate encoders and a common decoder can achieve exactly the rates with

$R(S) > H\big(X(S)\mid X(S^c)\big) \quad \text{for all } S \subseteq \{1,\ldots,m\}$

The result extends to any jointly ergodic source, with entropy rates in place of entropies.

Interpretation: colouring the fans

IntuitionGraph colouring at the corner point

At the corner $R_1 = H(X)$ , $R_2 = H(Y\mid X)$ , the decoder learns $X^n$ exactly. Around each typical $\mathbf x$ there is a fan of about $2^{nH(Y\mid X)}$ sequences $\mathbf y$ that are jointly typical with it. If the $Y$ encoder knew $\mathbf x$ , it could send the index of $\mathbf y$ within that fan. It doesn’t, so it colours every $\mathbf y$ randomly with one of $2^{nR_2}$ colours. If $R_2 > H(Y\mid X)$ , there are exponentially more colours than members of any fan, so with high probability all colours within a fan are distinct, and the colour plus the decoder’s knowledge of the fan pins down $\mathbf y$ .

Duality between Slepian–Wolf coding and the multiple-access channel

	Multiple-access channel	Slepian–Wolf
Problem	Independent messages through a noisy shared channel	Correlated sources through noiseless separate links
Random map	messages → codewords	sequences → bin indices
Error event	a wrong codeword is jointly typical with what was received	a wrong typical pair shares the bins
Error bound	$\epsilon + \sum_{2^{nR_1}}2^{-nI_1} + \sum_{2^{nR_2}}2^{-nI_2} + \sum_{2^{n(R_1+R_2)}}2^{-nI_3}$	$\epsilon + \sum_{2^{nH_1}}2^{-nR_1} + \sum_{2^{nH_2}}2^{-nR_2} + \sum_{2^{nH_3}}2^{-n(R_1+R_2)}$
Constraints	$R \le I$	$R \ge H$

IntuitionRates and informations swap places

In the channel, the number of candidates is set by the rate and the chance each fools the decoder by a mutual information. In source coding, the number of candidates is set by an entropy and the chance each shares a bin by the rate. One might have expected the broadcast channel to be the dual of the multiple-access channel. It isn’t; Slepian–Wolf is.

The broadcast channel

One sender, several receivers: a TV station, a lecturer, a market-report telegram to many subscribers.

flowchart LR
  W["Messages W1 and W2"] --> E["Encoder: X"]
  E --> C["Channel p of y1 and y2 given x"]
  C --> Y1["Y1"] --> D1["Decoder 1: estimate of W1"]
  C --> Y2["Y2"] --> D2["Decoder 2: estimate of W2"]

ExampleMotivating broadcasts

TV station, same content to all: the rate is at most $\max_{p(x)}\min_iI(X;Y_i)$ , which can be below the worst receiver’s own capacity. Better: give everyone a basic signal, and give the good receivers extra detail (high-definition layers).
A lecturer: a poorly prepared lecture runs at the pace of the weakest student. Ideally strong students get more and weak students still get the essentials.
Orthogonal channels: two independent links give the rectangle $R_1 < C_1$ , $R_2 < C_2$ .
A single user with an unknown channel: get the basic information through when the channel is bad and extra information when it is good, which is the same superposition idea.

ExampleA Spanish and Dutch speaker

The speaker knows $2^{20}$ words in each language and says one word per second. One listener understands only Spanish, the other only Dutch. Talking only to one listener gives 20 bits/s; time-sharing gives $R_1 + R_2 = 20$ .

But each listener can tell which language is being spoken, even without understanding it. Speaking half the time in each language, the pattern of languages over 100 words is one of about $\binom{100}{50} \approx 2^{100}$ orderings, which is about 1 bit/s of information that both listeners receive. Total: 10 + 10 + 1 = 21 bits/s, beating time-sharing. This is superposition.

DefinitionBroadcast channel and its codes

An input alphabet $\mathcal X$ , outputs $\mathcal Y_1, \mathcal Y_2$ , and a transition function $p(y_1,y_2\mid x)$ , memoryless if it factors over time. A $((2^{nR_1}, 2^{nR_2}), n)$ code with independent messages has an encoder $X : \{1..2^{nR_1}\}\times\{1..2^{nR_2}\} \rightarrow \mathcal X^n$ and decoders $g_j : \mathcal Y_j^n \rightarrow \{1..2^{nR_j}\}$ . Its error probability is $P_e^{(n)} = P\big(g_1(Y_1^n)\ne W_1 \text{ or } g_2(Y_2^n)\ne W_2\big)$ with uniform messages. With a common message of rate $R_0$ , each decoder must recover $(W_0, W_j)$ .

TheoremOnly the marginals matter

The capacity region depends only on $p(y_1\mid x)$ and $p(y_2\mid x)$ , not on how the two outputs are correlated. Receiver $j$ ‘s error depends only on $(X^n, Y_j^n)$ . (Proof left to the book’s problems.)

Degraded broadcast channels

DefinitionDegradedness

Physically degraded: $p(y_1,y_2\mid x) = p(y_1\mid x)\,p(y_2\mid y_1)$ , i.e. $X \rightarrow Y_1 \rightarrow Y_2$ . The bad receiver hears a noisy copy of what the good receiver hears.
Stochastically degraded: same marginals as some physically degraded channel, i.e. $p(y_2\mid x) = \sum_{y_1}p(y_1\mid x)p'(y_2\mid y_1)$ for some $p'$ .

Only marginals matter, so the two have the same capacity region, and we may assume physical degradedness.

TheoremCapacity of the degraded broadcast channel

For $X \rightarrow Y_1 \rightarrow Y_2$ , the capacity region is the closure of the convex hull of all $(R_1, R_2)$ with

$R_2 \le I(U;Y_2), \qquad R_1 \le I(X;Y_1\mid U)$

for some $p(u)p(x\mid u)p(y_1,y_2\mid x)$ , with $|\mathcal U| \le \min\{|\mathcal X|, |\mathcal Y_1|, |\mathcal Y_2|\}$ .

IntuitionClouds and satellites

The auxiliary $U$ is a cloud centre. Each of the $2^{nR_2}$ clouds (message $W_2$ ) is surrounded by $2^{nR_1}$ satellite codewords (message $W_1$ ). The bad receiver can only make out which cloud; the good receiver resolves the cloud and the satellite within it.

ProofSuperposition coding and its error analysis

Fix $p(u)p(x\mid u)$ .

Codebook. Draw $2^{nR_2}$ cloud centres $\mathbf U(w_2)$ i.i.d. $\sim\prod p(u_i)$ . For each, draw $2^{nR_1}$ satellites $\mathbf X(w_1,w_2) \sim \prod p(x_i\mid u_i(w_2))$ . Send $\mathbf X(W_1, W_2)$ .

Receiver 2 decodes the unique $\hat w_2$ with $(\mathbf U(\hat w_2), \mathbf Y_2)$ jointly typical. Assume $(1,1)$ was sent. A wrong cloud centre is independent of $\mathbf Y_2$ , so

$P_e^{(n)}(2) \le \epsilon + 2^{nR_2}2^{-n(I(U;Y_2)-2\epsilon)}$

which vanishes if $R_2 < I(U;Y_2)$ .

Receiver 1 decodes the unique $(\hat w_1, \hat w_2)$ with $(\mathbf U(\hat w_2), \mathbf X(\hat w_1,\hat w_2), \mathbf Y_1)$ jointly typical. Errors:

Wrong cloud: probability $\le 2^{nR_2}2^{-n(I(U;Y_1)-3\epsilon)}$ . By data processing along $U \rightarrow Y_1 \rightarrow Y_2$ , $I(U;Y_1) \ge I(U;Y_2) > R_2$ , so this vanishes automatically.
Right cloud, wrong satellite: a wrong satellite shares the true $\mathbf U(1)$ but is otherwise conditionally independent of $\mathbf Y_1$ , so by the conditional-independence typicality theorem $P \le 2^{-n(I(X;Y_1\mid U)-4\epsilon)}$ . With $2^{nR_1}$ of them, this vanishes if $R_1 < I(X;Y_1\mid U)$ .

The converse (Gallager) is outlined in the book’s Problem 15.11.

∎

TheoremAdding a common message

Any broadcast channel: if $(R_1, R_2)$ is achievable, then so is $(R_0, R_1 - R_0, R_2 - R_0)$ for $R_0 \le \min(R_1,R_2)$ . Carve the common message out of both private ones.
Degraded: $(R_0, R_1, R_2 - R_0)$ is achievable for $R_0 < R_2$ . The good receiver decodes the bad receiver’s message anyway, so the common message rides on $W_2$ for free.

ExampleBinary symmetric broadcast channel

Two BSCs with crossover probabilities $p_1 < p_2 < \frac12$ .

Make it degraded. A BSC( $p_2$ ) is a BSC( $p_1$ ) followed by a BSC( $\alpha$ ) with $p_1(1-\alpha) + (1-p_1)\alpha = p_2$ , i.e. $\alpha = \frac{p_2 - p_1}{1 - 2p_1}$ .

Auxiliary. By symmetry, take $U$ uniform on $\{0,1\}$ , connected to $X$ by a BSC( $\beta$ ). With the binary convolution $a * b = a(1-b) + (1-a)b$ ,

$R_2 = I(U;Y_2) = 1 - H(\beta * p_2), \qquad R_1 = I(X;Y_1\mid U) = H(\beta * p_1) - H(p_1)$

Sweep $\beta$ .

$\beta = 0$ : $U = X$ and everything is cloud: $(R_1,R_2) = (0,\ 1 - H(p_2))$ .
$\beta = \frac12$ : the cloud carries nothing: $(1 - H(p_1),\ 0)$ .

In between, the boundary curve lies strictly above the time-sharing line.

ExampleGaussian broadcast channel, degraded form

$Y_1 = X + Z_1$ , $Y_2 = Y_1 + Z_2'$ , with $Z_1 \sim \mathcal N(0,N_1)$ and $Z_2' \sim \mathcal N(0,N_2 - N_1)$ . Every scalar Gaussian broadcast channel is equivalent to this degraded form. Its region is the one given in the preview: $R_1 < \mathcal C(\alpha P/N_1)$ , $R_2 < \mathcal C\big((1-\alpha)P/(\alpha P + N_2)\big)$ .

The relay channel

flowchart LR
  X["Sender X"] --> C["Channel p of y and y1 given x and x1"]
  C --> Y1["Relay hears Y1"]
  Y1 --> R["Relay sends X1, using only past Y1"]
  R --> C
  C --> Y["Receiver Y"]

DefinitionRelay channel and its codes

Alphabets $\mathcal X, \mathcal X_1, \mathcal Y, \mathcal Y_1$ and $p(y, y_1\mid x, x_1)$ : $x$ is the sender’s input, $x_1$ the relay’s, $y_1$ what the relay hears, and $y$ what the destination hears. A $(2^{nR}, n)$ code has an encoder $X : \{1..2^{nR}\}\rightarrow\mathcal X^n$ , causal relay functions $x_{1i} = f_i(y_{11},\ldots,y_{1,i-1})$ , and a decoder $g : \mathcal Y^n \rightarrow \{1..2^{nR}\}$ . The capacity is the supremum of achievable rates.

IntuitionTwo cuts

The relay channel is a broadcast channel (from $X$ to $Y$ and $Y_1$ ) glued to a multiple-access channel (from $X$ and $X_1$ to $Y$ ). Information must cross two cuts:

Cut	Separates	Bound
Around the destination	$\{X, X_1\}$ from $Y$	$I(X, X_1; Y)$
Around the sender	$X$ from $\{Y, Y_1\}$ , given the relay’s input	$I(X; Y, Y_1\mid X_1)$

TheoremCut-set upper bound for the relay channel

$C \le \sup_{p(x,x_1)}\min\big\{I(X,X_1;Y),\ I(X;Y,Y_1\mid X_1)\big\}$

This is a special case of the general cut-set theorem (General multiterminal networks).

DefinitionPhysically degraded relay channel

$p(y,y_1\mid x,x_1) = p(y_1\mid x,x_1)\,p(y\mid y_1,x_1)$ : the destination hears a degraded version of what the relay hears.

TheoremCapacity of the degraded relay channel

$C = \sup_{p(x,x_1)}\min\big\{I(X,X_1;Y),\ I(X;Y_1\mid X_1)\big\}$

The max-flow min-cut bound is achieved.

ProofConverse, and an outline of block-Markov achievability

Converse. The cut-set bound, plus degradedness: $I(X;Y,Y_1\mid X_1) = I(X;Y_1\mid X_1)$ , since $Y$ adds nothing once $Y_1$ is known.

Achievability ingredients: random coding, list codes, Slepian–Wolf partitioning, cooperative multiple-access coding, superposition, and block-Markov encoding.

Codebook. Fix $p(x_1)p(x\mid x_1)$ . Draw $2^{nR_0}$ relay codewords $\mathbf x_1(s)$ . For each $s$ , draw $2^{nR}$ sender codewords $\mathbf x(w\mid s)$ . Randomly partition the messages $\{1..2^{nR}\}$ into $2^{nR_0}$ cells $S_s$ .

Blocks. Send $B - 1$ messages over $B$ blocks; the rate is $R\frac{B-1}B \rightarrow R$ . In block $i$ the sender sends $\mathbf x(w_i\mid s_i)$ , where $s_i$ is the cell of the previous message $w_{i-1}$ . The relay, which decoded $w_{i-1}$ , sends $\mathbf x_1(s_i)$ , the same cell index. So sender and relay cooperate on $s_i$ .

Decoding at the end of block $i$ :

The relay decodes $w_i$ from $\mathbf y_1(i)$ , knowing $s_i$ . This works if $R < I(X;Y_1\mid X_1)$ .
The destination decodes the cell $s_i$ from $\mathbf y(i)$ . This works if $R_0 < I(X_1;Y)$ .
The destination intersects cell $S_{s_i}$ with its list of messages consistent with $\mathbf y(i-1)$ , and recovers $w_{i-1}$ if $R < I(X;Y\mid X_1) + R_0$ .

Eliminating $R_0$ from steps 2 and 3: $R < I(X;Y\mid X_1) + I(X_1;Y) = I(X,X_1;Y)$ . Together with step 1, that is the theorem. (Full error analysis: Cover and El Gamal.)

∎

RemarkOther solved relay channels

The same formula is also the capacity of:

reversely degraded relay channels, $p(y,y_1\mid x,x_1) = p(y\mid x,x_1)p(y_1\mid y,x_1)$ ;
relay channels with feedback;
deterministic relay channels, $y_1 = f(x,x_1)$ , $y = g(x,x_1)$ .

Source coding with side information

The problem. $X$ and $Y$ are encoded separately, but only $X$ must be recovered. $Y$ is a helper. If the helper may send $R_2$ bits about $Y$ , how many bits $R_1$ does $X$ need?

flowchart LR
  X["X"] --> E1["Encoder, rate R1"]
  Y["Y, the helper"] --> E2["Encoder, rate R2"]
  E1 --> D["Decoder"]
  E2 --> D
  D --> O["Estimate of X only"]

IntuitionThe two extremes and everything between

$R_2 \ge H(Y)$ : $Y$ arrives perfectly, so by Slepian–Wolf $R_1 = H(X\mid Y)$ .
$R_2 = 0$ : no help, so $R_1 = H(X)$ .
In between, the helper describes a coarse version $U$ of $Y$ with $I(Y;U)$ bits, and $X$ is then described with $H(X\mid U)$ bits.

TheoremSource coding with coded side information

$X$ can be recovered with vanishing error probability iff

$R_1 \ge H(X\mid U), \qquad R_2 \ge I(Y;U)$

for some $p(x,y)p(u\mid y)$ with $|\mathcal U| \le |\mathcal Y| + 2$ . The factorization makes $X \rightarrow Y \rightarrow U$ a Markov chain: the helper’s message depends on $X$ only through $Y$ .

ProofConverse: build

U

from the helper’s message and the past

Let $S = f_n(X^n)$ , $T = g_n(Y^n)$ . By Fano, $H(X^n\mid S,T) \le n\epsilon_n$ .

$R_2$ . $nR_2 \ge H(T) \ge I(Y^n;T) = \sum_iI(Y_i;T\mid Y^{i-1}) = \sum_iI(Y_i;T,Y^{i-1}) = \sum_iI(Y_i;U_i)$ , with $U_i = (T, Y^{i-1})$ . The middle step uses that $Y_i$ is independent of $Y^{i-1}$ .

$R_1$ .

$nR_1 \ge H(S) \ge H(S\mid T) \ge H(X^n,S\mid T) - n\epsilon_n = H(X^n\mid T) - n\epsilon_n = \sum_iH(X_i\mid T,X^{i-1}) - n\epsilon_n$ $\ge \sum_iH(X_i\mid T,X^{i-1},Y^{i-1}) - n\epsilon_n = \sum_iH(X_i\mid T,Y^{i-1}) - n\epsilon_n = \sum_iH(X_i\mid U_i) - n\epsilon_n$

The second-to-last equality is the subtle step: $X_i \rightarrow (T, Y^{i-1}) \rightarrow X^{i-1}$ , because once the past $Y$ ‘s and the helper’s message are known, the past $X$ ‘s say nothing more about $X_i$ .

Markov structure. $X_i \rightarrow Y_i \rightarrow U_i$ , since $X_i$ knows nothing about $U_i$ that isn’t already in $Y_i$ .

Time-sharing. With $Q$ uniform on $\{1..n\}$ and independent of the source, $I(Y_Q;U_Q\mid Q) = I(Y_Q;U_Q,Q)$ , so $U = (U_Q, Q)$ satisfies the theorem.

∎

DefinitionStrong typicality

$(\mathbf x, \mathbf y, \mathbf z)$ is $\epsilon$ -strongly typical if every symbol triple’s empirical frequency is within $\frac{\epsilon}{|\mathcal X||\mathcal Y||\mathcal Z|}$ of its probability:

$\left|\frac1nN(a,b,c\mid\mathbf x,\mathbf y,\mathbf z) - p(a,b,c)\right| < \frac{\epsilon}{|\mathcal X||\mathcal Y||\mathcal Z|}$

Joint strong typicality of the triple implies typicality of each pair, but pairwise typicality does not imply typicality of the triple in general.

LemmaMarkov lemma

If $X \rightarrow Y \rightarrow Z$ , $(\mathbf y, \mathbf z)$ is strongly typical, and $\mathbf X \sim \prod_ip(x_i\mid y_i)$ , then $(\mathbf X, \mathbf y, \mathbf z)$ is strongly typical with probability $> 1 - \epsilon$ for large $n$ . Markovity is what lets $\mathbf X$ be drawn given $\mathbf y$ alone.

ProofAchievability: a quantizing helper plus a binned source

Fix $p(u\mid y)$ and compute $p(u)$ .

Codebooks. The helper has $2^{nR_2}$ codewords $\mathbf U(s)$ drawn i.i.d. $\sim\prod p(u_i)$ . All $X$ sequences are randomly binned into $2^{nR_1}$ bins.

Encoding. $X$ sends its bin index. The helper sends an $s$ with $(\mathbf Y, \mathbf U(s))$ strongly typical.

Decoding. Output the unique $\mathbf x$ in the bin with $(\mathbf x, \mathbf U(s))$ strongly typical.

Errors:

The source pair is atypical: small.
No helper codeword matches $\mathbf Y$ : small if $R_2 > I(Y;U)$ , by the covering argument from rate distortion.
$\mathbf U(s)$ matches $\mathbf Y$ but not $\mathbf X$ : small, by the Markov lemma.
Another typical $\mathbf x'$ in the same bin matches $\mathbf U(s)$ : probability $\le 2^{n(H(X)+\epsilon)}2^{-nR_1}2^{-n(I(X;U)-3\epsilon)}$ , which vanishes if $R_1 > H(X\mid U)$ .

∎

Rate distortion with side information (Wyner–Ziv)

The problem. Describe $X$ to within distortion $D$ , when the decoder (but not the encoder) has correlated side information $Y$ .

flowchart LR
  X["X"] --> E["Encoder, rate R"]
  E --> D["Decoder"]
  Y["Y, at the decoder only"] --> D
  D --> O["Reconstruction with expected distortion at most D"]

DefinitionRate distortion function with side information

$R_Y(D)$ is the infimum of rates $R$ for which there are maps $i_n : \mathcal X^n \rightarrow \{1..2^{nR}\}$ and $g_n : \mathcal Y^n\times\{1..2^{nR}\} \rightarrow \hat{\mathcal X}^n$ with

$\limsup_{n\rightarrow\infty}\mathbb Ed\big(X^n, g_n(Y^n, i_n(X^n))\big) \le D$

Since side information can only help, $R_Y(D) \le R(D)$ . At zero distortion this is Slepian–Wolf, so $R_Y(0) = H(X\mid Y)$ .

TheoremWyner–Ziv

$R_Y(D) = \min_{p(w\mid x)}\ \min_f\ \big(I(X;W) - I(Y;W)\big)$

over conditional distributions $p(w\mid x)$ with $|\mathcal W| \le |\mathcal X| + 1$ and decoding functions $f : \mathcal Y \times \mathcal W \rightarrow \hat{\mathcal X}$ satisfying

$\sum_{x,w,y}p(x,y)\,p(w\mid x)\,d\big(x, f(y,w)\big) \le D$

IntuitionPay for $W$ , get a discount for what $Y$ already knows

The encoder would like to send a description $W$ of $X$ , which costs $I(X;W)$ . But the decoder already holds $Y$ , which knows $I(Y;W)$ bits about $W$ . Binning lets the encoder skip those bits. Since $W \rightarrow X \rightarrow Y$ , the difference equals $I(X;W\mid Y)$ . That identity follows from the Markov chain; the book doesn’t state it.

Lemma $R_Y(D)$ is nonincreasing and convex

Monotone: a larger $D$ enlarges the feasible set. Convex: time-share. Let $Q$ be 1 with probability $\lambda$ , else 2, independent of everything. Set $W = (Q, W_Q)$ and $f(W,Y) = f_Q(W_Q, Y)$ . The distortion is $\lambda D_1 + (1-\lambda)D_2$ , and $I(X;W) - I(Y;W) = \lambda[I(X;W_1) - I(Y;W_1)] + (1-\lambda)[I(X;W_2) - I(Y;W_2)]$ , because $H(X\mid W) = \lambda H(X\mid W_1) + (1-\lambda)H(X\mid W_2)$ and the same for $Y$ .

ProofConverse: an auxiliary

W_i

from the index and the other

Y

‘s

Let $T = f_n(X^n)$ and $W_i = (T, Y^{i-1}, Y_{i+1}^n)$ .

$nR \ge H(T) \ge H(T\mid Y^n) \ge I(X^n;T\mid Y^n) = \sum_i\big[H(X_i\mid Y^n,X^{i-1}) - H(X_i\mid T,Y^n,X^{i-1})\big]$ $\ge \sum_i\big[H(X_i\mid Y_i) - H(X_i\mid W_i, Y_i)\big] = \sum_iI(X_i;W_i\mid Y_i) = \sum_i\big[I(W_i;X_i) - I(W_i;Y_i)\big]$

$H(X_i\mid Y^n, X^{i-1}) = H(X_i\mid Y_i)$ , since the source is i.i.d.;
dropping $X^{i-1}$ from the subtracted term can only increase it;
the last equality uses $W_i \rightarrow X_i \rightarrow Y_i$ , so $H(W_i\mid X_i, Y_i) = H(W_i\mid X_i)$ .

The decoder’s $i$ -th output is $g_{ni}(T, Y^n) = g_{ni}(W_i, Y_i)$ , so each term is at least $R_Y(D_i)$ with $D_i = \mathbb Ed(X_i,\hat X_i)$ . By Jensen and convexity,

$nR \ge \sum_iR_Y(D_i) \ge nR_Y\Big(\frac1n\sum_iD_i\Big) \ge nR_Y(D)$

∎

ProofAchievability: rate distortion codebook, then bin it

Fix $p(w\mid x)$ and $f$ .

Codebook. $2^{nR_1}$ codewords $\mathbf W(s) \sim\prod p(w_i)$ , with $R_1 = I(X;W) + \epsilon$ , randomly assigned to $2^{nR_2}$ bins with $R_2 = I(X;W) - I(Y;W) + 5\epsilon$ . Each bin holds about $2^{n(R_1-R_2)}$ codewords.

Encoding. Find $s$ with $(\mathbf X, \mathbf W(s))$ strongly typical (choosing the lowest such $s$ , or $s = 1$ if none). Send its bin.

Decoding. Find the unique $s$ in the bin with $(\mathbf W(s), \mathbf Y)$ strongly typical, and output $\hat X_i = f(W_i, Y_i)$ .

Errors:

The source pair is atypical: small.
No covering codeword exists: small, since $R_1 > I(W;X)$ .
The codeword matches $\mathbf X$ but not $\mathbf Y$ : small, by the Markov lemma.
A wrong codeword in the bin matches $\mathbf Y$ : probability $\le 2^{n(R_1-R_2)}2^{-n(I(W;Y)-3\epsilon)} \rightarrow 0$ .
If $s$ is correct, $(\mathbf X, \mathbf Y, \mathbf W)$ is jointly typical, so the empirical distortion is close to $D$ .

∎

WarningStill open: rate distortion for correlated sources

Encode $X$ and $Y$ separately, and reconstruct both within distortions. Slepian–Wolf, coded side information and Wyner–Ziv are all special cases of this problem, but its general rate distortion region is unknown.

General multiterminal networks

Setup. $m$ nodes. Node $i$ transmits $X^{(i)}$ and receives $Y^{(i)}$ (here superscripts index nodes and subscripts index time). Node $i$ sends an independent uniform message $W^{(ij)}$ at rate $R^{(ij)}$ to node $j$ . The channel $p(y^{(1)},\ldots,y^{(m)}\mid x^{(1)},\ldots,x^{(m)})$ is memoryless.

DefinitionNetwork codes

Encoders: $X_k^{(i)}$ depends on node $i$ ‘s messages $W^{(i1)},\ldots,W^{(im)}$ and on its past received symbols $Y_1^{(i)},\ldots,Y_{k-1}^{(i)}$ , so feedback and relaying are allowed.
Decoders: node $j$ estimates $W^{(ij)}$ from its whole received block and its own messages.

Rates are achievable if every $P_e^{(n)(ij)} \rightarrow 0$ .

flowchart LR
  subgraph S["Nodes in S"]
    A["X and Y at node 1"]
    B["X and Y at node 2"]
  end
  subgraph Sc["Nodes in the complement of S"]
    C["X and Y at node m"]
  end
  S -->|"rate across the cut"| Sc

TheoremCut-set bound

If the rates $\{R^{(ij)}\}$ are achievable, there is a joint distribution $p(x^{(1)},\ldots,x^{(m)})$ such that, for every cut $S$ ,

$\sum_{i\in S,\,j\in S^c}R^{(ij)} \le I\big(X^{(S)}; Y^{(S^c)} \,\big|\, X^{(S^c)}\big)$

IntuitionMax-flow min-cut for information

The information flowing across any boundary is at most the mutual information between the inputs on one side and the outputs on the other, given the inputs on the far side. Those inputs are known to the far side and can be subtracted out.

ProofFano across the cut, then a time-sharing variable

Let $T$ be the set of links crossing from $S$ to $S^c$ and $T^c$ the rest.

$n\sum_{i\in S, j\in S^c}R^{(ij)} \overset{(a,b)}{=} H(W^{(T)}) \overset{(c)}{=} H(W^{(T)}\mid W^{(T^c)}) = I\big(W^{(T)};Y_1^{(S^c)},\ldots,Y_n^{(S^c)}\mid W^{(T^c)}\big) + H\big(W^{(T)}\mid Y^{(S^c)}, W^{(T^c)}\big)$ $\overset{(d)}{\le} \sum_{k=1}^nI\big(W^{(T)};Y_k^{(S^c)}\mid Y_1^{(S^c)},\ldots,Y_{k-1}^{(S^c)},W^{(T^c)}\big) + n\epsilon_n$ $\overset{(g)}{\le} \sum_k\Big[H\big(Y_k^{(S^c)}\mid \text{past}^{(S^c)},W^{(T^c)},X_k^{(S^c)}\big) - H\big(Y_k^{(S^c)}\mid\text{past}^{(S^c)},W^{(T)},W^{(T^c)},X_k^{(S)},X_k^{(S^c)}\big)\Big] + n\epsilon_n$ $\overset{(h)}{\le} \sum_k\Big[H\big(Y_k^{(S^c)}\mid X_k^{(S^c)}\big) - H\big(Y_k^{(S^c)}\mid X_k^{(S)},X_k^{(S^c)}\big)\Big] + n\epsilon_n = \sum_kI\big(X_k^{(S)};Y_k^{(S^c)}\mid X_k^{(S^c)}\big) + n\epsilon_n$

(a, b, c) Messages are uniform and independent.
(d) Fano: the $S^c$ nodes decode $W^{(T)}$ from what they receive and their own messages. Then the chain rule.
(g) $X_k^{(S^c)}$ is a function of the $S^c$ nodes’ past receptions and messages, so adding it to the first term changes nothing. Adding $W^{(T)}, X_k^{(S)}$ to the second term can only lower it.
(h) In the first term, drop conditioning (which can only raise it). In the second, memorylessness: $Y_k$ depends only on the current inputs.

Time-sharing. Let $Q$ be uniform on $\{1..n\}$ . The sum becomes $nI(X_Q^{(S)};Y_Q^{(S^c)}\mid X_Q^{(S^c)},Q)$ . Removing $Q$ from the first entropy can only raise it, and $Y_Q$ depends on $Q$ only through the inputs, so the bound is at most $nI(X^{(S)};Y^{(S^c)}\mid X^{(S^c)})$ .

∎

ExampleThe bound applied

Multiple-access channel: the cuts give $R_1 \le I(X_1;Y\mid X_2)$ , $R_2 \le I(X_2;Y\mid X_1)$ , $R_1 + R_2 \le I(X_1,X_2;Y)$ , but for an arbitrary $p(x_1,x_2)$ . Capacity needs a product distribution (the senders can’t coordinate), so the bound is loose there.
Relay channel: the two cuts give $C \le \sup\min\{I(X,X_1;Y),\ I(X;Y,Y_1\mid X_1)\}$ , which is tight for degraded relay channels and relay channels with feedback.

WarningThe bound is not achievable in general

If the cut-set bounds were always achievable, network information flow would be solved, just as Ford–Fulkerson solves water flow. They are not achievable even for some simple channels.

Two single-user facts that fail in networks

WarningSource–channel separation fails

For one user, a source is transmissible iff its entropy rate is below capacity, so compression and channel coding can be designed separately. For networks one would expect: “transmissible iff the Slepian–Wolf region meets the multiple-access capacity region”, i.e.

$H(U\mid V) \le I(X_1;Y\mid X_2,Q), \quad H(V\mid U) \le I(X_2;Y\mid X_1,Q), \quad H(U,V) \le I(X_1,X_2;Y\mid Q)$

This is sufficient but not necessary. Counterexample: the three-point source (with the impossible pair being $(U,V) = (1,0)$ ) over the binary erasure multiple-access channel. $H(U,V) = \log 3 \approx 1.58 > \frac32$ , the channel’s maximum sum rate, so the regions don’t meet. Yet sending uncoded, $X_1 = U$ and $X_2 = V$ , works perfectly: $Y = U + V$ takes values 0, 1, 2 for the three possible pairs $(0,0), (0,1), (1,1)$ .

Why: the multiple-access channel’s capacity grows with correlated inputs, while Slepian–Wolf coding removes the correlation. Good network codes should preserve useful correlation (Cover–El Gamal–Salehi for multiple-access channels, Han–Costa for broadcast channels).

WarningFeedback can enlarge capacity regions

Feedback doesn’t increase the capacity of a single-user discrete memoryless channel. It does enlarge multiuser capacity regions, even for memoryless channels. Gaarder and Wolf showed this for the binary erasure multiple-access channel. The feedback acts as a side channel between the senders: they decode each other first, then cooperate to resolve the receiver’s remaining uncertainty at the higher cooperative rate. Cover–Leung gave an achievable region, Willems proved it is the capacity for a class including the binary erasure multiple-access channel, and Ozarow solved the two-user Gaussian case.

ImportantNo unified theory yet

There is still no general theory of network information flow. Even if one is found, it may be too complex to implement, but it would tell designers how far they are from optimal.

Quick reference

Object	Statement	Reads as
Gaussian capacity	$\mathcal C(x) = \frac12\log(1+x)$	Bits per use at SNR $x$ .
Gaussian multiple access	$\sum_SR_i < \mathcal C\big(\sum_SP_i/N\big)$	Pooled power, unbounded total rate.
Gaussian broadcast	$\mathcal C(\frac{\alpha P}{N_1})$ , $\mathcal C\big(\frac{(1-\alpha)P}{\alpha P+N_2}\big)$	Superposition and successive cancellation.
Gaussian relay	$\max_\alpha\min\big\{\mathcal C\big(\frac{P+P_1+2\sqrt{\bar\alpha PP_1}}{N_1+N_2}\big),\ \mathcal C(\frac{\alpha P}{N_1})\big\}$	Coherent cooperation.
Strong interference	$a^2 > 1 + P/N$ gives no rate loss	Decode the interference, then subtract it.
Conditional-independence typicality	$\doteq 2^{-nI(S_1;S_2\mid S_3)}$	Each wrong candidate’s chance.
Multiple-access channel	$R_1 < I(X_1;Y\mid X_2)$ , $R_2 < I(X_2;Y\mid X_1)$ , $R_1+R_2 < I(X_1,X_2;Y)$	Product inputs, convex hull.
Pentagon corner B	$\big(I(X_1;Y\mid X_2),\ I(X_2;Y)\big)$	Onion peeling.
Time-sharing	$\lvert\mathcal Q\rvert \le 4$	Carathéodory in $\mathbb R^3$ .
$m$ users	$R(S) \le I(X(S);Y\mid X(S^c))$	Beveled box.
Slepian–Wolf	$R_1 \ge H(X\mid Y)$ , $R_2 \ge H(Y\mid X)$ , $R_1+R_2 \ge H(X,Y)$	Separate encoding costs nothing in total.
Binning	rate $> H$ suffices	Hash; only the decoder needs the model.
Degraded broadcast	$R_2 \le I(U;Y_2)$ , $R_1 \le I(X;Y_1\mid U)$	Clouds and satellites.
Binary symmetric broadcast	$\big(H(\betap_1)-H(p_1),\ 1-H(\betap_2)\big)$	Sweep $\beta \in [0,\frac12]$ .
Degraded relay	$\sup\min\{I(X,X_1;Y),\ I(X;Y_1\mid X_1)\}$	Max-flow min-cut is achieved.
Coded side information	$R_1 \ge H(X\mid U)$ , $R_2 \ge I(Y;U)$	Quantize the helper.
Wyner–Ziv	$\min\big(I(X;W) - I(Y;W)\big)$	Bin the rate distortion codebook.
Cut-set	$\sum_{S\rightarrow S^c}R \le I(X^{(S)};Y^{(S^c)}\mid X^{(S^c)})$	Upper bound, not always achievable.

Facts to keep to hand

Every achievability proof is “candidates times $2^{-nI}$ ”. Random codebooks, jointly typical decoding and the union bound. Each rate constraint says the number of confusable alternatives must be exponentially smaller than $2^{nI}$ (channels) or the number of bins must exceed $2^{nH}$ (sources).
Decode some, treat the rest as noise, subtract. Onion peeling gives the corners of the multiple-access region, successive cancellation the broadcast region, and the strong-interference result. Interference you can decode is interference you can remove.
Separated encoders lose nothing in total for correlated sources, if the decoder is joint. Binning moves all the modelling to the decoder.
Auxiliary random variables carry the structure. $Q$ for time-sharing, $U$ for clouds or a quantized helper, $W$ for Wyner–Ziv descriptions. Carathéodory-type bounds keep them finite.
Networks break single-user intuition. Cut-set bounds are often loose, source–channel separation fails, and feedback can enlarge capacity regions.

References

Cover & Thomas, Elements of Information Theory — Chapter 15

Related

Motivation: from one wire to a telegraph network

Gaussian multiple-user channels: the preview

Single user

Multiple access: mmm users, one receiver

Broadcast: one sender, two receivers

Relay: a repeater station

Interference: two pairs talking over each other

Two-way: a full-duplex line

Jointly typical sequences

The multiple-access channel

Examples

Achievability

The pentagon and its corners

Convexity and time-sharing

Converse

mmm users

The Gaussian multiple-access channel in detail

Encoding of correlated sources (Slepian–Wolf)

Random binning

Achievability

Converse

Interpretation: colouring the fans

Duality between Slepian–Wolf coding and the multiple-access channel

The broadcast channel

Degraded broadcast channels

The relay channel

Source coding with side information

Rate distortion with side information (Wyner–Ziv)

General multiterminal networks

Two single-user facts that fail in networks

Quick reference

References

Multiple access: $m$ users, one receiver

$m$ users