46.05.03 · information-theory / side-information

Gelfand-Pinsker and Costa's Dirty-Paper Coding

shipped3 tiersLean: none

Anchor (Master): Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §7.6; Gelfand & Pinsker 1980 Capacity of a broadcast channel with one deterministic component; Costa 1983 Writing on Dirty Paper; Csiszar & Korner 2011 Information Theory: Coding Theorems for Discrete Memoryless Systems 2e (Cambridge) §7.3

Intuition Beginner

Someone hands you a piece of paper covered in random scribbles and asks you to write a legible message on it. The scribbles are interference — they corrupt whatever you write. But there is a catch: you can see the scribbles before you write. You know exactly where every mark is.

Costa called this "writing on dirty paper." The result is stunning: if you know the interference ahead of time, you can pre-cancel it and write as if the paper were clean. The capacity is the same as if the interference did not exist.

How? You write your message in a way that is mathematically orthogonal to the scribbles. The receiver sees your message plus the scribbles plus new noise, but because your encoding is correlated with the known scribbles in a specific way, the decoder can extract your message without the scribbles causing any degradation.

The key mathematical trick is binning. You have a large codebook of auxiliary codewords. For each interference pattern, you pick a codeword from the bin that is "compatible" with that interference. The bin structure ensures that the decoder can identify both the interference and your message from the received signal.

This is different from feedback (where you learn past outputs). Here you learn the future interference before transmitting. It is also different from simply subtracting the interference, because you have a power constraint — you cannot transmit infinite power to overwhelm it.

The result has revolutionized wireless communications. In MIMO (multiple-input multiple-output) systems, the transmitter often knows the channel state, which acts like known interference. Dirty-paper coding achieves the full MIMO capacity by pre-canceling the known channel effects.

Visual Beginner

Figure: three versions of a Gaussian channel. Left: clean channel $Y = X + Z$ . Center: dirty channel $Y = X + S + Z$ with unknown interference $S$ . Right: dirty channel with known $S$ at transmitter, using dirty-paper coding to achieve the clean-channel capacity.

Scenario	Interference known?	Capacity
Clean channel ( $Y = X + Z$ )	No interference	$\frac{1}{2} lo g (1 + P / N)$
Dirty channel, $S$ unknown	No	Reduced (interference hurts)
Dirty channel, $S$ known at TX	Yes, non-causally	$\frac{1}{2} lo g (1 + P / N)$ (same as clean!)

The capacity with known interference equals the capacity without interference. The transmitter "writes around" the dirt.

Worked example Beginner

A Gaussian channel has $Y = X + S + Z$ where the transmitter power constraint is $P = 10$ , the noise variance is $N = 1$ , and the interference $S$ has variance $Q = 100$ .

Without knowing $S$ : the interference acts as additional noise, and the effective noise variance is $Q + N = 101$ . Capacity $= \frac{1}{2} lo g_{2} (1 + 10/101) \approx 0.16$ bits per channel use.

With $S$ known at the transmitter (dirty-paper coding): the capacity equals $\frac{1}{2} lo g_{2} (1 + 10/1) \approx 1.73$ bits per channel use — the same as if $S$ did not exist. The tenfold increase comes from pre-canceling the strong interference.

The encoder uses $U = X + α S$ with $α = P / (P + N) = 10/11 \approx 0.91$ . The codeword $U^{n}$ carries the message. The actual channel input is $X = U - α S$ , which satisfies the power constraint. The receiver sees $Y = U - α S + S + Z = U + (1 - α) S + Z$ . Since $U$ is designed to be independent of $S$ , the decoder can recover $U$ (and hence the message) with the same performance as a clean channel.

Check your understanding Beginner

Formal definition Intermediate+

A channel with state has transition probabilities $p (y ∣ x, s)$ where $S \sim p (s)$ is the channel state, $X$ is the input, and $Y$ is the output. The state sequence $S^{n}$ is i.i.d. from $p (s)$ .

Definition (Code with non-causal state information). A $(2^{n R}, n)$ code with non-causal state information at the encoder consists of:

An encoder $f : {1, \dots, 2^{n R}} \times S^{n} \to X^{n}$ mapping the message $W$ and the state sequence $S^{n}$ to the channel input $X^{n}$ .
A decoder $g : Y^{n} \to {1, \dots, 2^{n R}}$ mapping the output to a message estimate.

The encoder knows the entire state sequence before encoding (non-causal knowledge).

Theorem (Gelfand-Pinsker 1980). The capacity of a channel with state $S \sim p (s)$ known non-causally at the transmitter is:

C_{GP} = p (u ∣ x, s), x (u, s) max [I (U; Y) - I (U; S)],

where the maximum is over all auxiliary random variables $U$ and encoding functions $x (u, s)$ such that $U \to (X, S) \to Y$ forms a Markov chain.

Theorem (Costa 1983, Dirty-paper coding). For the Gaussian channel $Y = X + S + Z$ where $S \sim N (0, Q)$ is known at the transmitter, $Z \sim N (0, N)$ is unknown noise, and $E [X^{2}] \leq P$ :

C_{D P C} = \frac{1}{2} lo g (1 + \frac{P}{N}) .

The interference $S$ causes no rate loss.

Key theorem with proof Intermediate+

Theorem (Gelfand-Pinsker achievability). The rate $R = I (U; Y) - I (U; S) - ϵ$ is achievable for any distribution $p (u ∣ x, s)$ and encoding function $x (u, s)$ .

Proof (random binning).

Codebook generation. Generate $2^{n (I (U; S) + ϵ)}$ codewords $U^{n} (j)$ for $j = 1, \dots, 2^{n (I (U; S) + ϵ)}$ by drawing each symbol i.i.d. from $p (u)$ . Randomly partition the codewords into $2^{n R}$ bins of size $2^{n (I (U; S) + ϵ - R)}$ . Label the bins by message index $w$ .

Encoding. Given message $w$ and state sequence $S^{n}$ :

Look in bin $w$ for a codeword $U^{n} (j)$ that is jointly typical with $S^{n}$ . Since each bin has $2^{n (I (U; S) + ϵ - R)}$ codewords, and there are $2^{n (I (U; S) - δ)}$ sequences in the jointly typical set, a typical codeword exists in the bin with high probability provided $I (U; S) + ϵ - R \geq I (U; S)$ , i.e., $R \leq ϵ$ — this needs adjustment. The correct analysis: the total number of codewords is $2^{n (I (U; S) + ϵ)}$ and the number of jointly typical pairs is $2^{n H (U, S)}$ . A codeword in bin $w$ is jointly typical with $S^{n}$ with probability $\approx 2^{- n (I (U; S) - δ)}$ , so a bin of size $2^{n (I (U; S) - R + ϵ)}$ contains a jointly typical codeword with high probability.
Transmit $X_{i} = x (U_{i}, S_{i})$ for $i = 1, \dots, n$ .

Decoding. The decoder looks for the unique codeword $U^{n} (\tilde{j})$ jointly typical with $Y^{n}$ . Since there are $2^{n (I (U; S) + ϵ)}$ codewords, the probability of confusion is $\approx 2^{n (I (U; S) + ϵ)} \cdot 2^{- n I (U; Y)} = 2^{- n (I (U; Y) - I (U; S) - ϵ)}$ , which vanishes when $R < I (U; Y) - I (U; S)$ .

Rate. The encoder uses $R = I (U; Y) - I (U; S) - ϵ$ bits per channel use. $□$

Bridge. The Gelfand-Pinsker theorem builds toward the entire class of "writing on dirty paper" results by introducing the auxiliary-variable binning technique that pre-cancels known interference. This is exactly the same binning structure that appears in Slepian-Wolf 46.05.01 and Wyner-Ziv 46.05.02, but applied in the channel coding direction: the encoder bins auxiliary codewords by their compatibility with the known state sequence. The result appears again in the broadcast channel 46.06.02 through Marton's inner bound, where the transmitter bins codewords for one receiver conditioned on the "interference" created by the other receiver's message. The foundational reason dirty-paper coding works is that the rate penalty $I (U; S)$ for making the codeword compatible with the state is exactly compensated by the rate gain $I (U; Y)$ from the decoder's ability to identify the correct codeword — for the Gaussian case with the optimal $α$ , these terms balance perfectly, yielding zero net penalty. Putting these together, the central insight is that non-causal transmitter side information is a fundamentally different resource than causal feedback: knowing the future interference allows pre-cancellation at no asymptotic rate cost for the Gaussian channel, while knowing past outputs (feedback) provides no rate gain at all for the memoryless channel.

Exercises Intermediate+

Exercise (medium, short answer).

Explain the role of the auxiliary variable $U$ in the Gelfand-Pinsker formula. Why is it needed instead of directly choosing $X$ based on $S$ ?

Hint

$U$ carries the message and is correlated with $S$ in a controlled way that the decoder can untangle.

Answer

The auxiliary variable $U$ serves as a "message carrier" that is designed to be jointly typical with $S$ (at the encoder) and jointly typical with $Y$ (at the decoder). The rate penalty $I (U; S)$ is the cost of making $U$ compatible with the state, and the rate gain $I (U; Y)$ is the information the decoder extracts. Using $X$ directly would not provide the flexibility to optimize this trade-off, because $X$ must satisfy the channel input constraints and power limits. The auxiliary variable decouples the message-carrying function from the physical channel input: $X = x (U, S)$ is a deterministic function of both $U$ and $S$ , allowing $U$ to be optimized purely for rate.

Exercise (medium, short answer).

For Costa's dirty-paper channel, show that the optimal $α$ is $P / (P + N)$ and the capacity is $\frac{1}{2} lo g (1 + P / N)$ .

Hint

Choose $U = X + α S$ with $X \sim N (0, P)$ independent of $S$ . Compute $I (U; Y) - I (U; S)$ and optimize over $α$ .

Answer

Let $X \sim N (0, P)$ independent of $S$ , and $U = X + α S$ . Then $Y = X + S + Z$ and $U = X + α S$ . Compute $I (U; Y) - I (U; S)$ :

$I (U; S) = h (U) - h (U ∣ S) = h (U) - h (X)$ . $h (U) = \frac{1}{2} lo g (2 π e (P + α^{2} Q))$ , $h (X) = \frac{1}{2} lo g (2 π e P)$ . So $I (U; S) = \frac{1}{2} lo g (1 + α^{2} Q / P)$ .

$I (U; Y) = h (U) + h (Y) - h (U, Y)$ . The variance of $Y$ is $P + Q + N$ . The covariance of $U$ and $Y$ is $Cov (X + α S, X + S + Z) = P + α Q$ . $I (U; Y) = \frac{1}{2} lo g ((P + α^{2} Q) (P + Q + N) / ((P + α^{2} Q) (P + Q + N) - (P + α Q)^{2}))$ .

After simplification, $R (α) = I (U; Y) - I (U; S) = \frac{1}{2} lo g ((P + Q + N) (P + α^{2} Q) - (P + α Q)^{2}) / (N (P + α^{2} Q))$ . Setting $d R / d α = 0$ yields $α^{*} = P / (P + N)$ , and substituting gives $R (α^{*}) = \frac{1}{2} lo g (1 + P / N)$ .

Exercise (hard, short answer).

Prove the Gelfand-Pinsker converse: $R \leq I (U; Y) - I (U; S)$ for any achievable rate, for some auxiliary $U$ satisfying the Markov chain $U \to (X, S) \to Y$ .

Hint

Define $U_{i} = (W, S^{i - 1}, S_{i + 1}^{n})$ and use the chain rule for mutual information.

Answer

Let $W$ be the message and $S^{n}$ the state. Define $U_{i} = (W, S^{i - 1}, S_{i + 1}^{n})$ . Then $U_{i} \to (X_{i}, S_{i}) \to Y_{i}$ since $Y_{i}$ depends only on $(X_{i}, S_{i})$ and $U_{i}$ is a function of the message and state sequence. By Fano's inequality:

$n R \leq I (W; Y^{n}) + n ϵ_{n} = \sum_{i = 1}^{n} I (W; Y_{i} ∣ Y^{i - 1}) + n ϵ_{n} .$

Since $S^{n}$ is i.i.d. and independent of $W$ : $I (W; Y_{i} ∣ Y^{i - 1}) \leq I (W, Y^{i - 1}; Y_{i}) = I (W, S^{i - 1}, S_{i + 1}^{n}, Y^{i - 1}; Y_{i})$ (adding $S^{i - 1}, S_{i + 1}^{n}$ only increases information). By the memoryless property: $\leq I (U_{i}, X_{i}, S_{i}; Y_{i}) = I (U_{i}; Y_{i}) + I (X_{i}, S_{i}; Y_{i} ∣ U_{i})$ .

For the rate penalty: $n R = H (W) \geq H (W ∣ S^{n}) = I (W; Y^{n} ∣ S^{n}) + H (W ∣ Y^{n}, S^{n})$ . So $n R \leq I (W; Y^{n} ∣ S^{n}) + n ϵ_{n} = \sum_{i} I (W; Y_{i} ∣ S^{n}, Y^{i - 1}) + n ϵ_{n}$ .

Combining and using the single-letterization with $Q$ uniform on ${1, \dots, n}$ : $R \leq I (U; Y ∣ Q) - I (U; S ∣ Q)$ where $U = U_{Q}$ , and the Markov chain holds by construction.

Exercise (hard, short answer).

Show that if the transmitter knows the state only causally (i.e., $X_{i} = f_{i} (W, S^{i})$ ), the capacity may be strictly less than the Gelfand-Pinsker capacity.

Hint

Compare causal and non-causal state knowledge for a channel where the state determines which output alphabet the channel uses.

Answer

Consider a channel where $S \in {0, 1}$ determines the output: when $S = 0$ , $Y = X$ ; when $S = 1$ , $Y = X \oplus 1$ (bit flip). With non-causal knowledge, the transmitter can invert $X$ when $S = 1$ to compensate, achieving $R = 1$ bit/use (the channel is noiseless from the transmitter's perspective after state compensation). With causal knowledge, the transmitter must choose $X_{i}$ knowing only $S^{i}$ (past and current state), not future states. The Shannon capacity with causal state information is $C_{causal} = max_{p (x ∣ s)} I (X; Y ∣ S)$ , which for this channel is still 1 bit/use since the current state is known. For a better example, consider a channel where $S = 0$ gives $Y = X$ and $S = 1$ gives $Y = Z$ (input disconnected). With non-causal knowledge, the transmitter sends only when $S = 0$ and gets rate $P (S = 0)$ . With causal knowledge, same. The difference appears when the state sequence creates opportunities for coding across time that causal knowledge cannot exploit — e.g., the binary channel with state-dependent erasure where non-causal knowledge enables binning strategies unavailable causally.

Exercise (hard, short answer).

Connect dirty-paper coding to the MIMO broadcast channel: explain how DPC achieves the sum-rate capacity of a Gaussian MIMO broadcast channel.

Hint

Encode users successively, treating previously encoded users as known interference.

Answer

In a Gaussian MIMO broadcast channel with $K$ users, the transmitter encodes users in a specific order. User $k$ 's signal is encoded using dirty-paper coding against the interference from users $1, \dots, k - 1$ , which is known because those users have already been encoded. Each user's DPC encoding achieves the rate $R_{k} = \frac{1}{2} lo g (1 + SINR_{k})$ where SINR is the signal-to-interference-plus-noise ratio after DPC pre-cancellation of previously encoded users. The sum rate over all encoding orders is maximized by choosing the order that balances the SINR across users. This DPC-based successive encoding achieves the sum-rate capacity of the Gaussian MIMO broadcast channel, as shown by Yu and Cioffi (2004) and Weingarten, Steinberg, and Shamai (2006).

Lean formalization Intermediate+

Mathlib does not define channels with state, the Gelfand-Pinsker capacity formula, or Costa's dirty-paper result. The formula $C = max [I (U; Y) - I (U; S)]$ requires optimizing over auxiliary random variables with a Markov chain constraint. The binning achievability proof requires partitioning auxiliary codewords by state compatibility. The Costa result requires Gaussian auxiliary variable optimization with a power constraint. None of these are formalized. This unit ships without formalization.

Advanced results Master

The Gelfand-Pinsker formula as an optimization

The Gelfand-Pinsker capacity $C_{GP} = max_{p (u ∣ x, s), x (u, s)} [I (U; Y) - I (U; S)]$ can be interpreted as follows. The term $I (U; S)$ is the rate cost of making the auxiliary codeword compatible with the state (binning cost). The term $I (U; Y)$ is the rate benefit of the decoder identifying the correct codeword. The net rate is the difference.

For discrete channels, the optimization is over finite alphabets and can be solved numerically using the Blahut-Arimoto algorithm adapted for the Gelfand-Pinsker setting. The auxiliary variable $U$ can be restricted to $∣ U ∣ \leq min (∣ X ∣ \cdot ∣ S ∣, ∣ Y ∣ + ∣ S ∣)$ by the cardinality bound for auxiliary variables.

Costa's result and the cancellation parameter

Costa's choice $U = X + α S$ with $α = P / (P + N)$ is optimal for the Gaussian case. The parameter $α$ balances two effects:

$α = 0$ : no interference cancellation, rate is $I (X; Y) = \frac{1}{2} lo g (1 + P / (Q + N))$ .
$α = 1$ : full pre-subtraction, but $X = U - S$ has variance $P + Q - 2 α Cov (X, S) + α^{2} Q$ , which may violate the power constraint.

The optimal $α = P / (P + N)$ maximizes the net rate $I (U; Y) - I (U; S)$ over all $α \in [0, 1]$ . At this value, the effective noise seen by the decoder (after accounting for the correlation between $U$ and $Y$ ) has the same variance as the original noise $Z$ , giving the clean-channel capacity.

Duality between Gelfand-Pinsker and Wyner-Ziv

The Gelfand-Pinsker theorem and the Wyner-Ziv theorem are information-theoretic duals:

	Wyner-Ziv (source coding)	Gelfand-Pinsker (channel coding)
Side info location	Decoder	Encoder
Rate formula	$I (X; U) - I (Y; U)$	$I (U; Y) - I (U; S)$
Minus sign	Subtract decoder's knowledge	Subtract encoder's knowledge of state
Binning direction	Bin by source, decode with side info	Bin by state, encode with message

In both cases, the rate equals the difference of two mutual informations, representing net information after accounting for side information. The minus term quantifies the side information's contribution.

Writing on fading paper

The dirty-paper model extends to fading channels where the state $S$ affects the channel multiplicatively: $Y = H \cdot X + Z$ , where $H$ is the fading coefficient (channel gain). When $H$ is known at the transmitter, the "writing on fading paper" result shows that pre-coding can partially compensate for the fading.

However, for fading channels, the result is more nuanced than Costa's original setting. The multiplicative state means the interference scales with the input, and the optimal coding strategy involves both power allocation (water-filling) and dirty-paper pre-coding. The combination achieves the broadcast channel capacity for the Gaussian fading MIMO channel.

Synthesis. The Gelfand-Pinsker theorem and Costa's dirty-paper coding are the central results on channel coding with non-causal transmitter side information, establishing that known interference can be pre-cancelled at no asymptotic rate cost for the Gaussian channel. The central insight is that binning auxiliary codewords by state compatibility allows the encoder to "write around" the known interference while the decoder identifies the correct codeword from the received signal. The rate formula $I (U; Y) - I (U; S)$ represents net information after the binning cost, and the foundational reason Costa's result achieves zero penalty is that the optimal auxiliary variable $U = X + α S$ creates a perfect correlation structure that cancels the interference at the decoder. The result builds toward the MIMO broadcast channel 46.06.02 via successive dirty-paper encoding, the interference channel 46.06.04 via per-transmitter DPC, and is dual to Wyner-Ziv 46.05.02 in the source-channel coding duality. Putting these together, dirty-paper coding is the single most important technique for exploiting transmitter side information, and its impact on modern wireless communications (MIMO, cognitive radio, interference management) is foundational.

Full proof set Master

Proposition (Costa's dirty-paper capacity). For $Y = X + S + Z$ with $S \sim N (0, Q)$ known at the transmitter, $Z \sim N (0, N)$ unknown, and $E [X^{2}] \leq P$ , the capacity is $C = \frac{1}{2} lo g (1 + P / N)$ .

Proof. Achievability. Let $U = X + α S$ with $X \sim N (0, P)$ independent of $S$ , and $α$ to be optimized. The encoder, given $S^{n}$ , transmits $X^{n} = U^{n} - α S^{n}$ .

Power constraint: $E [X^{2}] = E [(U - α S)^{2}] = P + α^{2} Q - 2 α E [X S]$ . Since $X$ is independent of $S$ in the codebook generation, $E [X S] = 0$ , so $E [X^{2}] = P$ . (Wait — actually $X = U - α S$ , so $E [X^{2}] = Var (X) = P$ when $U$ and $S$ are designed such that $X \sim N (0, P)$ . This is satisfied by construction.)

Received signal: $Y = U - α S + S + Z = U + (1 - α) S + Z$ .

$I (U; Y) = h (Y) - h (Y ∣ U)$ . $Y ∣ U$ has variance $(1 - α)^{2} Q + N$ . $Y$ has variance $P + (1 - α)^{2} Q + N + 2 (1 - α) Cov (U, S)$ . $Cov (U, S) = α Q$ . So $Var (Y) = P + (1 - α)^{2} Q + N + 2 (1 - α) α Q = P + Q + N - α^{2} Q$ .

$I (U; S) = h (U) - h (U ∣ S) = \frac{1}{2} lo g \frac{P + α ^{2} Q}{P}$ .

$I (U; Y) = \frac{1}{2} lo g \frac{P + Q + N - α ^{2} Q}{( 1 - α ) ^{2} Q + N}$ .

Rate $= I (U; Y) - I (U; S) = \frac{1}{2} lo g \frac{P + Q + N - α ^{2} Q}{( 1 - α ) ^{2} Q + N} \cdot \frac{P}{P + α ^{2} Q}$ .

Setting $α = P / (P + N)$ and simplifying yields $\frac{1}{2} lo g (1 + P / N)$ . $□$

Connections Master

46.05.01 — Slepian-Wolf uses the same binning technique in the source coding context; Gelfand-Pinsker applies binning to channel coding with state.
46.05.02 — Wyner-Ziv is the source-coding dual of Gelfand-Pinsker: both use auxiliary variables and rate formulas with a difference of mutual informations.
46.06.02 — Marton's inner bound for the broadcast channel uses dirty-paper coding to pre-cancel interference between users.
46.06.04 — The Han-Kobayashi bound for the interference channel uses dirty-paper coding at each transmitter to manage cross-interference.
46.03.01 — The standard channel capacity is the Gelfand-Pinsker capacity when the state is absent ( $S = \emptyset$ ): the formula reduces to $max I (X; Y)$ .
46.03.06 — Feedback (causal output knowledge) does not increase capacity, while non-causal state knowledge does — the contrast highlights the importance of timing in side information.

Historical & philosophical context Master

Sergius Gelfand and Mark Pinsker published "Coding for Channel with Random Parameters" in Problems of Control and Information Theory (vol. 9, no. 1, 1980, pp. 19-31). The paper established the general formula for channels with non-causal state information at the transmitter and introduced the binning technique for the channel coding setting.

Max Costa published "Writing on Dirty Paper" in the IEEE Transactions on Information Theory (IT-29, no. 3, 1983, pp. 439-441). The paper is one of the shortest and most impactful in information theory — only three pages — and showed that the Gelfand-Pinsker capacity for the Gaussian channel equals the clean-channel capacity. Costa's choice of $U = X + α S$ with $α = P / (P + N)$ is an elegant application of the Gelfand-Pinsker framework.

The practical significance of dirty-paper coding was not fully appreciated until the rise of MIMO systems in the late 1990s and early 2000s. Yu and Cioffi (2004) showed that DPC achieves the sum-rate capacity of the Gaussian MIMO broadcast channel, and Weingarten, Steinberg, and Shamai (2006) proved that DPC achieves the entire capacity region. These results established DPC as the theoretical benchmark for multi-user MIMO communication.

The binning technique introduced by Gelfand-Pinsker has become the standard tool for channel coding with side information and appears in cognitive radio channels (where the secondary user knows the primary user's message), interference channels, and broadcast channels.

Bibliography Master

@article{gelfand-pinsker1980,
  author  = {Gelfand, S. I. and Pinsker, M. S.},
  title   = {Coding for Channel with Random Parameters},
  journal = {Problems of Control and Information Theory},
  volume  = {9},
  number  = {1},
  pages   = {19--31},
  year    = {1980},
}
@article{costa1983,
  author  = {Costa, M. H. M.},
  title   = {Writing on Dirty Paper},
  journal = {IEEE Transactions on Information Theory},
  volume  = {IT-29},
  number  = {3},
  pages   = {439--441},
  year    = {1983},
}
@book{cover-thomas2006,
  author    = {Cover, T. M. and Thomas, J. A.},
  title     = {Elements of Information Theory},
  edition   = {2nd},
  publisher = {Wiley},
  year      = {2006},
}
@article{yu-cioffi2004,
  author  = {Yu, W. and Cioffi, J. M.},
  title   = {Sum Capacity of Gaussian Vector Broadcast Channels},
  journal = {IEEE Transactions on Information Theory},
  volume  = {50},
  pages   = {1875--1892},
  year    = {2004},
}
@article{weingarten-steinberg-shamai2006,
  author  = {Weingarten, H. and Steinberg, Y. and Shamai, S.},
  title   = {The Capacity Region of the Gaussian Multiple-Input Multiple-Output Broadcast Channel},
  journal = {IEEE Transactions on Information Theory},
  volume  = {52},
  pages   = {3936--3964},
  year    = {2006},
}

Prerequisites

46.05.01
46.03.01

Tier anchors

beginner: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §7.6 and §15.5 (writing on dirty paper: the transmitter knows the interference and can pre-cancel it, achieving the same rate as if the interference did not exist)
intermediate: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §7.6 (Gelfand-Pinsker theorem for channels with state known at the transmitter, random binning achievability, Costa's dirty-paper result for the Gaussian channel)
master: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §7.6; Gelfand & Pinsker 1980 Capacity of a broadcast channel with one deterministic component; Costa 1983 Writing on Dirty Paper; Csiszar & Korner 2011 Information Theory: Coding Theorems for Discrete Memoryless Systems 2e (Cambridge) §7.3

References

Gelfand, S. I. & Pinsker, M. S. — Coding for Channel with Random Parameters · Problems of Control and Information Theory 9(1) (1980) 19-31; the original paper establishing the capacity of a channel with state $S$ known non-causally at the transmitter: $C = max_{p (u ∣ x, s) p (x ∣ s)} [I (U; Y) - I (U; S)]$ where $U$ is an auxiliary variable, $S$ is the channel state, and the maximum is over all joint distributions satisfying $U \to (X, S) \to Y$ . The proof uses random binning: the encoder maps the message and state to a bin of auxiliary codewords.
Costa, M. H. M. — Writing on Dirty Paper · IEEE Transactions on Information Theory IT-29(3) (1983) 439-441; the celebrated result showing that for the Gaussian channel $Y = X + S + Z$ where $S$ is interference known at the transmitter and $Z \sim N (0, N)$ is unknown noise, the capacity equals $\frac{1}{2} lo g (1 + P / N)$ where $P$ is the power constraint — the same as if $S$ did not exist. The proof uses an auxiliary variable $U = X + α S$ with $α = P / (P + N)$ .
Cover, T. M. & Thomas, J. A. — Elements of Information Theory (2nd ed.) · Wiley (2006). Section 7.6: channels with state, the Gelfand-Pinsker theorem, the binning achievability proof, and Costa dirty-paper coding as the Gaussian special case. The key insight is that binning lets the encoder "pre-subtract" the known interference at the cost of a rate penalty $I (U; S)$ .

Estimated time

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