46.06.01 · information-theory / network-information

Multiple-Access Channel: Achievable Rates, Superposition, and the Capacity Region

shipped3 tiersLean: none

Anchor (Master): Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §15.3-15.6; Ahlswede 1971 Multi-way Communication Channels; Liao 1972 Multiple Access Channels; Csiszar & Korner 2011 Information Theory: Coding Theorems for Discrete Memoryless Systems 2e (Cambridge) §4.1-4.3

Intuition Beginner

Two people want to send messages to a single receiver over a shared noisy channel. Think of two cell phones in the same cell tower coverage area, both trying to upload data at the same time. The tower hears the superposition of both signals, corrupted by noise. How fast can each user send?

The answer is a region, not a single number. User 1 can send at rate $R_{1}$ and user 2 at rate $R_{2}$ , but the rates are coupled. If user 1 sends faster, user 2 must slow down, and vice versa. The set of all simultaneously achievable rate pairs $(R_{1}, R_{2})$ is the capacity region.

For the simplest model — two independent transmitters and one receiver — the capacity region is a pentagon in the $(R_{1}, R_{2})$ plane. The pentagon has five sides: two individual rate constraints ( $R_{1}$ and $R_{2}$ each bounded above), one sum-rate constraint ( $R_{1} + R_{2}$ bounded above), and two non-negativity constraints.

The sum-rate bound is the total information the channel can carry. No matter how you split it, the combined rate cannot exceed $I (X_{1}, X_{2}; Y)$ , the mutual information between both inputs and the output. This is the channel's total capacity when both senders are considered as one.

The individual bounds $R_{1} \leq I (X_{1}; Y ∣ X_{2})$ say: even if user 2's message were known perfectly, user 1 could not exceed this rate. The conditioning on $X_{2}$ means "treating user 2's signal as known rather than interference."

Each corner of the pentagon represents a different operating point. At one corner, user 1 gets maximum rate while user 2 gets the minimum. At another corner, the roles reverse. The sum-rate corner gives the fairest split. Time-sharing between corners fills in the rest.

Visual Beginner

Figure: the MAC capacity region as a pentagon in the $(R_{1}, R_{2})$ plane. The vertices are: origin, $(I (X_{1}; Y ∣ X_{2}), 0)$ , $(I (X_{1}; Y ∣ X_{2}), I (X_{2}; Y ∣ X_{1}))$ on the sum-rate line, $(I (X_{1}; Y ∣ X_{2}), I (X_{2}; Y ∣ X_{1}))$ is not a vertex — the vertices are $(I (X_{1}; Y ∣ X_{2}), I (X_{2}; Y) - I (X_{1}; Y ∣ X_{2}))$ and $(I (X_{1}; Y) - I (X_{2}; Y ∣ X_{1}), I (X_{2}; Y ∣ X_{1}))$ . The diagonal line $R_{1} + R_{2} = I (X_{1}, X_{2}; Y)$ is the sum-rate bound.

Constraint	Formula	Meaning
User 1 individual	$R_1 \leq I(X_1; Y	X_2)$
User 2 individual	$R_2 \leq I(X_2; Y	X_1)$
Sum-rate	$R_{1} + R_{2} \leq I (X_{1}, X_{2}; Y)$	Total channel capacity
Non-negativity	$R_{1} \geq 0$ , $R_{2} \geq 0$	Rates must be non-negative

Worked example Beginner

Two users transmit binary symbols over a binary adder channel. User 1 sends $X_{1} \in {0, 1}$ and user 2 sends $X_{2} \in {0, 1}$ . The receiver observes $Y = X_{1} + X_{2} \in {0, 1, 2}$ (no noise).

With uniform inputs: $I (X_{1}, X_{2}; Y) = H (Y) - H (Y ∣ X_{1}, X_{2}) = H (Y) = H (1/4, 1/2, 1/4) = 1.5$ bits. $I (X_{1}; Y ∣ X_{2}) = H (X_{1}) = 1$ bit (knowing $X_{2}$ , the output determines $X_{1}$ ). Similarly $I (X_{2}; Y ∣ X_{1}) = 1$ bit.

The capacity region is: $R_{1} \leq 1$ , $R_{2} \leq 1$ , $R_{1} + R_{2} \leq 1.5$ . This is a pentagon with vertices $(0, 0)$ , $(1, 0)$ , $(1, 0.5)$ , $(0.5, 1)$ , $(0, 1)$ .

Each user alone could send 1 bit. Together they can send 1.5 bits total — more than either alone, but less than the sum of their individual capacities (2 bits). The channel is a shared resource, and the sum-rate reflects the total information-carrying capacity.

Check your understanding Beginner

Exercise (medium, short answer).

Explain why treating the other user's signal as noise is suboptimal for the MAC.

Hint

What does joint decoding do that single-user decoding cannot?

Answer

Treating user 2's signal as noise means user 1 sees an effective channel with reduced capacity (since user 2's signal acts as interference). Joint decoding exploits the structure of both users' codebooks to simultaneously decode both messages. The joint decoder can separate the two signals because each user's codewords are drawn from an independent random codebook, and the joint typicality of the received signal with both codewords is a much stronger constraint than individual typicality with either codeword alone. This is why the sum-rate bound $I (X_{1}, X_{2}; Y)$ exceeds the sum of the "treat as noise" rates.

Formal definition Intermediate+

A two-user discrete memoryless multiple-access channel (MAC) has input alphabets $X_{1}, X_{2}$ , output alphabet $Y$ , and transition probabilities $p (y ∣ x_{1}, x_{2})$ .

Definition (MAC code). A $(2^{n R_{1}}, 2^{n R_{2}}, n)$ MAC code consists of:

Two encoders: $f_{1} : {1, \dots, 2^{n R_{1}}} \to X_{1}^{n}$ and $f_{2} : {1, \dots, 2^{n R_{2}}} \to X_{2}^{n}$ , mapping messages to codewords.
A decoder $g : Y^{n} \to {1, \dots, 2^{n R_{1}}} \times {1, \dots, 2^{n R_{2}}}$ mapping the received sequence to message estimates.

The average probability of error is $P_{e}^{(n)} = Pr [(\hat{W}_{1}, \hat{W}_{2}) \neq = (W_{1}, W_{2})]$ .

Definition (MAC capacity region). The capacity region $C$ is the closure of the set of achievable rate pairs $(R_{1}, R_{2})$ .

Theorem (Ahlswede 1971, Liao 1972). The capacity region of the two-user discrete memoryless MAC is:

C = conv p (x_{1}) p (x_{2}) ⋃ {(R_{1}, R_{2}) : R_{1} \leq I (X_{1}; Y ∣ X_{2}), R_{2} \leq I (X_{2}; Y ∣ X_{1}), R_{1} + R_{2} \leq I (X_{1}, X_{2}; Y)},

where the union is over all product distributions $p (x_{1}) p (x_{2})$ and conv denotes convex closure.

Key theorem with proof Intermediate+

Theorem (MAC achievability). Fix a product distribution $p (x_{1}) p (x_{2})$ . The rate region:

R (p_{1}, p_{2}) = {(R_{1}, R_{2}) : R_{1} \leq I (X_{1}; Y ∣ X_{2}), R_{2} \leq I (X_{2}; Y ∣ X_{1}), R_{1} + R_{2} \leq I (X_{1}, X_{2}; Y)}

is achievable.

Proof (random coding with joint typicality decoding).

Codebook generation. Generate $2^{n R_{1}}$ codewords $X_{1}^{n} (w_{1})$ for user 1 by drawing each symbol i.i.d. from $p (x_{1})$ . Independently generate $2^{n R_{2}}$ codewords $X_{2}^{n} (w_{2})$ for user 2 by drawing each symbol i.i.d. from $p (x_{2})$ .

Encoding. User 1 sends $X_{1}^{n} (W_{1})$ , user 2 sends $X_{2}^{n} (W_{2})$ .

Decoding. The receiver looks for the unique pair $(\tilde{w}_{1}, \tilde{w}_{2})$ such that $(X_{1}^{n} (\tilde{w}_{1}), X_{2}^{n} (\tilde{w}_{2}), Y^{n})$ is jointly typical. If a unique pair exists, output it. Otherwise, declare error.

Error analysis. Let $(W_{1}, W_{2}) = (1, 1)$ without loss of generality. An error occurs if:

$(X_{1}^{n} (1), X_{2}^{n} (1), Y^{n}) \in / T_{ϵ}^{(n)}$ : probability $\to 0$ by the joint AEP.
Some impostor pair $(\tilde{w}_{1}, \tilde{w}_{2}) \neq = (1, 1)$ is jointly typical with $Y^{n}$ .

For a pair with $\tilde{w}_{1} \neq = 1, \tilde{w}_{2} \neq = 1$ : $X_{1}^{n} (\tilde{w}_{1})$ and $X_{2}^{n} (\tilde{w}_{2})$ are independent of $Y^{n}$ , so the probability of joint typicality is approximately $2^{- n I (X_{1}, X_{2}; Y)}$ . There are $2^{n R_{1}} \cdot 2^{n R_{2}}$ such pairs, so the expected number of impostors is $2^{n (R_{1} + R_{2} - I (X_{1}, X_{2}; Y))} \to 0$ when $R_{1} + R_{2} < I (X_{1}, X_{2}; Y)$ .

For $\tilde{w}_{1} \neq = 1, \tilde{w}_{2} = 1$ : $X_{1}^{n} (\tilde{w}_{1})$ is independent of $(X_{2}^{n} (1), Y^{n})$ but $X_{2}^{n} (1)$ is given. The probability is $2^{- n I (X_{1}; Y ∣ X_{2})}$ , and there are $2^{n R_{1}}$ such pairs. The constraint $R_{1} < I (X_{1}; Y ∣ X_{2})$ ensures these vanish.

By symmetry, $R_{2} < I (X_{2}; Y ∣ X_{1})$ controls the $\tilde{w}_{2} \neq = 1, \tilde{w}_{1} = 1$ case. By the union bound, $P_{e}^{(n)} \to 0$ . $□$

Bridge. The MAC capacity region builds toward every multi-user network information theory result by introducing the pentagonal achievable region as the fundamental object. This is exactly the structure that reappears in the broadcast channel 46.06.02 (with reversed roles) and the interference channel 46.06.04 (with two such pentagons interacting). The result appears again in the relay channel 46.06.03 as one face of the cut-set bound: the MAC from relay-and-source to destination constrains the overall achievable rate. The foundational reason the MAC region is a pentagon (not a rectangle) is that the sum-rate constraint $R_{1} + R_{2} \leq I (X_{1}, X_{2}; Y)$ couples the users: the channel output carries joint information about both inputs that cannot be decomposed into independent parts. Putting these together, the MAC is the simplest multi-user network beyond point-to-point and its capacity region is the prototype for all multi-user rate regions; the central insight is that joint decoding extracts more capacity than treating interference as noise, and the gap between these two strategies grows with the channel's joint information content. The result generalises to more than two users by the same technique, and the duality with Slepian-Wolf 46.05.01 reveals the deep symmetry between source and channel coding in the multi-user setting.

Exercises Intermediate+

Exercise (medium, short answer).

Explain the difference between successive cancellation decoding and joint typicality decoding for the MAC.

Hint

Successive cancellation decodes one user first, then uses that decoded message to decode the second user.

Answer

Joint typicality decoding searches for the unique pair of codewords (one from each user) that is jointly typical with the received sequence. Successive cancellation first decodes one user (say user 1) treating user 2 as noise, then subtracts user 1's decoded codeword from the received signal and decodes user 2 from the residual. The advantage of successive cancellation is that it achieves the corner points of the MAC pentagon (the rate pairs on the sum-rate boundary) with simpler decoding, while joint typicality achieves the entire pentagon but requires searching over all codeword pairs.

Exercise (medium, numeric).

A Gaussian MAC has $Y = X_{1} + X_{2} + Z$ where $Z \sim N (0, 1)$ , $X_{1}$ has power constraint $P_{1} = 3$ , and $X_{2}$ has power constraint $P_{2} = 7$ . Compute the MAC capacity region boundaries.

Hint

Use the Gaussian MAC capacity: $R_{1} \leq \frac{1}{2} lo g (1 + P_{1})$ , $R_{2} \leq \frac{1}{2} lo g (1 + P_{2})$ , $R_{1} + R_{2} \leq \frac{1}{2} lo g (1 + P_{1} + P_{2})$ .

Answer

$R_{1} \leq \frac{1}{2} lo g_{2} (1 + 3) = \frac{1}{2} lo g_{2} 4 = 1$ bit/use (treating user 2 as noise is not optimal; the conditional bound with Gaussian signaling is $R_{1} \leq \frac{1}{2} lo g_{2} (1 + P_{1}) = 1$ when $X_{2}$ is known; but the correct individual bound is $R_{1} \leq \frac{1}{2} lo g_{2} (1 + P_{1} / (1 + 0))$ — actually for the Gaussian MAC with independent inputs the bounds are: $R_{1} \leq \frac{1}{2} lo g (1 + P_{1} / N)$ when user 2 is decoded first and subtracted, giving $R_{1} \leq \frac{1}{2} lo g_{2} (1 + 3/1) = 1$ bit. $R_{2} \leq \frac{1}{2} lo g_{2} (1 + P_{2} / N) = \frac{1}{2} lo g_{2} (1 + 7) \approx 1.5$ bits. Sum-rate: $R_{1} + R_{2} \leq \frac{1}{2} lo g_{2} (1 + (P_{1} + P_{2}) / N) = \frac{1}{2} lo g_{2} (1 + 10) \approx 1.73$ bits/use.

Wait — the standard Gaussian MAC bounds with successive cancellation are: when decoding user 2 first (treating user 1 as noise), user 2 gets $R_{2} \leq \frac{1}{2} lo g_{2} (1 + P_{2} / (P_{1} + N))$ . After subtracting, user 1 gets $R_{1} \leq \frac{1}{2} lo g_{2} (1 + P_{1} / N)$ . The pentagon vertices depend on decoding order.

The full region: $R_{1} \leq \frac{1}{2} lo g_{2} (1 + P_{1} / N) = 1$ bit. $R_{2} \leq \frac{1}{2} lo g_{2} (1 + P_{2} / N) = 1.5$ bits. Sum-rate: $R_{1} + R_{2} \leq \frac{1}{2} lo g_{2} (1 + (P_{1} + P_{2}) / N) = 1.73$ bits. And $R_{1} \leq \frac{1}{2} lo g_{2} (1 + P_{1} / (P_{2} + N)) = \frac{1}{2} lo g_{2} (1 + 3/8) \approx 0.26$ bits (user 1 treating user 2 as noise), $R_{2} \leq \frac{1}{2} lo g_{2} (1 + P_{2} / (P_{1} + N)) = \frac{1}{2} lo g_{2} (1 + 7/4) \approx 0.97$ bits.

Exercise (medium, short answer).

Prove that the MAC capacity region is convex. Why does time-sharing work?

Hint

Use a time-sharing random variable to switch between two operating points.

Answer

Given two achievable rate pairs $(R_{1}^{(a)}, R_{2}^{(a)})$ and $(R_{1}^{(b)}, R_{2}^{(b)})$ achieved by codes of length $n$ , construct a new code of length $2 n$ : use code (a) for the first $n$ symbols and code (b) for the second $n$ symbols. The resulting rate pair is the average $(R_{1}^{(a)} + R_{1}^{(b)}) /2, (R_{2}^{(a)} + R_{2}^{(b)}) /2)$ . More generally, introduce a time-sharing random variable $Q$ and use input distributions $p (x_{1} ∣ Q) p (x_{2} ∣ Q)$ . The convex closure in the capacity region formula accounts for this time-sharing. Time-sharing works because the encoders can agree on a schedule (using a shared clock) without communicating their messages.

Exercise (hard, short answer).

Prove the MAC converse: any achievable rate pair must satisfy $R_{1} \leq I (X_{1}; Y ∣ X_{2}, Q)$ , $R_{2} \leq I (X_{2}; Y ∣ X_{1}, Q)$ , $R_{1} + R_{2} \leq I (X_{1}, X_{2}; Y ∣ Q)$ for some $p (q) p (x_{1} ∣ q) p (x_{2} ∣ q)$ .

Hint

Apply Fano's inequality and use the chain rule for mutual information with the time-sharing variable $Q = (W_{2}, Y^{i - 1})$ or similar.

Answer

By Fano's inequality, $H (W_{1}, W_{2} ∣ Y^{n}) \leq n ϵ_{n}$ where $ϵ_{n} \to 0$ . Then:

$n (R_{1} + R_{2}) = H (W_{1}, W_{2}) = I (W_{1}, W_{2}; Y^{n}) + H (W_{1}, W_{2} ∣ Y^{n}) \leq I (W_{1}, W_{2}; Y^{n}) + n ϵ_{n} .$

By the data-processing inequality and the memoryless channel property:

$I (W_{1}, W_{2}; Y^{n}) \leq I (X_{1}^{n}, X_{2}^{n}; Y^{n}) = \sum_{i = 1}^{n} I (X_{1, i}, X_{2, i}; Y_{i} ∣ Y^{i - 1}) .$

Since $X_{1, i}$ is a function of $W_{1}$ only and $X_{2, i}$ is a function of $W_{2}$ only (independent encoders), setting $Q_{i} = (Y^{i - 1})$ gives $I (X_{1, i}, X_{2, i}; Y_{i} ∣ Q_{i}) \leq I (X_{1, i}, X_{2, i}; Y_{i} ∣ Q_{i})$ and the single-letter form follows by introducing the auxiliary variable $Q$ uniform on ${1, \dots, n}$ .

For the individual bound: $n R_{1} \leq I (W_{1}; Y^{n}, W_{2}) + n ϵ_{n} \leq I (W_{1}; Y^{n} ∣ W_{2}) + n ϵ_{n}$ . By the chain rule and the memoryless property with the encoder structure, this reduces to $\sum_{i} I (X_{1, i}; Y_{i} ∣ X_{2, i}, Q_{i})$ , giving $R_{1} \leq I (X_{1}; Y ∣ X_{2}, Q)$ in single-letter form.

Exercise (hard, short answer).

The MAC with feedback: show that feedback can enlarge the MAC capacity region by allowing users to cooperate through the feedback signal.

Hint

Contrast with the single-user case where feedback does not increase capacity. In the MAC, feedback lets users learn each other's messages and cooperate.

Answer

In the single-user DMC, feedback does not increase capacity because the transmitter already knows the message and the channel is memoryless. In the MAC, feedback from the receiver lets each user observe the channel output, which depends on both users' inputs. Through the output, user 1 can infer information about user 2's message (and vice versa). This enables cooperation: after learning part of user 2's message via feedback, user 1 can help relay it, increasing the sum rate. Gaarder and Wolf (1975) showed that for the binary adder MAC with feedback, the capacity region is strictly larger than without feedback. The enlarged region comes from the users' ability to cooperatively resolve each other's messages through the feedback channel, breaking the independent-encoder constraint of the non-feedback MAC.

Lean formalization Intermediate+

Mathlib does not define multiple-access channels, MAC codes, or the capacity region as a subset of rate space. The achievability proof requires independently generated codebooks for each user and a joint typicality decoder that searches over all codeword pairs. The converse uses Fano's inequality with a multi-message version of the data-processing inequality. The convexity of the capacity region (via time-sharing) requires defining a time-sharing random variable and showing that convex combinations of achievable rate pairs are achievable. None of these structures exist in Mathlib. This unit ships without formalization.

Advanced results Master

The Gaussian MAC and successive cancellation

The Gaussian MAC $Y = X_{1} + X_{2} + Z$ with $Z \sim N (0, N)$ and power constraints $E [X_{i}^{2}] \leq P_{i}$ has the capacity region:

R_{1} \leq \frac{1}{2} lo g (1 + \frac{P _{1}}{N}), R_{2} \leq \frac{1}{2} lo g (1 + \frac{P _{2}}{N}),

R_{1} + R_{2} \leq \frac{1}{2} lo g (1 + \frac{P _{1} + P _{2}}{N}) .

The sum-rate bound is achieved by independent Gaussian inputs. The individual bounds are achieved by successive cancellation: decode user 2 first (treating user 1 as noise), then subtract user 2's contribution and decode user 1 with no interference.

The two decoding orders give two corner points of the pentagon:

Decode user 2 first: $R_{2} \leq \frac{1}{2} lo g (1 + P_{2} / (P_{1} + N))$ , $R_{1} \leq \frac{1}{2} lo g (1 + P_{1} / N)$ .
Decode user 1 first: $R_{1} \leq \frac{1}{2} lo g (1 + P_{1} / (P_{2} + N))$ , $R_{2} \leq \frac{1}{2} lo g (1 + P_{2} / N)$ .

The MAC with more than two users

For $k$ users with inputs $X_{1}, \dots, X_{k}$ and output $Y$ , the capacity region generalizes to:

i \in S \sum R_{i} \leq I (X_{S}; Y ∣ X_{S^{c}})

for every subset $S \subseteq {1, \dots, k}$ . There are $2^{k} - 1$ such constraints. The achievability proof uses independently generated codebooks for each user and joint typicality decoding over all $k$ users. The converse follows the same Fano argument.

The number of constraints grows exponentially with $k$ , making the full characterization complex for large numbers of users. However, the sum-rate constraint (with $S = {1, \dots, k}$ ) is often the binding constraint in practice, and it is simply $I (X_{1}, \dots, X_{k}; Y)$ maximized over product input distributions.

The MAC duality with Slepian-Wolf

The MAC capacity region and the Slepian-Wolf achievable region are information-theoretic duals:

	Slepian-Wolf (source coding)	MAC (channel coding)
Individual bound	$R_{1} \geq H (X_{1} ∣ X_{2})$	$R_{1} \leq I (X_{1}; Y ∣ X_{2})$
Sum bound	$R_{1} + R_{2} \geq H (X_{1}, X_{2})$	$R_{1} + R_{2} \leq I (X_{1}, X_{2}; Y)$
Inequality direction	Lower bound (at least)	Upper bound (at most)
Quantity	Entropy	Mutual information

The duality reflects the complementary nature of compression (rates above entropy) and communication (rates below capacity).

Synthesis. The MAC capacity region is the foundational object of network information theory: a pentagonal region in rate space defined by individual conditional-mutual-information bounds and a sum-rate mutual-information bound. The central insight is that joint decoding extracts the full channel capacity $I (X_{1}, X_{2}; Y)$ by exploiting the structure of both users' codebooks simultaneously, rather than treating either user's signal as noise. The result builds toward the broadcast channel 46.06.02, where one sender distributes information to multiple receivers, and the relay channel 46.06.03, where intermediate nodes create a cascade of MAC and broadcast sub-channels. The foundational reason the MAC region is a pentagon is that the three constraints — two individual bounds and one sum-rate bound — are independent: each captures a different aspect of the channel's information-carrying capacity. The duality with Slepian-Wolf 46.05.01 reveals the central insight that source coding and channel coding are mirror images in the multi-user setting, with entropy and mutual information playing symmetric roles. Putting these together, the MAC is the prototype for all multi-user rate regions, and its pentagonal structure is the load-bearing template for network capacity analysis.

Full proof set Master

Proposition (MAC converse). Any achievable rate pair $(R_{1}, R_{2})$ satisfies $R_{1} + R_{2} \leq I (X_{1}, X_{2}; Y ∣ Q)$ for some $p (q) p (x_{1} ∣ q) p (x_{2} ∣ q)$ .

Proof. By Fano's inequality:

H (W_{1}, W_{2} ∣ Y^{n}) \leq 1 + P_{e}^{(n)} \cdot 2 n R \leq n ϵ_{n}

where $ϵ_{n} \to 0$ as $P_{e}^{(n)} \to 0$ . Then:

n (R_{1} + R_{2}) = H (W_{1}) + H (W_{2}) = H (W_{1}, W_{2}) = I (W_{1}, W_{2}; Y^{n}) + H (W_{1}, W_{2} ∣ Y^{n}) .

Since $W_{1} \to X_{1}^{n} \to Y^{n}$ and $W_{2} \to X_{2}^{n} \to Y^{n}$ with the independent encoder constraint:

I (W_{1}, W_{2}; Y^{n}) \leq I (X_{1}^{n}, X_{2}^{n}; Y^{n}) = i = 1 \sum n I (X_{1, i}, X_{2, i}; Y_{i} ∣ Y^{i - 1}) .

Introduce $Q \sim Uniform {1, \dots, n}$ independent of everything, and define $X_{1} = X_{1, Q}$ , $X_{2} = X_{2, Q}$ , $Y = Y_{Q}$ . Then:

\frac{1}{n} i = 1 \sum n I (X_{1, i}, X_{2, i}; Y_{i} ∣ Y^{i - 1}) = I (X_{1}, X_{2}; Y ∣ Q) .

The product structure $p (x_{1} ∣ q) p (x_{2} ∣ q)$ follows from the independent encoder constraint: $X_{1, i}$ is a function of $W_{1}$ only, $X_{2, i}$ is a function of $W_{2}$ only, and $W_{1} ⊥ W_{2}$ . $□$

Connections Master

46.03.02 — The single-user channel coding theorem is the MAC with one user; the MAC individual bounds reduce to $I (X; Y)$ when the other user is absent.
46.01.02 — Mutual information $I (X_{1}; Y ∣ X_{2})$ and $I (X_{1}, X_{2}; Y)$ define the MAC capacity region boundaries; the chain rule for mutual information decomposes the sum-rate.
46.05.01 — The Slepian-Wolf region is the source-coding dual of the MAC capacity region, with entropy replacing mutual information and inequality directions reversed.
46.06.02 — The broadcast channel is the role-reversal of the MAC: one sender, multiple receivers, with superposition coding as the dual of joint decoding.
46.06.03 — The relay channel contains a MAC sub-problem (relay + source to destination), and the MAC capacity region provides one face of the cut-set bound.
46.03.06 — Feedback does not increase single-user capacity but can enlarge the MAC capacity region, because feedback enables cooperation between users.

Historical & philosophical context Master

Rudolf Ahlswede established the MAC capacity region in "Multi-way Communication Channels" (Proc. 2nd Int. Symp. Information Theory, Tsahkadsor, Armenia, 1971). H. H. J. Liao independently derived the same result in his 1972 dissertation at the University of Hawaii ("Multiple Access Channels"). The Ahlswede-Liao theorem was the first complete characterization of a multi-user channel's capacity region and established the pentagonal structure that has since become the template for all multi-user rate regions.

The proof technique — independently generated codebooks with joint typicality decoding — introduced the paradigm for multi-user achievability proofs. The converse, using Fano's inequality with the independent-encoder constraint, established the method for multi-user converses.

The Gaussian MAC with successive cancellation decoding has become the theoretical foundation for modern multiple-access technologies including CDMA (Code Division Multiple Access), OFDMA (Orthogonal Frequency Division Multiple Access), and non-orthogonal multiple access (NOMA) in 5G cellular systems. The successive cancellation decoder, where one user's signal is decoded first and then subtracted before decoding the next user, is the standard receiver architecture for these systems.

Cover, El Gamal, and Salehi (1980) showed that the MAC capacity region interacts with correlated source coding in a way that breaks the separation theorem, establishing that joint source-channel coding can outperform separate coding in multi-user settings.

Bibliography Master

@inproceedings{ahlswede1971,
  author    = {Ahlswede, R.},
  title     = {Multi-way Communication Channels},
  booktitle = {Proc. 2nd Int. Symp. Information Theory},
  address   = {Tsahkadsor, Armenia},
  year      = {1971},
}
@phdthesis{liao1972,
  author = {Liao, H. H. J.},
  title  = {Multiple Access Channels},
  school = {University of Hawaii},
  year   = {1972},
}
@book{cover-thomas2006,
  author    = {Cover, T. M. and Thomas, J. A.},
  title     = {Elements of Information Theory},
  edition   = {2nd},
  publisher = {Wiley},
  year      = {2006},
}
@book{csiszar-korner2011,
  author    = {Csisz{\'a}r, I. and K{\"o}rner, J.},
  title     = {Information Theory: Coding Theorems for Discrete Memoryless Systems},
  edition   = {2nd},
  publisher = {Cambridge University Press},
  year      = {2011},
}
@article{gaarder-wolf1975,
  author  = {Gaarder, N. T. and Wolf, J. K.},
  title   = {The Capacity Region of a Multiple-Access Discrete Memoryless Channel Can Increase with Feedback},
  journal = {IEEE Transactions on Information Theory},
  volume  = {IT-21},
  pages   = {100--102},
  year    = {1975},
}

Prerequisites

46.03.02
46.01.02

Tier anchors

beginner: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §15.3-15.4 (two senders one receiver, the capacity region as a pentagon, superposition coding in pictures)
intermediate: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §15.3-15.4 (MAC capacity region, random coding achievability, superposition coding, converse via Fano and the MAC version of the data-processing inequality)
master: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §15.3-15.6; Ahlswede 1971 Multi-way Communication Channels; Liao 1972 Multiple Access Channels; Csiszar & Korner 2011 Information Theory: Coding Theorems for Discrete Memoryless Systems 2e (Cambridge) §4.1-4.3

References

Ahlswede, R. — Multi-way Communication Channels · Proc. 2nd Int. Symp. Information Theory (1971) Tsahkadsor, Armenia; the original paper establishing the MAC capacity region as the convex closure of rate pairs satisfying $R_{1} \leq I (X_{1}; Y ∣ X_{2})$ , $R_{2} \leq I (X_{2}; Y ∣ X_{1})$ , $R_{1} + R_{2} \leq I (X_{1}, X_{2}; Y)$ over product input distributions $p (x_{1}) p (x_{2})$ .
Cover, T. M. & Thomas, J. A. — Elements of Information Theory (2nd ed.) · Wiley (2006). Section 15.3: the Gaussian multiple-access channel with capacity region as a pentagon defined by the power constraints. Section 15.3.1: the discrete MAC capacity region, random codebook generation with independent codewords for each user, joint typicality decoding. Section 15.3.2: the converse proof using Fano inequality and the chain rule $I (X_{1}^{n}, X_{2}^{n}; Y^{n}) = I (X_{1}^{n}; Y^{n}) + I (X_{2}^{n}; Y^{n} ∣ X_{1}^{n})$ .
Csiszar, I. & Korner, J. — Information Theory: Coding Theorems for Discrete Memoryless Systems (2nd ed.) · Cambridge University Press (2011). Section 4.1: the MAC capacity region as the convex closure of the union over input distributions. Section 4.2: the achievability proof using independent random codebooks and the packing lemma. Section 4.3: the strong converse for the MAC.

Estimated time

beginner: 20m
intermediate: 50m
master: 100m