46.06.04 · information-theory / network-information

Interference Channel: Han-Kobayashi Bound and Gaussian Interference

shipped3 tiersLean: none

Anchor (Master): Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §15.5; Han & Kobayashi 1981 A new achievable rate region for the interference channel; Etkin, Tse & Wang 2008 Gaussian interference channel capacity to within one bit; El Gamal & Kim 2011 Network Information Theory Ch. 6

Intuition Beginner

Two people are talking on their cell phones in the same room. Each person hears their own caller plus interference from the other person's conversation. How fast can each person communicate?

This is the interference channel: two independent transmitter-receiver pairs sharing the same medium. Each transmitter has its own message for its intended receiver, but the signals interfere with each other.

The simplest strategy is to treat the other user's signal as noise. Each receiver ignores the interference and decodes its own message. This works well when the interference is weak — it is just a small amount of extra noise.

A better strategy is to decode the interference. If receiver 1 can decode transmitter 2's message, it can subtract it from the received signal and then decode its own message cleanly. This works well when the interference is strong — strong enough to decode reliably.

The Han-Kobayashi strategy interpolates between these extremes using rate-splitting. Each transmitter divides its message into a private part (decoded only by its intended receiver) and a common part (decoded by both receivers). Each receiver first decodes both common parts (its own and the other user's), subtracts the interference, then decodes its private part.

The Gaussian interference channel has three regimes. Weak interference: treat as noise is near-optimal. Strong interference: decode the interference is optimal. Moderate interference: rate-splitting (Han-Kobayashi) achieves the best known performance, within 1 bit of capacity.

Visual Beginner

Figure: the Gaussian interference channel. Two transmitters (TX1, TX2) send signals $X_{1}, X_{2}$ . Receiver 1 sees $Y_{1} = X_{1} + a X_{2} + Z_{1}$ . Receiver 2 sees $Y_{2} = b X_{1} + X_{2} + Z_{2}$ . The cross-links $a, b$ represent interference strength.

Interference regime	Condition	Best strategy	Capacity known?
Very strong	$a \geq 1 + P_{1}$	Decode interference at unintended RX	Yes
Strong	$a \geq 1$	Decode interference	Yes
Weak	$a < 1$	Rate-splitting (HK)	Within 1 bit
Very weak	$a \approx 0$	Treat as noise	Near-optimal

Worked example Beginner

A symmetric Gaussian interference channel: $Y_{1} = X_{1} + a X_{2} + Z_{1}$ and $Y_{2} = a X_{1} + X_{2} + Z_{2}$ , with $P_{1} = P_{2} = 5$ , $N_{1} = N_{2} = 1$ , and $a = 0.5$ (weak interference).

Treating interference as noise: each receiver sees effective noise with variance $a^{2} P_{2} + N_{1} = 0.25 \times 5 + 1 = 2.25$ . Rate $= \frac{1}{2} lo g (1 + 5/2.25) \approx \frac{1}{2} lo g (3.22) \approx 0.85$ bits/use per user.

Han-Kobayashi rate-splitting: split each user's power into private ( $α P$ ) and common ( $(1 - α) P$ ) parts. Each receiver decodes both common parts first (treating the private interference as noise), then decodes its private part with the common interference removed. The optimal split gives a higher rate than treating as noise.

For very strong interference ( $a = 3$ ): receiver 1 decodes $X_{2}$ first at rate $\frac{1}{2} lo g (1 + a^{2} P_{2} / (P_{1} + N_{1})) = \frac{1}{2} lo g (1 + 45/6) \approx 1.5$ bits/use, subtracts it, then decodes $X_{1}$ at full rate $\frac{1}{2} lo g (1 + 5/1) \approx 1.58$ bits/use. Both users achieve their point-to-point capacity.

Check your understanding Beginner

Formal definition Intermediate+

A two-user interference channel has input alphabets $X_{1}, X_{2}$ , output alphabets $Y_{1}, Y_{2}$ , and transition probabilities $p (y_{1}, y_{2} ∣ x_{1}, x_{2})$ .

Definition (Interference channel code). A $(2^{n R_{1}}, 2^{n R_{2}}, n)$ 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}$ , and 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 (Gaussian interference channel). The Gaussian IC has:

Y_{1} = X_{1} + a_{21} X_{2} + Z_{1}, Y_{2} = a_{12} X_{1} + X_{2} + Z_{2},

with $Z_{i} \sim N (0, N_{i})$ and power constraints $E [X_{i}^{2}] \leq P_{i}$ .

Definition (Han-Kobayashi region). The HK achievable rate region is:

R_{H K} = ⋃ ⎩ ⎨ ⎧ (R_{1}, R_{2}) : R_{1} R_{2} R_{1} + R_{2} \leq I (X_{1}; Y_{1} ∣ U_{2}, Q) \leq I (X_{2}; Y_{2} ∣ U_{1}, Q) \leq min (I (X_{1}, U_{2}; Y_{1} ∣ Q) + I (X_{2}; Y_{2} ∣ U_{1}, U_{2}, Q), I (X_{1}; Y_{1} ∣ U_{1}, U_{2}, Q) + I (X_{2}, U_{1}; Y_{2} ∣ Q)) ⎭ ⎬ ⎫

where the union is over all $p (q) p (u_{1} ∣ q) p (u_{2} ∣ q) p (x_{1} ∣ u_{1}, q) p (x_{2} ∣ u_{2}, q)$ . The auxiliary variables $U_{1}, U_{2}$ represent the common messages, and $X_{1}, X_{2}$ carry both common and private information.

Key theorem with proof Intermediate+

Theorem (Etkin-Tse-Wang 2008). The Han-Kobayashi achievable rate region is within 1 bit per user of the capacity of the two-user Gaussian interference channel.

Proof sketch. The proof shows that a specific HK strategy (with Gaussian inputs and a specific power split) achieves a rate within 1 bit of the cut-set outer bound.

Power split. Each user splits power: private part uses power $α_{i} P_{i}$ and common part uses $(1 - α_{i}) P_{i}$ . The optimal split sets $α_{i}$ such that the private signal is at the noise floor of the unintended receiver: $α_{i} P_{i} \cdot a_{ij}^{2} \approx N_{j}$ , giving $α_{i} \approx N_{j} / (a_{ij}^{2} P_{i})$ .

Near-optimal rates. With this split, each receiver sees the other user's private signal at or below the noise floor, so it causes minimal interference. The common parts are decoded and subtracted. The resulting rate for user 1 is:

R_{1} \approx \frac{1}{2} lo g (1 + \frac{P _{1}}{N _{1} + α _{2} P _{2} a _{21}^{2}}) \geq \frac{1}{2} lo g (1 + \frac{P _{1}}{2 N _{1}}) = C_{1} - \frac{1}{2} lo g 2 = C_{1} - 0.5 bits .

The 0.5-bit gap per constraint, combined with the sum-rate constraint, gives at most 1 bit gap per user from the outer bound. $□$

Bridge. The interference channel builds toward all multi-user wireless network models by capturing the fundamental tension between treating interference as noise and decoding it. This is exactly the design choice that appears in every practical wireless system: cellular networks (where neighboring cells interfere), Wi-Fi (where overlapping access points interfere), and cognitive radio (where secondary users manage interference to primary users). The result appears again in the relay channel 46.06.03 where relay cooperation creates controlled interference, and the MAC 46.06.01 provides the decoding framework for the interference channel (each receiver faces a virtual MAC from both transmitters). The foundational reason the HK strategy works is that rate-splitting creates a continuum between the two extreme strategies (treat as noise vs. full decode), and the optimal operating point on this continuum depends on the interference strength. The central insight is that partial interference decoding through rate-splitting captures almost all the available capacity — within 1 bit — for the Gaussian channel. Putting these together, the interference channel capacity problem is the most important open problem in network information theory, and the HK bound represents the state of the art, demonstrating that a simple power-splitting strategy achieves near-optimal performance.

Exercises Intermediate+

Exercise (medium, short answer).

Describe the rate-splitting strategy in Han-Kobayashi. What are the common and private messages?

Hint

Each user splits its message into two parts with different visibility at the receivers.

Answer

User $i$ splits its message $W_{i}$ into a common message $W_{c i}$ (to be decoded by both receivers) and a private message $W_{p i}$ (decoded only by receiver $i$ ). The encoding uses superposition: $X_{i}$ is generated from both $W_{c i}$ and $W_{p i}$ . Each receiver decodes both common messages ( $W_{c 1}$ and $W_{c 2}$ ) and its own private message ( $W_{p i}$ ), treating the other user's private message as noise. This creates a virtual three-user MAC at each receiver. The rate split determines how much of each user's rate is devoted to common versus private information, with the optimal split depending on the interference strength.

Exercise (hard, short answer).

Prove that in the strong interference regime ( $a_{12} \geq 1, a_{21} \geq 1$ ), the capacity region is the intersection of two MAC capacity regions.

Hint

Show that both messages must be decodable at both receivers, reducing the problem to two simultaneous MAC constraints.

Answer

Converse. In strong interference, receiver 1's channel from user 2 is better than receiver 2's channel from user 2: $a_{21} \geq 1$ means $X_{2}$ arrives at $Y_{1}$ with gain $\geq 1$ . By the strong interference condition, any achievable rate pair must satisfy $R_{2} \leq I (X_{2}; Y_{1} ∣ X_{1})$ (receiver 1 can decode user 2's message) and $R_{1} \leq I (X_{1}; Y_{2} ∣ X_{2})$ (receiver 2 can decode user 1's message). Therefore both receivers can decode both messages, and the capacity region is the intersection of the two MAC regions:

$R_{1} \leq I (X_{1}; Y_{1} ∣ X_{2})$ , $R_{2} \leq I (X_{2}; Y_{1} ∣ X_{1})$ , $R_{1} + R_{2} \leq I (X_{1}, X_{2}; Y_{1})$ (MAC at receiver 1),

$R_{1} \leq I (X_{1}; Y_{2} ∣ X_{2})$ , $R_{2} \leq I (X_{2}; Y_{2} ∣ X_{1})$ , $R_{1} + R_{2} \leq I (X_{1}, X_{2}; Y_{2})$ (MAC at receiver 2).

Achievability. Each receiver decodes both messages using joint typicality decoding (as in the MAC). Since both messages are decodable at both receivers, the MAC achievability proof applies at each receiver independently.

Exercise (hard, short answer).

For the one-sided interference channel ( $Y_{1} = X_{1} + Z_{1}$ , $Y_{2} = a X_{1} + X_{2} + Z_{2}$ ), find the capacity region. Why is this special case solvable?

Hint

Receiver 1 sees no interference. Receiver 2 sees interference from transmitter 1.

Answer

Receiver 1 sees a clean channel $Y_{1} = X_{1} + Z_{1}$ with capacity $C_{1} = \frac{1}{2} lo g (1 + P_{1} / N_{1})$ . Since receiver 1 is not affected by user 2, user 2's rate does not constrain user 1.

Receiver 2 sees $Y_{2} = a X_{1} + X_{2} + Z_{2}$ . Two cases:

If $a \leq 1$ (weak interference from user 1 to receiver 2): receiver 2 treats $X_{1}$ as noise. $R_{2} \leq \frac{1}{2} lo g (1 + P_{2} / (a^{2} P_{1} + N_{2}))$ .

If $a > 1$ (strong interference): receiver 2 decodes $X_{1}$ first (since $a > 1$ , the signal from user 1 is stronger than user 2's intended signal). After subtracting, $R_{2} \leq \frac{1}{2} lo g (1 + P_{2} / N_{2})$ . But user 1's rate must satisfy $R_{1} \leq \frac{1}{2} lo g (1 + a^{2} P_{1} / (P_{2} + N_{2}))$ for receiver 2 to decode $X_{1}$ .

The one-sided case is solvable because the interference is asymmetric: only one receiver faces interference, simplifying the analysis to a single MAC-like constraint at receiver 2.

Exercise (hard, short answer).

Show that the sum-rate of the symmetric Gaussian IC with $P_{1} = P_{2} = P$ , $N_{1} = N_{2} = N$ , and interference gain $a$ satisfies: in weak interference ( $a < 1$ ), the sum-rate is strictly less than $2 \cdot C_{point-to-point} = lo g (1 + P / N)$ .

Hint

Use the cut-set bound at each receiver.

Answer

Each receiver sees $Y_{i} = X_{i} + a X_{j} + Z_{i}$ . The cut-set bound at receiver 1 gives $R_{1} \leq I (X_{1}; Y_{1} ∣ X_{2}) = \frac{1}{2} lo g (1 + P / N)$ (conditioning on $X_{2}$ removes interference). But the sum-rate is bounded by $R_{1} + R_{2} \leq I (X_{1}; Y_{1}) + I (X_{2}; Y_{2} ∣ X_{1}) = \frac{1}{2} lo g (1 + (P + a^{2} P) / N) + \frac{1}{2} lo g (1 + P / (a^{2} P + N))$ . For $a < 1$ , this is strictly less than $lo g (1 + P / N)$ because the interference term reduces the effective SNR at each receiver. Specifically, each receiver must contend with the other's interference, and the sum of the resulting rates is less than twice the interference-free capacity. The gap increases as $a \to 1$ .

Lean formalization Intermediate+

Mathlib does not define interference channels, rate-splitting, or the Han-Kobayashi region. The interference channel requires two independent encoder-decoder pairs with cross-channel interference. Rate-splitting divides each message into common and private parts. The HK region is a union over auxiliary variables and input distributions. None of this is formalized. This unit ships without formalization.

Advanced results Master

The weak interference regime

For the symmetric Gaussian IC with weak interference ( $a < 1$ ), the exact capacity is not known, but significant progress has been made:

Treat as noise (TIN): Each receiver treats the other user's signal as noise. Achievable rate: $R_{i} = \frac{1}{2} lo g (1 + P / (a^{2} P + N))$ . This is optimal in the very weak interference regime ( $a \leq 1/2$ for the symmetric case with $P / N$ large).
Han-Kobayashi: Within 1 bit of capacity for all $a < 1$ . The improvement over TIN is most significant in the moderate interference regime ( $0.5 < a < 1$ ).

The generalized degrees of freedom

The generalized degrees of freedom (GDoF) provides a high-SNR approximation to the capacity. For the symmetric Gaussian IC with $SNR = P / N$ and interference-to-noise ratio $INR = a^{2} P / N$ :

GDoF = SNR \to \infty lim \frac{C _{sum}}{lo g SNR} = min (1, 1 - \frac{α}{2}, \frac{1 - α}{2} + \frac{1}{2})

where $α = lo g INR / lo g SNR$ is the interference exponent. This piecewise linear function has three regimes:

$α \leq 1/2$ (weak): GDoF $= 1$ per user (interference is negligible).
$1/2 < α \leq 1$ (moderate): GDoF $= 1 - α /2$ (interference reduces degrees of freedom).
$1 < α \leq 2$ (strong): GDoF $= α /2$ (interference helps through decoding).
$α > 2$ (very strong): GDoF $= 1$ per user (interference can be fully decoded and removed).

The $K$ -user interference channel

The two-user results extend partially to $K$ users, but the analysis becomes significantly more complex. The degrees of freedom perspective has been productive: Cadambe and Jafar (2008) showed that the sum GDoF of the $K$ -user interference channel scales as $K /2$ , meaning each user gets approximately half its interference-free capacity at high SNR. Interference alignment (aligning multiple interference signals into the same subspace) is the key technique.

Cognitive interference channels

The cognitive interference channel is a special case where one transmitter knows the other's message non-causally. This models cognitive radio scenarios where the secondary user knows the primary user's transmission. The capacity is known for most cases, achieved by dirty-paper coding the known message at the cognitive transmitter.

Synthesis. The interference channel is the most practically important open problem in network information theory, capturing the fundamental tension between treating interference as noise (simple but suboptimal) and decoding it (optimal in strong interference but complex). The central insight is that the Han-Kobayashi rate-splitting strategy provides a universal approach: by splitting each message into common and private parts, HK creates a continuum between the two extreme strategies that adapts to the interference strength. The Etkin-Tse-Wang result shows this continuum is within 1 bit of capacity for the Gaussian channel. The result builds toward the MAC 46.06.01 (each receiver faces a virtual MAC), the broadcast channel 46.06.02 (each transmitter performs broadcast-like encoding via rate-splitting), and the relay channel 46.06.03 (relay cooperation as interference management). The foundational reason the exact capacity remains unknown for weak interference is that the interplay between the two receivers' decoding strategies creates a non-convex optimization that no known technique resolves. Putting these together, the interference channel is the central open problem of network information theory, and the HK bound with its 1-bit optimality is the state of the art.

Full proof set Master

Proposition (Strong interference capacity). For the Gaussian IC with $a_{12} \geq 1$ and $a_{21} \geq 1$ (strong interference), the capacity region is:

C = p (x_{1}) p (x_{2}) ⋃ k = 1, 2 ⋂ {R_{1} \leq I (X_{1}; Y_{k} ∣ X_{2}), R_{2} \leq I (X_{2}; Y_{k} ∣ X_{1}), R_{1} + R_{2} \leq I (X_{1}, X_{2}; Y_{k})} .

Proof. Achievability. Each receiver performs joint typicality decoding of both messages (MAC decoding). Since $a_{ij} \geq 1$ , receiver $k$ can decode both $X_{1}$ and $X_{2}$ from $Y_{k}$ at rates satisfying the MAC constraints. The region is the intersection of the two MAC regions.

Converse. By Fano's inequality at receiver 1: $n R_{2} \leq I (X_{2}^{n}; Y_{1}^{n} ∣ X_{1}^{n}) + n ϵ_{n}$ . Since $a_{21} \geq 1$ , receiver 1 has a "better" channel from user 2 than receiver 2 does. The strong interference condition ensures $I (X_{2}; Y_{1} ∣ X_{1}) \geq I (X_{2}; Y_{2} ∣ X_{1})$ for all input distributions. Therefore any rate achievable at receiver 2 for user 2 must also be decodable at receiver 1. The MAC constraints at each receiver provide the converse bounds. $□$

Connections Master

46.06.01 — Each receiver in the interference channel faces a virtual MAC (both transmitters contribute to the received signal); the MAC capacity region provides the decoding constraints.
46.06.02 — Each transmitter in the HK strategy performs broadcast-like encoding (common and private messages), analogous to the broadcast channel superposition coding.
46.03.05 — The Gaussian channel capacity and water-filling provide the point-to-point baseline that the interference channel rates approach in the very weak and very strong interference regimes.
46.05.03 — Dirty-paper coding is used in the cognitive interference channel, where one transmitter knows the other's message non-causally.
46.06.03 — The relay channel can be viewed as a special interference channel where the relay cooperates rather than interferes.

Historical & philosophical context Master

Te Sun Han and Kingo Kobayashi published "A New Achievable Rate Region for the Interference Channel" in the IEEE Transactions on Information Theory (IT-27, 1981, 49-60). The paper introduced rate-splitting as the key technique: each user splits its message into common and private parts, and each receiver decodes both common parts plus its own private part. The resulting achievable region strictly improves on all previously known bounds and remains unimproved after more than four decades.

Ronald Etkin, David Tse, and Hua Wang published "Gaussian Interference Channel Capacity to Within One Bit" (IEEE Trans. IT-54, 2008, 5534-5562), establishing that the HK strategy with a specific power split achieves rates within 1 bit per user of the capacity. This landmark result proved that HK is "approximately optimal" for the most important practical case, making the interference channel the first major network information theory problem to admit a constant-gap capacity characterization.

The generalized degrees of freedom framework, developed by Etkin, Tse, and Wang and extended by Cadambe and Jafar, provides a clean high-SNR picture of the interference landscape. Interference alignment (Cadambe and Jafar 2008) extends the analysis to $K$ users and shows that the total DoF scales as $K /2$ , a surprising result given that naive analysis suggests each user loses a degree of freedom to interference.

Bibliography Master

@article{han-kobayashi1981,
  author  = {Han, T. S. and Kobayashi, K.},
  title   = {A New Achievable Rate Region for the Interference Channel},
  journal = {IEEE Transactions on Information Theory},
  volume  = {IT-27},
  pages   = {49--60},
  year    = {1981},
}
@article{etkin-tse-wang2008,
  author  = {Etkin, R. H. and Tse, D. N. C. and Wang, H.},
  title   = {Gaussian Interference Channel Capacity to Within One Bit},
  journal = {IEEE Transactions on Information Theory},
  volume  = {54},
  pages   = {5534--5562},
  year    = {2008},
}
@book{cover-thomas2006,
  author    = {Cover, T. M. and Thomas, J. A.},
  title     = {Elements of Information Theory},
  edition   = {2nd},
  publisher = {Wiley},
  year      = {2006},
}
@article{cadambe-jafar2008,
  author  = {Cadambe, V. R. and Jafar, S. A.},
  title   = {Interference Alignment and Degrees of Freedom of the $K$-User Interference Channel},
  journal = {IEEE Transactions on Information Theory},
  volume  = {54},
  pages   = {3425--3441},
  year    = {2008},
}
@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.05

Tier anchors

beginner: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §15.5 (two transmitter-receiver pairs interfering with each other, treating interference as noise versus decoding it)
intermediate: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §15.5 (the interference channel model, Han-Kobayashi inner bound via rate-splitting, the Gaussian interference channel and its regimes)
master: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §15.5; Han & Kobayashi 1981 A new achievable rate region for the interference channel; Etkin, Tse & Wang 2008 Gaussian interference channel capacity to within one bit; El Gamal & Kim 2011 Network Information Theory Ch. 6

References

Han, T. S. & Kobayashi, K. — A New Achievable Rate Region for the Interference Channel · IEEE Transactions on Information Theory IT-27(1) (1981) 49-60; the paper introducing the Han-Kobayashi achievable region, which uses rate-splitting: each transmitter divides its message into a private part (decoded only by its intended receiver) and a common part (decoded by both receivers). The achievable region is the convex closure over all such splits and input distributions. The HK bound remains the best known inner bound for the general interference channel.
Etkin, R. H., Tse, D. N. C. & Wang, H. — Gaussian Interference Channel Capacity to Within One Bit · IEEE Transactions on Information Theory 54(12) (2008) 5534-5562; the landmark result showing that the Han-Kobayashi achievable region is within 1 bit per user of the capacity for the two-user Gaussian interference channel, regardless of channel parameters. This established HK as the approximately optimal strategy for the most important practical case.
Cover, T. M. & Thomas, J. A. — Elements of Information Theory (2nd ed.) · Wiley (2006). Section 15.5: the interference channel model $Y_{1} = X_{1} + a_{21} X_{2} + Z_{1}$ , $Y_{2} = a_{12} X_{1} + X_{2} + Z_{2}$ for the Gaussian case. The three interference regimes: weak ( $a < 1$ ), mixed, and strong ( $a > 1$ ). The HK achievable strategy via rate-splitting and the capacity results for the strong and very strong interference regimes.

Estimated time

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

Intuition Beginner

Visual Beginner

Worked example Beginner

Check your understanding Beginner

Formal definition Intermediate+

Key theorem with proof Intermediate+

Exercises Intermediate+

Lean formalization Intermediate+

Advanced results Master

The weak interference regime

The generalized degrees of freedom

The K-user interference channel

Cognitive interference channels

Full proof set Master

Connections Master

Historical & philosophical context Master

Bibliography Master

The $K$ -user interference channel