Ferkans — Interactive Telecom Tutor

Why We Need More Than Superposition

In Chapter 15, we established the capacity region of the degraded broadcast channel using superposition coding. The degraded structure — where the outputs form a Markov chain $X \to Y_1 \to Y_2$ — is what makes superposition coding sufficient: the "stronger" receiver can always decode everything the "weaker" receiver can, plus more.

But most broadcast channels of practical interest are not degraded. Consider a MIMO broadcast channel where two users have different spatial signatures: neither user's channel is a degraded version of the other's. Or consider a broadcast channel where user 1 observes a noisy version of the even-indexed input symbols and user 2 observes a noisy version of the odd-indexed symbols — there is no degradation ordering at all.

For such channels, we need a more powerful coding technique. The key insight, due to Marton (1979), is to combine superposition coding with binning — the same Gel'fand-Pinsker technique we used for channels with state in Chapter 12. The idea is elegant: generate codebooks for each user and use random binning to create correlation between the codewords destined for different users, even though the encoder does not know the channel state. The "state" that each user's codeword must cope with is, in a sense, the codeword intended for the other user.

Definition:
The General Broadcast Channel

A two-user broadcast channel consists of:

A finite input alphabet $\mathcal{X}$
Two finite output alphabets $\mathcal{Y}_1$ and $\mathcal{Y}_2$
A channel transition probability $P_{Y_1, Y_2 | X}(y_1, y_2 | x)$

The encoder maps a message pair $(m_1, m_2) \in [1:2^{nR_{1}}] \times [1:2^{nR_{2}}]$ to a codeword $x^n(m_1, m_2)$ . Receiver $k$ observes $Y_k^n$ and produces an estimate $\hat{m}_k$ . A rate pair $(R_{1}, R_{2})$ is achievable if the probability of error $P_e^{(n)} = \Pr(\hat{M}_1 \neq M_1 \text{ or } \hat{M}_2 \neq M_2) \to 0$ .

The capacity region $C_{\text{BC}}$ is the closure of the set of achievable rate pairs.

Unlike the degraded BC, we do not assume any ordering between $Y_1$ and $Y_2$ . The general BC is one of the few fundamental multiuser channels whose capacity region remains unknown in full generality.

General broadcast channel

A one-to-many channel where a single encoder communicates independent messages to multiple receivers, with no assumed degradation ordering among the outputs.

Definition:
Marton's Auxiliary Random Variables

For the two-user BC with transition $P_{Y_1, Y_2 | X}$ , introduce:

A common auxiliary $U$ and private auxiliaries $V_1, V_2$
A joint distribution $P_{U, V_1, V_2, X}$ such that: $P_{U, V_1, V_2, X, Y_1, Y_2} = P_{U, V_1, V_2, X} \cdot P_{Y_1, Y_2 | X}$
The encoding function $x = f(u, v_1, v_2)$ that maps the auxiliaries to a channel input

The common message is carried by $U$ , and the private messages for receivers 1 and 2 are carried by $V_1$ and $V_2$ respectively. The key question is how to generate correlated $(V_1, V_2)$ pairs — this is where binning enters.

Theorem: Marton's Inner Bound

For the two-user broadcast channel $P_{Y_1, Y_2 | X}$ , the following rate region is achievable: $R_{1} < I(U, V_1; Y_1)$ $R_{2} < I(U, V_2; Y_2)$ $R_{1} + R_{2} < I(U, V_1; Y_1) + I(U, V_2; Y_2) - I(V_1; V_2 | U)$

where the union is over all joint distributions $P_U P_{V_1, V_2 | U} P_{X | U, V_1, V_2}$ .

Without the common message (i.e., setting $U = \emptyset$ ), the bound simplifies to: $R_{1} < I(V_1; Y_1), \quad R_{2} < I(V_2; Y_2)$ $R_{1} + R_{2} < I(V_1; Y_1) + I(V_2; Y_2) - I(V_1; V_2)$

The sum-rate constraint reflects the "cost" of creating correlation between $V_1$ and $V_2$ through binning. The term $I(V_1; V_2 | U)$ is the binning rate needed to synchronize the two private codebooks. If $V_1$ and $V_2$ were independent (no correlation needed), this cost vanishes and we recover the product of two point-to-point rates. But for non-degraded channels, making $V_1$ and $V_2$ correlated can increase the individual rates $I(V_k; Y_k)$ enough to more than compensate for the binning cost.

Proof

Codebook generation

Fix a joint distribution $P_U P_{V_1, V_2 | U} P_{X | U, V_1, V_2}$ . Generate $2^{nR_{0}}$ i.i.d. codewords $u^n(m_0)$ according to $P_U^n$ . For each $u^n(m_0)$ , generate $2^{n(R_{1} + \tilde{R}_1)}$ conditionally i.i.d. codewords $v_1^n(m_0, m_1, l_1)$ according to $\prod_{i=1}^n P_{V_1|U}(v_{1i}|u_i)$ , indexed by the private message $m_1 \in [1:2^{nR_{1}}]$ and a bin index $l_1 \in [1:2^{n\tilde{R}_1}]$ . Similarly generate $v_2^n(m_0, m_2, l_2)$ from $P_{V_2|U}$ .

Encoding via mutual covering

To send $(m_0, m_1, m_2)$ , the encoder finds a pair $(l_1, l_2)$ such that $(u^n(m_0), v_1^n(m_0, m_1, l_1), v_2^n(m_0, m_2, l_2))$ is jointly typical. By the mutual covering lemma, such a pair exists with high probability provided: $\tilde{R}_1 + \tilde{R}_2 > I(V_1; V_2 | U) + \delta(\epsilon)$ The encoder then transmits $x^n$ generated symbol-by-symbol via $x_i = f(u_i, v_{1i}, v_{2i})$ .

Decoding

Receiver 1 looks for the unique $(\hat{m}_0, \hat{m}_1)$ such that $(u^n(\hat{m}_0), v_1^n(\hat{m}_0, \hat{m}_1, l_1), y_1^n)$ is jointly typical for some $l_1$ . By the packing lemma, this succeeds with high probability if: $R_{1} + \tilde{R}_1 < I(V_1; Y_1 | U)$ $R_{0} + R_{1} + \tilde{R}_1 < I(U, V_1; Y_1)$ Similarly for receiver 2.

Eliminating bin rates via Fourier-Motzkin

The bin rates $\tilde{R}_1, \tilde{R}_2$ are internal to the coding scheme — only $R_{0}, R_{1}, R_{2}$ are operationally meaningful. Applying Fourier-Motzkin elimination to remove $\tilde{R}_1$ and $\tilde{R}_2$ from the system of inequalities yields the rate region in the theorem statement. The sum-rate bound arises because the covering constraint ( $\tilde{R}_1 + \tilde{R}_2$ must be large enough) competes with the packing constraints ( $R_{k} + \tilde{R}_k$ must be small enough).

,

Historical Note: Katalin Marton and the Power of Binning

1979

Katalin Marton published her inner bound for the general broadcast channel in 1979, building on the binning ideas that Gel'fand and Pinsker had developed for channels with state. The remarkable aspect of Marton's construction is that it uses binning not to pre-cancel known interference (as in dirty-paper coding) but to create beneficial correlation between codewords — a fundamentally different use of the same technique.

For over four decades, Marton's inner bound has remained the best known achievable region for the general broadcast channel. Whether it equals the capacity region is one of the major open problems in network information theory. The bound is known to be tight for several important special cases: the degraded BC, the semi-deterministic BC, and the binary-input case (matched by the Nair-El Gamal outer bound).

Random binning

A coding technique where codewords are randomly partitioned into bins. The encoder selects a codeword from a specific bin based on the message and/or side information. Binning creates correlation between sequences without requiring a shared codebook structure.

Mutual covering lemma

A probabilistic lemma guaranteeing that among independently generated codeword pairs $(V_1^n, V_2^n)$ , at least one pair is jointly typical with high probability, provided the product of the codebook sizes exceeds $2^{n I(V_1; V_2)}$ . This is the key tool enabling Marton's binning construction.

Example: Marton's Bound for the Binary Skew-Symmetric BC

Consider a binary broadcast channel where $\mathcal{X} = \mathcal{Y}_1 = \mathcal{Y}_2 = \{0, 1\}$ . The channel to user 1 is a BSC with crossover probability $p_1 = 0.1$ , and the channel to user 2 is a BSC with crossover probability $p_2 = 0.3$ . This channel is degraded ( $p_1 < p_2$ ). Verify that Marton's inner bound recovers the superposition coding capacity region.

Solution

Identify the degraded structure

Since both sub-channels are BSCs with $p_1 < p_2$ , the channel is stochastically degraded: $Y_2$ can be obtained by passing $Y_1$ through an independent BSC with crossover probability $p = (p_2 - p_1)/(1 - 2p_1)$ .

Set Marton's auxiliaries to match superposition

Choose $U = V_2$ (common + user-2 message), $V_1 = X$ (user-1 message encoded directly), and $V_2 \to X$ as the superposition structure. With $V_1 = X$ , we have $I(V_1; V_2) = I(X; U)$ , and the binning cost exactly matches the correlation already present in superposition.

Evaluate the rate region

The Marton bounds become: $R_{1} < I(X; Y_1 | U) = H(Y_1 | U) - H(Y_1 | X) = H(Y_1 | U) - h_b(p_1)$ $R_{2} < I(U; Y_2) = H(Y_2) - H(Y_2 | U)$ where $h_b(\cdot)$ is the binary entropy function. The sum-rate constraint is automatically satisfied (the binning cost is zero because $V_1 = X$ is a function of $U$ and the channel). This matches the superposition coding region of Chapter 15.

When Marton Strictly Outperforms Superposition

For non-degraded channels, Marton's bound can be strictly larger than the superposition coding region. The gain comes from the freedom to choose $(V_1, V_2)$ with a joint distribution that is tailored to the channel, rather than being constrained by the cloud-center/satellite structure. In particular, for the Blackwell channel and certain binary-input channels, the Marton region is known to equal capacity while superposition coding falls short.

Common Mistake: Auxiliary Variable Cardinality Bounds

Mistake:

Assuming that the auxiliary random variables $(U, V_1, V_2)$ in Marton's bound require alphabets as large as the input or output alphabets.

Correction:

By the support lemma (Carath'{e}odory-type argument), the cardinality of $U$ can be bounded by $|\mathcal{X}| + 4$ , and $|V_k|$ by $|\mathcal{X}| + 2$ . These bounds make the optimization over auxiliary distributions finite-dimensional, though still non-convex and computationally challenging.

Quick Check

In Marton's inner bound (without common message), the sum-rate constraint is $R_{1} + R_{2} < I(V_1; Y_1) + I(V_2; Y_2) - I(V_1; V_2)$ . What does the term $I(V_1; V_2)$ represent?

The rate penalty due to binning — the cost of correlating the two private codewords

The capacity of the channel between receiver 1 and receiver 2

The rate at which the common message is transmitted

Correction:

The rate penalty due to binning — the cost of correlating the two private codewords

The mutual covering lemma requires the bin sizes to satisfy $\tilde{R}_1 + \tilde{R}_2 > I(V_1; V_2)$ , which consumes rate that could otherwise carry information.

Marton's Binning Construction

Animated walkthrough of Marton's codebook construction: two independently generated codebooks are partitioned into bins, and a jointly typical pair is found via the mutual covering lemma. The binning cost

I(V_1; V_2)

is visualized.

Key Takeaway

Marton's inner bound extends the broadcast channel achievable region beyond superposition coding by using binning to correlate the codewords for different receivers. The binning cost $I(V_1; V_2 | U)$ is the price paid for this correlation, and the art of applying Marton's bound lies in choosing the joint distribution of $(U, V_1, V_2, X)$ that balances this cost against the gains in individual rates.

Marton's Coding Scheme

Why We Need More Than Superposition

Definition: The General Broadcast Channel

General broadcast channel

Definition: Marton's Auxiliary Random Variables

Theorem: Marton's Inner Bound

Codebook generation

Encoding via mutual covering

Decoding

Eliminating bin rates via Fourier-Motzkin

Historical Note: Katalin Marton and the Power of Binning

Random binning

Mutual covering lemma

Example: Marton's Bound for the Binary Skew-Symmetric BC

Identify the degraded structure

Set Marton's auxiliaries to match superposition

Evaluate the rate region

When Marton Strictly Outperforms Superposition

Common Mistake: Auxiliary Variable Cardinality Bounds

Quick Check

Marton's Binning Construction

Key Takeaway

Definition:
The General Broadcast Channel

Definition:
Marton's Auxiliary Random Variables