Ferkans — Interactive Telecom Tutor

The Interference Channel: The Unsolved Fundamental Problem

The interference channel (IC) is the most practically relevant and theoretically challenging multiuser channel. Two (or more) transmitter-receiver pairs communicate simultaneously, with each transmitter creating interference at unintended receivers. This models inter-cell interference in cellular networks, co-channel Wi-Fi APs, and spectrum sharing between operators. Unlike the MAC and BC, the capacity region of the general two-user IC remains unknown — one of the great open problems in information theory. What we do know: the capacity in the strong and very strong interference regimes, the approximate capacity within 1 bit/s/Hz for all parameter values (Etkin, Tse, Wang, 2008), and the Han-Kobayashi inner bound that has resisted improvement for over four decades.

Two-User Interference Channel — Schematic of the 2-user Gaussian interference channel. Transmitter $k$ sends message $W_k$ to receiver $k$ via direct link $h_{kk}$ . Cross-links $h_{12}$ and $h_{21}$ create mutual interference. The capacity depends on the relative strength of direct and cross-links.

Definition:
Two-User Gaussian Interference Channel

The two-user Gaussian IC is defined by:

$Y_1 = X_1 + \sqrt{a} X_2 + Z_1$ $Y_2 = \sqrt{b} X_1 + X_2 + Z_2$

where $X_k$ has power constraint $P_k$ , $Z_k \sim \mathcal{N}(0, 1)$ , and $a, b \geq 0$ are the cross-link gains (interference coefficients).

Define the signal-to-noise and interference-to-noise ratios: $\text{SNR}_{1} = P_1, \quad \text{SNR}_{2} = P_2$ $\mathrm{INR}_{12} = a P_2, \quad \mathrm{INR}_{21} = b P_1$

Interference regimes:

Very strong: $a \geq 1 + P_1$ and $b \geq 1 + P_2$ (each receiver can decode the interferer's message)
Strong: $a \geq 1$ and $b \geq 1$ (INR $\geq$ SNR)
Weak: $a < 1$ and $b < 1$
Moderate/mixed: one link has strong interference, the other weak

The interference regime classification determines the optimal strategy: decode interference (strong), treat as noise (weak), or a hybrid approach (moderate).

,

Theorem: Capacity of the Strong Interference Channel

For the two-user Gaussian IC with strong interference ( $a \geq 1$ , $b \geq 1$ ), the capacity region is:

$R_1 \leq \frac{1}{2}\log_2(1 + P_1)$ $R_2 \leq \frac{1}{2}\log_2(1 + P_2)$ $R_1 + R_2 \leq \frac{1}{2}\log_2(1 + P_1 + aP_2)$ $R_1 + R_2 \leq \frac{1}{2}\log_2(1 + bP_1 + P_2)$

This is the intersection of two MAC regions — each receiver decodes both messages.

When interference is strong ( $a \geq 1$ , $b \geq 1$ ), each receiver sees the interfering signal at least as strongly as its own signal. It is therefore optimal for each receiver to decode the interfering message (rather than treating it as noise) and subtract it before decoding its own message. The IC reduces to two coupled MACs.

Proof

Achievability

Each receiver performs SIC to decode both messages:

Receiver 1 decodes $(W_1, W_2)$ from $Y_1 = X_1 + \sqrt{a}X_2 + Z_1$ . This is a MAC with powers $(P_1, aP_2)$ , so the achievable rates satisfy: $R_1 \leq \frac{1}{2}\log_2(1 + P_1)$ , $R_2 \leq \frac{1}{2}\log_2(1 + aP_2)$ , $R_1 + R_2 \leq \frac{1}{2}\log_2(1 + P_1 + aP_2)$ .

Similarly for receiver 2. Since $a \geq 1$ , the constraint $R_2 \leq \frac{1}{2}\log_2(1 + aP_2) \geq \frac{1}{2}\log_2(1 + P_2)$ is non-binding, and the effective constraints are the individual rate bounds and the two sum-rate bounds.

Converse

The converse shows that no scheme can exceed the MAC bounds at each receiver. By Fano's inequality:

$nR_1 \leq I(W_1; Y_1^n) + n\epsilon_n$

Since receiver 1 must decode $W_1$ reliably regardless of $W_2$ : $nR_1 \leq I(X_1^n; Y_1^n | X_2^n) + n\epsilon_n = \frac{n}{2}\log_2(1 + P_1)$

For the sum rate: $n(R_1 + R_2) \leq I(W_1, W_2; Y_1^n) + n\epsilon_n \leq \frac{n}{2}\log_2(1 + P_1 + aP_2)$

The condition $a \geq 1$ ensures that receiver 1 can decode $W_2$ as well as receiver 2 can (degradedness in the interference signal). $\blacksquare$

Definition:
Treating Interference as Noise (TIN)

In the weak interference regime, the simplest strategy is to treat interference as noise (TIN): each receiver decodes its own message while treating the interfering signal as additional Gaussian noise.

TIN achievable rates: $R_1^{\mathrm{TIN}} = \frac{1}{2}\log_2\!\left(1 + \frac{P_1}{1 + aP_2}\right)$ $R_2^{\mathrm{TIN}} = \frac{1}{2}\log_2\!\left(1 + \frac{P_2}{1 + bP_1}\right)$

TIN optimality (Geng, Nair, 2014): TIN achieves to within a constant gap of the capacity if:

$\mathrm{INR}_{12} \leq \text{SNR}_{1} \quad \text{and} \quad \mathrm{INR}_{21} \leq \text{SNR}_{2}$

More precisely, TIN is sum-rate optimal when the interference is "noisy" — below a threshold where decoding interference provides no benefit.

TIN is the strategy used by all practical systems (LTE, NR, Wi-Fi) when inter-cell interference is moderate. The theoretical justification that TIN is approximately optimal in the weak interference regime validates this engineering practice.

Definition:
Han-Kobayashi Achievable Rate Region

The Han-Kobayashi (HK) scheme (1981) is the best known achievable rate region for the general two-user IC. Each transmitter splits its message into a common part (decodable by both receivers) and a private part (decodable only by the intended receiver):

$X_k = X_k^{(c)} + X_k^{(p)}, \quad k = 1, 2$

with power split $P_k^{(c)} + P_k^{(p)} = P_k$ .

Each receiver decodes:

Its own common and private messages
The other user's common message (treating the private as noise)

The HK region is the closure of the convex hull of all rate pairs achievable over all power splits $(P_1^{(c)}, P_2^{(c)})$ and time-sharing. Despite 40+ years of research, no scheme is known to strictly improve upon the HK region for the general IC.

The genius of the HK scheme is the message splitting: the common part is decoded by both receivers (reducing interference), while the private part is treated as noise. The optimal power split depends on the interference regime and is generally hard to compute.

Theorem: Etkin-Tse-Wang Approximate Capacity

For the two-user Gaussian IC with parameters $(\text{SNR}_{1}, \text{SNR}_{2}, \mathrm{INR}_{12}, \mathrm{INR}_{21})$ , the Han-Kobayashi scheme with a specific simple power split achieves rates within 1 bit/s/Hz of the capacity region for all parameter values:

$\mathcal{C} \subseteq \mathcal{R}_{\mathrm{HK}}^{\mathrm{simple}} + 1$

The simple HK scheme sets the private message power to $P_k^{(p)} = \min(P_k, 1/\mathrm{INR}_{kj})$ (just below the noise floor at the unintended receiver) and allocates the remaining power to the common message.

The outer bound uses genie-aided arguments: providing side information to the receivers and reducing to a degraded BC.

Corollary (generalised DoF): At high SNR, the symmetric capacity of the symmetric IC with $\text{SNR} = \text{SNR}$ and $\mathrm{INR} = \text{SNR}^\alpha$ is:

$C_{\mathrm{sym}}(\alpha) \approx \begin{cases} \frac{1}{2}\log(1 + \text{SNR}) & \alpha \leq 1/2 \\ \frac{1}{2}\log(\text{SNR}^{1-\alpha}) & 1/2 < \alpha < 2/3 \\ \frac{1}{2}\log(\text{SNR}^{2\alpha/3}) & 2/3 \leq \alpha \leq 1 \\ \frac{1}{2}\log(\text{SNR}^{\alpha/2}) & 1 < \alpha \leq 2 \\ \frac{1}{2}\log(1 + \text{SNR}) & \alpha \geq 2 \end{cases}$

to within 1 bit.

The 1-bit gap result shows that a simple scheme (with a specific power split) is never more than 1 bit/s/Hz from optimal. This is practically important because it means that the capacity of the IC is known to engineering accuracy for all parameters. The "W-curve" of the generalised DoF reveals five distinct interference regimes, each with a different optimal strategy.

Proof

Inner bound (achievability)

Use the HK scheme with power split: $P_1^{(p)} = \min(P_1, 1/b)$ (private power at user 1).

This ensures user 1's private signal arrives at receiver 2 at power $\leq 1$ (below noise floor), so receiver 2 does not need to decode it. The common part $P_1^{(c)} = P_1 - P_1^{(p)}$ is decoded by both receivers.

Computing rates for this specific split: $R_1 \geq \frac{1}{2}\log\!\left(1 + P_1^{(p)}\right) + \frac{1}{2}\log\!\left(1 + \frac{P_1^{(c)}}{1 + P_1^{(p)} + aP_2^{(p)}}\right)$

Outer bound (converse)

The outer bound provides receiver 1 with side information $S_1 = \sqrt{b}X_1 + Z_2'$ (a noisy version of user 1's signal as seen at receiver 2). With this genie, receiver 1 can decode user 2's message optimally, reducing the IC to a single-user channel plus a degraded BC.

The resulting outer bound is: $R_1 \leq \frac{1}{2}\log(1 + P_1)$ $R_1 + R_2 \leq \frac{1}{2}\log(1 + P_1 + aP_2) + \frac{1}{2}\log\!\left(1 + \frac{P_2}{1 + bP_1}\right)$

Comparing inner and outer bounds shows a gap of at most 1 bit for each rate. $\blacksquare$

Interference Channel Rate Region

Visualise the achievable rate region for the two-user symmetric Gaussian interference channel. The plot shows the TIN (treating interference as noise) achievable rates, the Han-Kobayashi inner bound, and the outer bound. Adjust the SNR and INR to observe transitions between interference regimes: at low INR, TIN is near-optimal; at high INR, decoding interference is optimal.

Parameters

SNR (dB)20

INR (dB)10

Example: Identifying Interference Regimes

A two-cell system has $P_1 = P_2 = 20$ dB SNR. Compute the achievable sum rate for three scenarios:

(a) INR = 0 dB (weak interference, $\alpha = 0$ ). (b) INR = 20 dB (moderate interference, $\alpha = 1$ ). (c) INR = 40 dB (very strong interference, $\alpha = 2$ ).

Solution

Weak interference

(a) $\text{SNR} = 100$ , $\mathrm{INR} = 1$ . TIN: $R_k = \frac{1}{2}\log_2(1 + 100/2) = 2.87$ bits. Sum rate: $5.74$ bits/c.u. (Near interference-free: $\frac{1}{2}\log_2(101) = 3.33$ .)

Moderate interference

(b) $\text{SNR} = 100$ , $\mathrm{INR} = 100$ . TIN: $R_k = \frac{1}{2}\log_2(1 + 100/101) = 0.50$ bits. Sum rate (TIN): $1.00$ bits/c.u.

Decoding interference: $R_k = \frac{1}{2}\log_2(1+100) = 3.33$ bits, but subject to sum-rate constraint $R_1 + R_2 \leq \frac{1}{2}\log_2(1+200) = 3.82$ bits.

HK (optimal split): sum rate $\approx 3.5$ bits/c.u. Huge improvement over TIN.

Very strong interference

(c) $\text{SNR} = 100$ , $\mathrm{INR} = 10{,}000$ . Decode interference: each user achieves single-user capacity. $R_k = \frac{1}{2}\log_2(101) = 3.33$ bits. Sum rate: $6.66$ bits/c.u.

Paradoxically, very strong interference is easier than moderate interference because each receiver can cleanly decode and remove the interfering signal. $\blacksquare$

Quick Check

For the two-user Gaussian interference channel, why is the capacity region still unknown in general?

Because the channel model is too complex to analyse mathematically

Because the best known inner bound (Han-Kobayashi) and outer bound do not match for all parameter values

Because the interference channel has infinitely many users

Because dirty-paper coding cannot be applied to the interference channel

Correction:

Because the best known inner bound (Han-Kobayashi) and outer bound do not match for all parameter values

The capacity region of the general two-user IC is unknown because the best inner bound (Han-Kobayashi, 1981) and the best outer bound do not coincide for all interference levels. They match in the strong/very strong regime and are within 1 bit for all regimes (Etkin-Tse-Wang, 2008), but the exact capacity in the moderate interference regime remains open. The IC is fundamentally harder than the MAC or BC because neither transmitter knows the other's message, and neither receiver needs to decode the other's message.

Common Mistake: Always Decoding Interference

Mistake:

Assuming that decoding interference is always better than treating it as noise — i.e., applying the strong-IC strategy in the weak interference regime.

Correction:

Decoding interference is optimal only when the interference is strong enough that each receiver can reliably decode the other user's message ( $\mathrm{INR} \geq \text{SNR}$ ). In the weak interference regime ( $\mathrm{INR} < \text{SNR}$ ), attempting to decode the interferer's message wastes rate: the receiver cannot reliably decode it, and the rate constraints from the MAC-like decoding become binding. TIN is approximately optimal in the weak regime (Geng and Nair, 2014). The ETW result shows that the simple HK scheme with message splitting handles the transition between regimes within 1 bit of capacity.

Multiuser Channel Capacity Summary

Channel	Capacity Known?	Optimal Strategy	Sum Capacity/DoF
Gaussian MAC	Yes (exact)	Random coding + SIC	$\frac{1}{2}\log(1 + (P_1+P_2)/N)$
Degraded Gaussian BC	Yes (exact)	Superposition coding	$\frac{1}{2}\log(1 + P/N_1)$
MIMO BC	Yes (exact)	DPC (MAC-BC duality)	$d_\Sigma = \min(n_t, K)$
Gaussian IC (strong)	Yes (exact)	Decode both messages	Intersection of two MACs
Gaussian IC (general)	Within 1 bit	Han-Kobayashi	$d_\Sigma = K/2$ (IA)
Gaussian Relay	Unknown	DF/CF (bounds)	$d = 1$ (no DoF gain)

Treating Interference as Noise (TIN)

A decoding strategy where the receiver ignores the structure of the interfering signal and treats it as additional Gaussian noise. Optimal (to within a constant gap) in the weak interference regime.

Related: Han-Kobayashi Scheme

Han-Kobayashi Scheme

The best known achievable scheme for the interference channel. Each transmitter splits its message into a common part (decoded by both receivers) and a private part (decoded only by the intended receiver). The rate region is the closure of the convex hull over all power splits and time-sharing.

Interference Channel