Network Information Theory: Multiple Access, Broadcast, and Relay¶

Job: develop the MAC capacity region (Ahlswede–Liao / polymatroid), the broadcast (Cover / superposition), the relay (Cover–El Gamal) and interference (Han–Kobayashi), and the network coding (Ahlswede–Cai–Li–Yeung / max-flow min-cut) — with the Gaussian MAC capacity region as the worked example.

Core¶

Multiple access (MAC)¶

The MAC channel $Y=X_1+X_2+Z$, the capacity region $\{(R_1,R_2):R_1\le I(X_1;Y|X_2),\,R_2\le I(X_2;Y|X_1),\,R_1+R_2\le I(X_1,X_2;Y)\}$ (the Ahlswede–Liao, the polymatroid).

MAC / capacity region	Description
MAC	$Y=X_1+X_2+Z$ (the multiple access, the two senders)
Capacity region	${R_1\le I(X_1;Y
Polymatroid	the capacity region the polymatroid (the corner points $(R_1,0),(0,R_2)$, the sum-rate face)

Broadcast (BSC)¶

The broadcast channel $W(y_1|x)W(y_2|x)$, the degraded $Y_1=X+Z_1,\,Y_2=Y_1+Z_2$, the capacity region $\{R_1\le I(X;Y_1|U),\,R_2\le I(U;Y_2)\}$ (the Cover, the superposition).

Broadcast / degraded / superposition	Description
Broadcast	$W(y_1
Degraded	$Y_1=X+Z_1,\,Y_2=Y_1+Z_2$ (the degraded, the $Y_2$ the worse)
Capacity region	${R_1\le I(X;Y_1

Relay and interference¶

Relay / Cover–El Gamal / interference	Description
Relay channel	$(Y_1,Y_2)$ the relay $Y_1$ forwards to $Y_2$ (the Cover–El Gamal: the decode-and-forward, the compress-and-forward)
Cover–El Gamal	the decode-and-forward / the compress-and-forward (the capacity the open)
Interference	the Han–Kobayashi (the interference channel, the capacity the open)

Network coding and the max-flow min-cut¶

Network coding / max-flow min-cut	Description
Network coding (Ahlswede–Cai–Li–Yeung)	the multicast the max-flow min-cut (the routing the insufficient, the coding the optimal)
Max-flow min-cut	the network the cut, the capacity the min-cut (the optimization)
Routing vs coding	the routing the insufficient, the coding the optimal (the multicast the gap)

See it¶

Gaussian MAC capacity region and the polymatroid. The Gaussian MAC $Y=X_1+X_2+Z$ ($Z\sim\mathcal{N}(0,N)$, the power $P_1,P_2$), the capacity region $\{R_1\le\frac12\log(1+P_1/N),\,R_2\le\frac12\log(1+P_2/N),\,R_1+R_2\le\frac12\log(1+(P_1+P_2)/N)\}$ (the Ahlswede–Liao, the polymatroid the corner points the $(R_1,0),(0,R_2)$, the sum-rate the face). The key point: the MAC the capacity region the polymatroid (the corner points, the sum-rate), the Gaussian the explicit.

Check¶

Show that the MAC capacity region is a polymatroid, and explain the corner points.

The MAC region $\{R_1\le I(X_1;Y|X_2),\,R_2\le I(X_2;Y|X_1),\,R_1+R_2\le I(X_1,X_2;Y)\}$ (the Ahlswede–Liao). The polymatroid: the region is the polymatroid (the submodular, the monotone, the $R_i\ge0$), the corner points the $(I(X_1;Y|X_2),0)$, $(0,I(X_2;Y|X_1))$, the sum-rate the $I(X_1,X_2;Y)$ the face. The Gaussian: the $\frac12\log(1+P_i/N)$ the individual, the $\frac12\log(1+(P_1+P_2)/N)$ the sum (the polymatroid the corner points, the sum-rate the face).

Explain the broadcast superposition coding and the degraded channel.

The degraded broadcast $Y_1=X+Z_1,\,Y_2=Y_1+Z_2$ ($Y_2$ the degraded / the worse receiver). The superposition: $U\to X$ (the $U$ the message for $Y_2$, the $X$ the refinement for $Y_1$), the $R_2\le I(U;Y_2)$ (the $U$ decoded by $Y_2$), the $R_1\le I(X;Y_1|U)$ (the $X$ the refinement decoded by $Y_1$ given $U$). The Cover: the capacity region $\{R_1\le I(X;Y_1|U),\,R_2\le I(U;Y_2)\}$ (the superposition, the degraded).

Pitfalls¶

The MAC the polymatroid (the corner points, the sum-rate the face) — the capacity region the polymatroid, the corner points the $(R_1,0),(0,R_2)$.
The broadcast the degraded (the $Y_2$ the worse, the superposition $U\to X$) — the degraded the Cover, the non-degraded the open.
The relay the open (the Cover–El Gamal the decode-and-forward / the compress-and-forward, the capacity the open) — the relay the open, the Cover–El Gamal the bounds.
The network coding the multicast (the Ahlswede–Cai–Li–Yeung the max-flow min-cut, the routing the insufficient) — the multicast the coding the optimal, the non-multicast the open.

Refs¶

Ahlswede–Liao, "Multi-way communication channels" (1971); Cover, "Broadcast channels" (1972)
Cover–El Gamal, "Capacity theorems for the relay channel" (1979); Han–Kobayashi, "Interference channel" (1981)
Ahlswede–Cai–Li–Yeung, "Network information flow" (2000); the network coding

Next¶

IT index · Foundations · Rate-Distortion & Lossy · Finite-Blocklength & Dispersion · Quantum & Large Deviations · Optimization