Multi-user Information Theory — Mathematics Knowledge System

Overview

Multi-user information theory extends Shannon's single-user channel capacity to networks with multiple senders and receivers. Key settings include the multiple-access channel (MAC, many senders -- one receiver), broadcast channel (one sender -- many receivers), interference channel (multiple sender-receiver pairs sharing a medium), and relay channel. Unlike single-user channels, the capacity region (the set of achievable rate tuples) can be a complex convex polytope. Superposition coding, successive cancellation decoding, and dirty paper coding are the fundamental tools.

Intuition

In a coffee shop with WiFi, multiple users (MAC) compete for the same bandwidth. The capacity region describes all rate pairs (R_1, R_2) that both users can simultaneously achieve. Unlike a single user who can use the full capacity C, with two users the achievable rates trade off: if user 1 uses rate R_1 near C, user 2 is left with little. The MAC capacity region is a pentagon bounded by individual capacities and the sum-rate constraint. Broadcast is the dual: one transmitter sends to multiple receivers, and superposition coding achieves the full region.

Formal Definition

Definition

The two-user MAC has inputs X_1, X_2, output Y, and transition probability p(y|x_1, x_2). The capacity region is the closure of the set of (R_1, R_2) such that R_1 <= I(X_1; Y | X_2), R_2 <= I(X_2; Y | X_1), R_1 + R_2 <= I(X_1, X_2; Y), for some product input distribution p(x_1)p(x_2). The degraded broadcast channel with channel p(y_1|x)p(y_2|y_1) achieves rates R_1 <= I(X; Y_1 | U), R_2 <= I(U; Y_2) via superposition coding with auxiliary variable U.

R_1 \le I(X_1; Y \mid X_2),\quad R_2 \le I(X_2; Y \mid X_1),\quad R_1+R_2 \le I(X_1,X_2; Y)

MAC capacity region constraints

C_{\mathrm{sum}} = \max_{p(x_1)p(x_2)} I(X_1,X_2; Y)

Sum-rate capacity of MAC

C_{\mathrm{DPC}} = \frac{1}{2}\log\!\left(1 + \frac{P}{N}\right)

Dirty paper coding achieves same capacity as no interference

C_{\mathrm{Gaussian\ BC}} = \frac{1}{2}\log\!\left(1 + \frac{\alpha P}{N_1}\right),\; \frac{1}{2}\log\!\left(1 + \frac{(1-\alpha)P}{\alpha P + N_2}\right)

Gaussian broadcast channel rates

Notation

Notation	Meaning
$R_1, R_2$	Information rates of users 1 and 2
$I(X;Y\|Z)$	Conditional mutual information
$\mathcal{C}$	Capacity region (set of achievable rate tuples)

Theorems

Theorem 1: Multiple-Access Channel Capacity Region

The capacity region of the MAC with transition p(y|x_1,x_2) is the closure of the convex hull of all (R_1, R_2) satisfying R_1 <= I(X_1;Y|X_2), R_2 <= I(X_2;Y|X_1), R_1+R_2 <= I(X_1,X_2;Y) for some product distribution p(x_1)p(x_2). The boundary is achieved by successive cancellation decoding.

Theorem 2: Costa's Dirty Paper Coding Theorem

Consider the Gaussian channel Y = X + S + Z where S is interference known non-causally at the transmitter (but not the receiver), Z ~ N(0,N) is noise, and X has power constraint P. The capacity equals (1/2)*log(1 + P/N) -- the same as if S were absent. The interference can be pre-cancelled at the transmitter using a random binning argument.

Theorem 3: Degraded Broadcast Channel

For a degraded broadcast channel p(y_1, y_2 | x) = p(y_1 | x) p(y_2 | y_1), the capacity region is achieved by superposition coding: encode user 2's message as a coarse layer X_2 (auxiliary U), and user 1's message as a fine layer on top. Rates R_2 <= I(U; Y_2) and R_1 <= I(X; Y_1 | U) are simultaneously achievable.

Worked Examples

1
For Gaussian MAC, the sum-rate capacity is achieved by Gaussian inputs.
$C_{\mathrm{sum}} = \max_{P_1 \le P, P_2 \le P} I(X_1, X_2; Y)$
2
With X_1 ~ N(0,P), X_2 ~ N(0,P) independent, X_1 + X_2 ~ N(0, 2P).
$I(X_1, X_2; Y) = \frac{1}{2}\log\!\left(1 + \frac{2P}{N}\right)$
3
Individual capacity constraints: each user alone achieves C_i = (1/2) log(1 + P/N).
$R_i \le \frac{1}{2}\log\!\left(1 + \frac{P}{N}\right)$

✓ Answer

The MAC capacity region is the pentagon: R_1 <= (1/2)log(1 + P/N), R_2 <= (1/2)log(1 + P/N), R_1 + R_2 <= (1/2)log(1 + 2P/N).

Practice Problems

Hardfree response

Explain the duality between the MAC and the broadcast channel, and how it is used to derive the broadcast channel capacity region.

Common Mistakes

Common Mistake

Thinking the MAC capacity region is always a rectangle (each user achieves their individual capacity simultaneously).

The MAC capacity region is a pentagon, not a rectangle. Users can simultaneously achieve their individual rates only along the boundary of the region, and the sum-rate is bounded by I(X_1,X_2;Y), which is typically less than C_1 + C_2.

Quiz

The MAC sum-rate constraint R_1 + R_2 <= I(X_1, X_2; Y) arises from:

Each user occupying half the bandwidthThe total mutual information from both users' combined input to the outputThe Nyquist sampling theoremThe minimum of the individual capacities

Historical Background

Multi-user information theory began with Shannon's two-way channel (1961). Ahlswede and Liao independently solved the multiple-access channel in 1971-73. Cover and Bergmans characterised the Gaussian broadcast channel in 1972. The interference channel remains largely open -- a fundamental open problem in information theory. Costa's dirty paper coding theorem (1983) showed that known interference can be pre-cancelled at the transmitter, a result key to MIMO precoding.

1961
Shannon analyses the two-way channel
Claude Shannon
1971
Ahlswede characterises the MAC capacity region
Rudolf Ahlswede
1972
Cover and Bergmans solve the degraded broadcast channel
Thomas Cover, Patrick Bergmans
1983
Costa proves the dirty paper coding theorem
Max Costa

Summary

Multi-user IT extends Shannon capacity to networks: MAC, broadcast, interference, relay channels.
MAC capacity region: bounded by R_1 <= I(X_1;Y|X_2), R_2 <= I(X_2;Y|X_1), R_1+R_2 <= I(X_1,X_2;Y).
Broadcast: superposition coding achieves the degraded BC capacity region.
Costa's dirty paper coding: known interference at the transmitter does not reduce capacity.

References

BookCover, T.M. and Thomas, J.A. Elements of Information Theory. Wiley, 2006. Chapters 14-15.
BookEl Gamal, A. and Kim, Y.-H. Network Information Theory. Cambridge, 2011.
WebsiteWikipedia -- Multiple-access channel