Digital Communications

Costa Precoding

Q: How does Costa precoding differ from receiver-side interference cancellation?

In receiver-side cancellation the receiver must estimate and subtract the interference, which costs power and is limited by estimation error. Costa precoding instead exploits interference that is known non-causally at the transmitter, such as the signals intended for other users in a multiuser downlink. Costa's 1983 result proves that when the interference s is known to the transmitter but not the receiver, the achievable rate equals (1/2)log2(1 + P/N), exactly the same as if the interference were absent, with no power penalty and no need for the receiver to know s. The transmitter applies a random binning and modulo strategy that aligns the codeword with the interference so the receiver decodes cleanly. This is why it is called writing on dirty paper: the writer who sees the dirt in advance can write so the reader cannot tell the page was ever dirty.

Q: Why is dirty-paper coding considered optimal for the MIMO broadcast channel?

In a MIMO downlink one base station with M antennas serves K users simultaneously, and each user sees the signals meant for the other users as interference. Because the base station generates all of those signals, it knows that interference non-causally, which is exactly the condition Costa's theorem requires. By encoding users sequentially and pre-subtracting each already-encoded user's contribution, the base station achieves rates as if every user were interference-free. Weingarten, Steinberg, and Shamai proved in 2006 that this dirty-paper coding strategy achieves the full capacity region of the Gaussian MIMO broadcast channel, making it the information-theoretic optimum rather than just a good heuristic. Linear precoders such as zero-forcing only approach this region at high SNR.

Q: What practical schemes approximate Costa precoding in real transmitters?

True random-binning dirty-paper coding has prohibitive complexity, so deployed systems use structured lattice approximations. Tomlinson-Harashima precoding (THP) is the most common: it applies a modulo operation that folds the pre-subtracted interference back into the fundamental Voronoi region, capturing most of the dirty-paper gain with a simple feedback filter and a modulo device. Vector perturbation precoding and lattice-reduction-aided precoding push closer to the Costa bound at the cost of a search over the perturbation lattice. These schemes incur a modulo loss (about 1.53 dB shaping loss for large QAM plus a power-boost and modulo-loss term at low rates) but avoid the exponential codebook of the original construction. Massive MIMO systems often skip THP entirely and rely on near-orthogonal channels where zero-forcing already nears capacity.

/KOH-stuh pree-KOH-ding/

Proved by Max Costa in his 1983 paper "Writing on Dirty Paper," this result shows that interference known non-causally at the transmitter can be perfectly pre-cancelled, so the achievable rate equals that of an interference-free channel with no power penalty and without the receiver ever knowing the interference. It is the information-theoretic foundation of dirty-paper coding and the optimal downlink strategy for the multiuser MIMO broadcast channel, where the base station knows every user's signal and can subtract each one before transmission. Random-binning Costa coding is too complex to deploy directly, so practical transmitters use lattice approximations such as Tomlinson-Harashima precoding.

Category: Digital Communications

Origin: M. Costa, 1983

Capacity penalty: 0 (ideal DPC)

Writing on Dirty Paper: The Costa Result

Costa's 1983 theorem answered a question that seemed counter-intuitive: if a channel adds Gaussian interference s that the transmitter knows in advance but the receiver does not, how much capacity is lost? The surprising answer is none. By treating the interference as side information available only at the encoder, Costa constructed a random-binning argument in which each message maps to a bin of auxiliary codewords, and the transmitter selects the codeword whose correlation with the known interference allows the receiver to decode after a simple subtraction. The resulting rate is identical to a channel with no interference at all, which is why the construction earned the memorable name "writing on dirty paper."

The mechanism that makes this work is the auxiliary variable u = x + αs, where x is the transmitted codeword, s is the known interference, and α is a scalar inflation factor. Costa showed that choosing α equal to the ratio P/(P + N), the minimum-mean-square-error coefficient, maximizes the mutual information I(u; y) minus I(u; s) and recovers the full interference-free rate. This single insight separated the side-information problem from the noise problem and made the broadcast downlink tractable.

In a multiuser MIMO downlink the base station generates the signals for all served users, so the cross-user interference is exactly the kind of transmitter-known interference Costa assumed. Encoding users one at a time and pre-subtracting each previously encoded user's contribution lets the base station deliver every user a clean channel. Weingarten, Steinberg, and Shamai later proved that this sequential dirty-paper coding achieves the full capacity region of the Gaussian MIMO broadcast channel, elevating Costa precoding from a clever bound to the proven optimum.

Governing Equations

Dirty-Paper Channel Model:
y = x + s + z, z ∼ N(0, N), E[x²] ≤ P (s known at Tx only)

Costa Capacity (no loss):
C = ½ log₂(1 + P/N) bits/channel use (independent of s)

Auxiliary Variable & Optimal Inflation:
u = x + αs, α_opt = P / (P + N)

Achievable Rate:
R = I(u; y) − I(u; s)

P = signal power, N = noise power, z = AWGN, s = transmitter-known interference, α = MMSE inflation factor. With α = α_opt the rate R equals the interference-free capacity C.

Costa Precoding vs. Practical Downlink Schemes

Scheme	Achieves BC capacity?	Tx complexity	Rx knows interference?	Typical gap to Costa	Where used
Ideal Costa / DPC	Yes (full region)	Exponential (random bins)	No	0 dB (reference)	Capacity benchmark
Tomlinson-Harashima	Near-optimal	Low (modulo + FB filter)	No	≈ 1.5 dB shaping + modulo loss	Wireline DSL, MU-MIMO
Vector perturbation	Near-optimal	High (lattice search)	No	≈ 0.5 to 1 dB	Multiuser downlink
Zero-forcing	Only at high SNR	Low (matrix inverse)	No	Several dB at low SNR	Massive MIMO 5G
No precoding (TDMA)	No	Minimal	n/a	Large (loses multiplexing)	Legacy single-user

Common Questions

Frequently Asked Questions

How does Costa precoding differ from receiver-side interference cancellation?

Receiver-side cancellation forces the receiver to estimate and subtract interference, which costs power and is bounded by estimation error. Costa precoding instead exploits interference known non-causally at the transmitter, such as other users' downlink signals. Costa's 1983 result proves the achievable rate equals ½log₂(1 + P/N), identical to an interference-free channel, with no power penalty and no receiver knowledge of s. The transmitter uses random binning with the auxiliary variable u = x + αs so the receiver decodes cleanly, hence "writing on dirty paper."

Why is dirty-paper coding considered optimal for the MIMO broadcast channel?

In a downlink, one base station with M antennas serves K users and each user sees the others' signals as interference. The base station generates all of them, so that interference is known non-causally, exactly Costa's condition. Encoding users sequentially and pre-subtracting each prior user's contribution gives every user an interference-free rate. Weingarten, Steinberg, and Shamai proved in 2006 that this strategy attains the full Gaussian MIMO broadcast capacity region, making it the information-theoretic optimum; linear zero-forcing only approaches it at high SNR.

What practical schemes approximate Costa precoding in real transmitters?

Random-binning DPC is too complex, so systems use structured lattices. Tomlinson-Harashima precoding applies a modulo operation that folds pre-subtracted interference into the fundamental Voronoi region, capturing most of the gain with a feedback filter and modulo device. Vector perturbation and lattice-reduction-aided precoding push closer to the Costa bound via a perturbation search. These incur shaping loss of roughly 1.53 dB plus modulo loss at low rates, but avoid the exponential codebook. Massive MIMO often skips them since near-orthogonal channels let zero-forcing near capacity.

Related Terms

← COST 231 Walfish-Ikegami Costas Loop →