46.06.02 · information-theory / network-information

Broadcast Channel: Degraded Broadcast Capacity and Marton's Inner Bound

shipped3 tiersLean: none

Anchor (Master): Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §15.6-15.7; Bergmans 1973 Random coding theorem for broadcast channels with degraded message sets; Gallager 1974 Capacity and coding for degraded broadcast channels; Marton 1979 A coding theorem for the discrete memoryless broadcast channel; El Gamal & Kim 2011 Network Information Theory Ch. 8

Intuition Beginner

A television tower broadcasts a signal. Some viewers have rooftop antennas (good reception) and others have indoor antennas (poor reception). The tower wants to send different programs to each group. How should it encode the signal?

This is the broadcast channel: one transmitter, multiple receivers with different channel qualities. The transmitter must design a single signal that carries information for all receivers simultaneously.

The key insight is superposition coding. The transmitter sends a "cloud center" codeword that carries the message for the worse receiver. Embedded within each cloud is a "satellite" codeword that carries the additional message for the better receiver. The worse receiver can decode the cloud center but not the satellite (its channel is too noisy). The better receiver can decode both.

Think of it as a two-layer cake. The base layer is coarse information that everyone can receive. The top layer is fine-grained information that only the best receivers can access. The transmitter builds both layers into a single signal, and each receiver extracts what its channel quality allows.

For the degraded broadcast channel — where one receiver's channel is a degraded version of the other's — the capacity region is known exactly. It is achieved by superposition coding, and the converse follows from the degradedness condition.

For the general (non-degraded) broadcast channel, the capacity region is not fully known. Marton's inner bound, based on binning correlated auxiliary codewords, is the best known achievable region, but no matching outer bound has been proved.

Visual Beginner

Figure: superposition coding. A grid of "cloud center" codewords $U^{n} (w_{2})$ , each surrounded by a cluster of "satellite" codewords $X^{n} (w_{1}, w_{2})$ . The worse receiver decodes the cloud center $w_{2}$ . The better receiver decodes both $w_{2}$ and the satellite index $w_{1}$ .

Component	Encoding	Decoded by worse RX?	Decoded by better RX?
Cloud center $U^{n} (w_{2})$	Base-layer message	Yes	Yes
Satellite $X^{n} (w_{1}, w_{2})$	Enhancement-layer message	No (too noisy)	Yes

Worked example Beginner

A binary broadcast channel: the transmitter sends $X \in {0, 1}$ . Receiver 1 sees $Y_{1} = X$ through a BSC with crossover probability 0.1 (good channel). Receiver 2 sees $Y_{2}$ which is $Y_{1}$ through an additional BSC with crossover probability 0.2 (degraded worse channel).

The degradedness: $Y_{2}$ is a noisier version of $Y_{1}$ . The effective channel to receiver 2 is a BSC with crossover $0.1 * 0.2 = 0.1 (1 - 0.2) + 0.2 (1 - 0.1) = 0.08 + 0.18 = 0.26$ .

Superposition coding: the transmitter chooses an auxiliary $U$ (cloud center) at rate $R_{2}$ for receiver 2, and a refinement $X$ (satellite) at rate $R_{1}$ for receiver 1. The achievable rates satisfy $R_{2} \leq I (U; Y_{2})$ and $R_{1} \leq I (X; Y_{1} ∣ U)$ .

At one extreme: send only to receiver 1 at rate $C_{1} = 1 - H (0.1) \approx 0.531$ bits/use. At the other: send only to receiver 2 at rate $C_{2} = 1 - H (0.26) \approx 0.173$ bits/use. The trade-off: more rate to one receiver means less to the other.

Check your understanding Beginner

Formal definition Intermediate+

A two-user discrete memoryless broadcast channel has input alphabet $X$ , output alphabets $Y_{1}, Y_{2}$ , and transition probabilities $p (y_{1}, y_{2} ∣ x)$ .

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

An encoder $f : {1, \dots, 2^{n R_{1}}} \times {1, \dots, 2^{n R_{2}}} \to X^{n}$ mapping the message pair to a channel input.
Two decoders: $g_{1} : Y_{1}^{n} \to {1, \dots, 2^{n R_{1}}}$ and $g_{2} : Y_{2}^{n} \to {1, \dots, 2^{n R_{2}}}$ .

Definition (Degraded broadcast channel). A broadcast channel is degraded if there exists a channel $p (y_{2} ∣ y_{1})$ such that $p (y_{1}, y_{2} ∣ x) = p (y_{1} ∣ x) p (y_{2} ∣ y_{1})$ . Physically: $Y_{2}$ is a noisy version of $Y_{1}$ .

Theorem (Bergmans 1973, Gallager 1974). The capacity region of the degraded broadcast channel $X \to Y_{1} \to Y_{2}$ is:

C = p (u) p (x ∣ u) ⋃ {(R_{1}, R_{2}) : R_{1} \leq I (X; Y_{1} ∣ U), R_{2} \leq I (U; Y_{2})} .

Key theorem with proof Intermediate+

Theorem (Degraded broadcast achievability). The superposition coding rate region is achievable.

Proof. Codebook. Fix $p (u)$ and $p (x ∣ u)$ . Generate $2^{n R_{2}}$ cloud center codewords $U^{n} (w_{2})$ by drawing i.i.d. from $p (u)$ . For each $w_{2}$ , generate $2^{n R_{1}}$ satellite codewords $X^{n} (w_{1}, w_{2})$ by drawing i.i.d. from $p (x ∣ u)$ for each position, conditioned on $U^{n} (w_{2})$ .

Encoding. To send messages $(w_{1}, w_{2})$ , transmit $X^{n} (w_{1}, w_{2})$ .

Decoder 2 (worse receiver). Find $\tilde{w}_{2}$ such that $(U^{n} (\tilde{w}_{2}), Y_{2}^{n}) \in T_{ϵ}^{(n)}$ . This succeeds with high probability if $R_{2} < I (U; Y_{2})$ .

Decoder 1 (better receiver). Find $(\tilde{w}_{1}, \tilde{w}_{2})$ such that $(U^{n} (\tilde{w}_{2}), X^{n} (\tilde{w}_{1}, \tilde{w}_{2}), Y_{1}^{n}) \in T_{ϵ}^{(n)}$ . This succeeds if $R_{1} + R_{2} < I (X; Y_{1})$ (sum-rate) and $R_{2} < I (U; Y_{1})$ (identify the correct cloud). Since $Y_{1}$ is better than $Y_{2}$ , $I (U; Y_{1}) \geq I (U; Y_{2})$ , so the binding constraint for the cloud is the worse receiver's: $R_{2} < I (U; Y_{2})$ .

The net rate for receiver 1 is $R_{1} < I (X; Y_{1} ∣ U) = I (X; Y_{1}) - I (U; Y_{1})$ . Combined with $R_{2} < I (U; Y_{2})$ , this gives the achievable region. $□$

Bridge. The broadcast channel capacity region builds toward the relay channel 46.06.03 by providing the downlink component: the source-to-relay-and-destination link is a broadcast channel, and its capacity region constrains how much information can reach both nodes simultaneously. The result appears again in the interference channel 46.06.04 where dirty-paper coding strategies from the broadcast channel are applied at each transmitter to pre-cancel cross-interference. The foundational reason superposition coding works is that the degradedness condition $X \to Y_{1} \to Y_{2}$ ensures the worse receiver's optimal strategy (decode the cloud center) is a subset of the better receiver's strategy (decode cloud and satellite). This is exactly the nesting property that makes the achievable region tight: the converse uses the degradedness to establish that no other coding scheme can improve on superposition. Putting these together, the broadcast channel is the dual of the multiple-access channel 46.06.01 and the central insight is that layered encoding matches the layered channel quality, with each receiver extracting the layers its channel can support.

Exercises Intermediate+

Exercise (medium, short answer).

Describe Marton's inner bound for the general (non-degraded) broadcast channel. How does it differ from superposition coding?

Hint

Marton uses correlated auxiliary codewords with binning, not layered superposition.

Answer

Marton's inner bound uses two auxiliary random variables $(U, V)$ with joint distribution $p (u, v)$ and a stochastic encoder $p (x ∣ u, v)$ . The achievable rates are $R_{1} \leq I (U; Y_{1})$ and $R_{2} \leq I (V; Y_{2})$ subject to the binning constraint $I (U; V) \leq I (U, V; X)$ . Unlike superposition coding (which uses nested codewords $U \subset X$ ), Marton's scheme uses correlated codewords $U^{n}$ and $V^{n}$ that are jointly generated but decoded independently by each receiver. The binning constraint ensures the encoder can find a pair of codewords compatible with the channel input. Marton's bound is strictly larger than superposition for non-degraded channels.

Exercise (medium, short answer).

Prove the converse for the degraded broadcast channel: $R_{1} \leq I (X; Y_{1} ∣ U)$ and $R_{2} \leq I (U; Y_{2})$ for some $p (u) p (x ∣ u)$ .

Hint

Define $U_{i} = (W_{2}, Y_{1, i + 1}^{n})$ and use Fano's inequality with the degradedness condition.

Answer

By Fano's inequality, $H (W_{2} ∣ Y_{2}^{n}) \leq n ϵ_{n}$ and $H (W_{1} ∣ Y_{1}^{n}, W_{2}) \leq n ϵ_{n}$ . Define $U_{i} = (W_{2}, Y_{1, i + 1}^{n})$ . For receiver 2: $n R_{2} \leq I (W_{2}; Y_{2}^{n}) + n ϵ_{n} = \sum_{i} I (W_{2}; Y_{2, i} ∣ Y_{2}^{i - 1}) + n ϵ_{n} \leq \sum_{i} I (W_{2}, Y_{1, i + 1}^{n}, Y_{2}^{i - 1}; Y_{2, i}) + n ϵ_{n}$ . By degradedness $X \to Y_{1} \to Y_{2}$ , $I (U_{i}, Y_{1}^{i - 1}; Y_{2, i}) \leq I (U_{i}; Y_{2, i})$ (since $Y_{2}$ depends on $Y_{1}$ which depends on $X$ ). Single-letterizing with $Q$ : $R_{2} \leq I (U; Y_{2} ∣ Q)$ .

For receiver 1: $n R_{1} \leq I (W_{1}; Y_{1}^{n} ∣ W_{2}) + n ϵ_{n}$ . By the chain rule and the Markov structure: $I (W_{1}; Y_{1}^{n} ∣ W_{2}) = \sum_{i} I (W_{1}; Y_{1, i} ∣ Y_{1}^{i - 1}, W_{2})$ . With $U_{i}$ defined as above: $R_{1} \leq I (X; Y_{1} ∣ U, Q)$ after single-letterization.

Exercise (medium, numeric).

A Gaussian broadcast channel has $Y_{1} = X + Z_{1}$ and $Y_{2} = X + Z_{2}$ where $Z_{1} \sim N (0, 1)$ , $Z_{2} \sim N (0, 10)$ , and $E [X^{2}] \leq P = 20$ . Compute the sum-rate capacity using superposition coding.

Hint

The Gaussian broadcast channel is degraded since $Z_{2}$ has more noise. Use superposition: $X = U + V$ with power split $α P$ for $U$ and $(1 - α) P$ for $V$ .

Answer

Treat $Y_{2}$ as the worse receiver (more noise). $X = U + V$ where $U$ (cloud center) has power $α P$ and $V$ (satellite) has power $(1 - α) P$ .

Receiver 2 sees $Y_{2} = U + V + Z_{2}$ . It decodes $U$ treating $V$ as noise: $R_{2} \leq \frac{1}{2} lo g (1 + α P / ((1 - α) P + 10))$ .

Receiver 1 sees $Y_{1} = U + V + Z_{1}$ . It decodes $U$ first (subtract), then $V$ : $R_{1} \leq \frac{1}{2} lo g (1 + (1 - α) P /1)$ .

Sum-rate: $R_{1} + R_{2} = \frac{1}{2} lo g (1 + (1 - α) \cdot 20) + \frac{1}{2} lo g (1 + α \cdot 20/ ((1 - α) \cdot 20 + 10))$ .

At $α = 0.5$ : $R_{1} = \frac{1}{2} lo g (1 + 10) \approx 1.73$ bits, $R_{2} = \frac{1}{2} lo g (1 + 10/20) \approx 0.39$ bits. Sum $\approx 2.12$ bits/use.

Exercise (hard, short answer).

Show that dirty-paper coding achieves the Gaussian broadcast channel capacity region.

Hint

Encode the message for the stronger receiver using DPC against the interference from the weaker receiver's signal.

Answer

For the Gaussian broadcast channel $Y_{1} = X + Z_{1}$ , $Y_{2} = X + Z_{2}$ with $Var (Z_{1}) < Var (Z_{2})$ , use Costa's dirty-paper coding: encode the message for receiver 1 (stronger) using the auxiliary variable $U_{1} = V_{1} + α V_{2}$ where $V_{1}$ is receiver 1's signal and $V_{2}$ is receiver 2's signal (known interference). The DPC encoding makes $V_{1}$ invisible to receiver 2 (it only sees $V_{2}$ plus noise), while receiver 1 can decode both. The resulting rates are $R_{1} = \frac{1}{2} lo g (1 + P_{1} / N_{1})$ and $R_{2} = \frac{1}{2} lo g (1 + P_{2} / (P_{1} + N_{2}))$ for some power split $P_{1} + P_{2} \leq P$ , which matches the superposition coding region and is optimal for the degraded Gaussian broadcast channel.

Exercise (hard, short answer).

Prove Marton's inner bound: the rate region ${R_{1} \leq I (U; Y_{1}), R_{2} \leq I (V; Y_{2})}$ subject to $I (U; V) \leq I (U, V; X)$ is achievable for the general broadcast channel.

Hint

Generate correlated codeword pairs $(U^{n}, V^{n})$ and bin them by the channel input $X^{n}$ .

Answer

Generate $2^{n (I (U; V) + ϵ)}$ codeword pairs $(U^{n} (j), V^{n} (j))$ jointly from $p (u, v)$ . Randomly partition them into $2^{n R_{1}}$ bins for receiver 1 and $2^{n R_{2}}$ bins for receiver 2. The encoder finds a pair $(j)$ such that $U^{n} (j)$ is in the desired bin for receiver 1, $V^{n} (j)$ is in the desired bin for receiver 2, and generates $X^{n}$ via $p (x ∣ u^{n} (j), v^{n} (j))$ . This is possible when the total number of codeword pairs exceeds the rate cost of binning: $I (U; V) + ϵ \geq R_{1} + R_{2} - I (U; V) + \dots$ — the condition simplifies to the encoding constraint that the pair is compatible with the channel input. The binning condition $I (U; V) \leq I (U, V; X)$ ensures the encoder can find such a pair. Each receiver decodes its auxiliary codeword from its channel output: receiver 1 finds $U^{n}$ jointly typical with $Y_{1}^{n}$ (succeeds when $R_{1} \leq I (U; Y_{1})$ ), and receiver 2 finds $V^{n}$ jointly typical with $Y_{2}^{n}$ (succeeds when $R_{2} \leq I (V; Y_{2})$ ).

Exercise (hard, short answer).

Give an example of a non-degraded broadcast channel where Marton's inner bound strictly exceeds the superposition coding region.

Hint

Consider a broadcast channel where the two outputs are not ordered by degradedness.

Answer

The binary symmetric broadcast channel (BS-BSC) with crossover probabilities $p_{1}$ and $p_{2}$ where $p_{1} \neq = p_{2}$ and neither is a degraded version of the other (i.e., $p_{1} * q \neq = p_{2}$ for any $q$ ). In this case, the channel is not degraded, and superposition coding gives a suboptimal region because it assumes one receiver is strictly better. Marton's bound, using correlated auxiliary codewords, achieves higher rates by allowing both receivers to decode from non-nested codebooks. For the specific case of the Blackwell channel (deterministic broadcast channel with $X \in {0, 1, 2}$ , $Y_{1} = 1 [X \neq = 0]$ , $Y_{2} = 1 [X \neq = 2]$ ), Marton's bound gives a strictly larger region than time-sharing between the two point-to-point capacities.

Lean formalization Intermediate+

Mathlib does not define broadcast channels, superposition coding, or Marton's inner bound. The degraded broadcast capacity region requires layered codebook structures and the degradedness condition for the converse. Marton's inner bound involves correlated auxiliary variables with binning constraints. None of this is formalized. This unit ships without formalization.

Advanced results Master

The Gaussian broadcast channel

The two-user Gaussian broadcast channel $Y_{1} = X + Z_{1}$ , $Y_{2} = X + Z_{2}$ with $Var (Z_{1}) = N_{1} < N_{2} = Var (Z_{2})$ is degraded. The capacity region is:

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

for some $α \in [0, 1]$ . The parameter $α$ splits the power: fraction $α P$ for the cloud center (receiver 2's message) and $(1 - α) P$ for the satellite (receiver 1's additional message). The sum-rate is maximized by choosing $α$ to balance the two rates.

This extends to $K$ users by successive refinement: the transmitter splits power into $K$ layers, and each receiver decodes all layers up to its channel quality.

The capacity region for more than two receivers

For the $K$ -user degraded broadcast channel $X \to Y_{1} \to Y_{2} \to \dots \to Y_{K}$ , the capacity region is:

R_{k} \leq I (U_{k}; Y_{k} ∣ U_{k + 1}), k = 1, \dots, K,

where $U_{1} = X$ , $U_{K + 1} = \emptyset$ , and $U_{1} \to U_{2} \to \dots \to U_{K}$ forms a Markov chain. Each $U_{k}$ carries the message for receiver $k$ , and the layered structure ensures each receiver can decode all layers above it.

For non-degraded broadcast channels with more than two receivers, even Marton's inner bound is difficult to compute, and the gap between inner and outer bounds grows with $K$ .

The broadcast channel with common and private messages

The broadcast channel can carry both common messages (decoded by all receivers) and private messages (decoded by individual receivers). The capacity region for the degraded case with common message $W_{0}$ and private messages $W_{1}, W_{2}$ is:

R_{0} + R_{2} \leq I (U; Y_{2}), R_{1} \leq I (X; Y_{1} ∣ U) .

The common message is encoded in the cloud center, and the private message for receiver 1 is encoded in the satellite. This model captures the scenario where some information must be received by all users (e.g., emergency broadcasts) while other information is user-specific.

Synthesis. The broadcast channel is the dual of the multiple-access channel 46.06.01: one sender to multiple receivers instead of multiple senders to one receiver. The central insight is that superposition coding matches the layered quality structure of degraded channels, with each receiver extracting the layers its channel can support. For the degraded case, the Bergmans-Gallager theorem establishes the exact capacity region via superposition coding with a matching converse that uses the degradedness condition. For the general case, Marton's inner bound using correlated auxiliary codewords with binning provides the best known achievable region, and the foundational reason it exceeds superposition is that correlated (rather than nested) codebooks can exploit the specific structure of non-degraded channels. The result builds toward the relay channel 46.06.03 where the broadcast component constrains information flow, and the interference channel 46.06.04 where dirty-paper coding from the broadcast setting manages cross-interference. Putting these together, the broadcast channel capacity region is the second major multi-user rate region (after the MAC) and the interplay between superposition coding and Marton's binning illustrates the transition from known to unknown capacity regions in network information theory.

Full proof set Master

Proposition (Degraded broadcast converse). For the degraded broadcast channel $X \to Y_{1} \to Y_{2}$ , any achievable rate pair satisfies $R_{2} \leq I (U; Y_{2})$ and $R_{1} \leq I (X; Y_{1} ∣ U)$ for some $p (u) p (x ∣ u)$ .

Proof. Define $U_{i} = (W_{2}, Y_{1, i + 1}^{n})$ . By Fano's inequality:

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

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

By degradedness, $Y_{2, i}$ depends on $Y_{1, i}$ which depends on $X_{i}$ . Csiszar's identity gives:

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

Single-letterize with $Q$ uniform on ${1, \dots, n}$ : $R_{2} \leq I (U; Y_{2} ∣ Q)$ where $U = U_{Q}$ .

For $R_{1}$ : $n R_{1} \leq I (W_{1}; Y_{1}^{n} ∣ W_{2}) + n ϵ_{n}$ . By the Markov chain $W_{1} \to X^{n} \to Y_{1}^{n}$ and the independence $W_{1} ⊥ W_{2}$ :

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

Single-letterize: $R_{1} \leq I (X; Y_{1} ∣ U, Q)$ . $□$

Connections Master

46.06.01 — The broadcast channel is the dual of the MAC: one sender to many receivers versus many senders to one receiver. The capacity regions have complementary structures.
46.03.01 — The point-to-point channel capacity is the broadcast channel with one receiver; superposition reduces to standard channel coding.
46.05.03 — Dirty-paper coding achieves the Gaussian broadcast channel capacity, using the Gelfand-Pinsker binning technique to pre-cancel interference between users.
46.06.03 — The relay channel has a broadcast sub-component (source to relay and destination) whose capacity constrains the overall achievable rate.
46.06.04 — The interference channel uses broadcast-like strategies at each transmitter; the Han-Kobayashi bound combines rate-splitting with dirty-paper coding.

Historical & philosophical context Master

Tom Cover introduced the broadcast channel in "Broadcast Channels" (IEEE Trans. IT-18, 1972, 2-14). Cover conjectured the superposition coding region for the degraded case and posed the general capacity problem. The degraded case was resolved by Bergmans (1973) for achievability and Gallager (1974) for the converse, establishing the superposition coding region as tight.

Katalin Marton established the best known inner bound for the general broadcast channel in "A Coding Theorem for the Discrete Memoryless Broadcast Channel" (IEEE Trans. IT-25, 1979, 306-311). Marton's bound uses correlated auxiliary codewords with binning and remains unimproved after more than four decades, making the general broadcast channel capacity one of the longest-standing open problems in network information theory.

The Gaussian broadcast channel was resolved by Bergmans (1974) and Cover (1972), who showed that superposition coding with power splitting achieves the capacity region. The extension to MIMO broadcast channels via dirty-paper coding was completed by Yu and Cioffi (2004) and Weingarten, Steinberg, and Shamai (2006), establishing DPC as the capacity-achieving strategy.

El Gamal and Kim's 2011 textbook Network Information Theory (Cambridge) provides the definitive treatment, with the broadcast channel occupying an entire chapter.

Bibliography Master

@article{cover1972,
  author  = {Cover, T. M.},
  title   = {Broadcast Channels},
  journal = {IEEE Transactions on Information Theory},
  volume  = {IT-18},
  pages   = {2--14},
  year    = {1972},
}
@article{bergmans1973,
  author  = {Bergmans, P. P.},
  title   = {Random Coding Theorem for Broadcast Channels with Degraded Message Sets},
  journal = {IEEE Transactions on Information Theory},
  volume  = {IT-19},
  pages   = {197--207},
  year    = {1973},
}
@article{marton1979,
  author  = {Marton, K.},
  title   = {A Coding Theorem for the Discrete Memoryless Broadcast Channel},
  journal = {IEEE Transactions on Information Theory},
  volume  = {IT-25},
  pages   = {306--311},
  year    = {1979},
}
@book{cover-thomas2006,
  author    = {Cover, T. M. and Thomas, J. A.},
  title     = {Elements of Information Theory},
  edition   = {2nd},
  publisher = {Wiley},
  year      = {2006},
}
@book{elgamal-kim2011,
  author    = {El Gamal, A. and Kim, Y.-H.},
  title     = {Network Information Theory},
  publisher = {Cambridge University Press},
  year      = {2011},
}

Prerequisites

46.06.01
46.03.01

Tier anchors

beginner: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §15.6 (one transmitter sending to multiple receivers, superposition coding for the degraded broadcast channel)
intermediate: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §15.6 (degraded broadcast channel capacity, superposition coding, converse, Marton's inner bound for the general broadcast channel)
master: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §15.6-15.7; Bergmans 1973 Random coding theorem for broadcast channels with degraded message sets; Gallager 1974 Capacity and coding for degraded broadcast channels; Marton 1979 A coding theorem for the discrete memoryless broadcast channel; El Gamal & Kim 2011 Network Information Theory Ch. 8

References

Cover, T. M. — Broadcast Channels · IEEE Transactions on Information Theory IT-18(1) (1972) 2-14; the paper that introduced the broadcast channel problem and conjectured the superposition coding region for the degraded case. Cover proposed that the capacity region is the convex closure of rate pairs satisfying $R_{1} \leq I (X; Y_{1} ∣ U)$ and $R_{2} \leq I (U; Y_{2})$ for auxiliary variable $U$ , with $X$ as a function of $(U, V)$ carrying both messages.
Bergmans, P. P. — Random Coding Theorem for Broadcast Channels with Degraded Message Sets · IEEE Transactions on Information Theory IT-19(2) (1973) 197-207; proved the achievability of superposition coding for degraded broadcast channels via random coding, establishing that the Cover rate region is achievable.
Marton, K. — A Coding Theorem for the Discrete Memoryless Broadcast Channel · IEEE Transactions on Information Theory IT-25(3) (1979) 306-311; introduced Marton inner bound for general (non-degraded) broadcast channels using random binning of correlated auxiliary codewords: the region defined by $R_{1} \leq I (U; Y_{1})$ and $R_{2} \leq I (V; Y_{2})$ subject to $I (U; V) \leq I (U, V; X)$ . This remains the best known inner bound.
Cover, T. M. & Thomas, J. A. — Elements of Information Theory (2nd ed.) · Wiley (2006). Section 15.6: the degraded broadcast channel, superposition coding achievability (auxiliary cloud centers for the worse receiver, satellite codewords for the better receiver), the converse using conditional mutual information. Section 15.6.2: the Gaussian broadcast channel and its capacity region via dirty-paper coding.

Estimated time

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