PaperlayerView exact revision on arXiv

Source-linked AI summary

Gaussian Interference Channel Capacity to Within One Bit

Raul Etkin, David Tse, Hua Wang

arXiv:cs/0702045v2cs.IT

TL;DR

Existing strategies can be sub-optimal because they either lose degrees of freedom or treat structured interference as noise. The paper derives a new outer bound and uses a simplified Han–Kobayashi strategy, obtaining capacity approximations within one bit or half the capacity region in supported regimes.

  • Problem

    Existing strategies can be sub-optimal because one loses degrees of freedom or treats structured, informative interference as pure noise.

  • Method

    The paper derives a new outer bound and uses a simple Han–Kobayashi scheme that makes visible interference common and weaker interference private.

  • Results

    The scheme is within half of the capacity region in the stated Gaussian interference-channel regimes, including weak interference and INR1 ≥ SNR2, INR2 < SNR1, while one-bit approximation results hold in the high SNR, INR regime.

  • Takeaways & Limitations

    A simple Han–Kobayashi strategy can closely approximate capacity without optimizing over all possible Han–Kobayashi strategies.

  • Takeaways & Limitations

    The strategy remains approximate because interference below the noise level retains some visibility, leaving up to a one-bit gap to capacity.

Abstract

from arXiv · show

The capacity of the two-user Gaussian interference channel has been open for thirty years. The understanding on this problem has been limited. The best known achievable region is due to Han-Kobayashi but its characterization is very complicated. It is also not known how tight the existing outer bounds are. In this work, we show that the existing outer bounds can in fact be arbitrarily loose in some parameter ranges, and by deriving new outer bounds, we show that a simplified Han-Kobayashi type scheme can achieve to within a single bit the capacity for all values of the channel parameters. We also show that the scheme is asymptotically optimal at certain high SNR regimes. Using our results, we provide a natural generalization of the point-to-point classical notion of degrees of freedom to interference-limited scenarios.

1 Introduction

The two-user Gaussian interference channel asks how two uncoordinated links should share a common medium while balancing their simultaneously achievable rates. This long-standing capacity problem motivates a simplified Han–Kobayashi scheme, new outer bounds, and a degrees-of-freedom characterization across interference regimes.

  • Motivation: Two common approaches—orthogonalizing links or treating interference as noise—can be suboptimal because they respectively waste degrees of freedom or ignore structure in interference.Orthogonalization loses degrees of freedom a priori, while treating interference as pure noise can fail to exploit information carried by the interfering signal.
  • Problem: The capacity region describes all simultaneously achievable rate pairs and has remained open for over thirty years outside strong interference.The Han–Kobayashi strategy splits each user's information into private and common parts, but optimizing its many power splits and time-sharing choices is complicated.
  • Main result: 1 bit/s/Hz: a simple Han–Kobayashi type scheme achieves the rate pair (R1 −1, R2 −1) for any point in the capacity region.The result holds for all channel parameters and is especially relevant at high SNR, where rates grow unbounded as noise decreases.
  • Scheme: Private-message power is set so that the private interference reaches the other receiver at approximately the Gaussian-noise level.This keeps cross-link interference small while allowing substantial private information when the direct gain exceeds the cross gain.
  • Outer bounds: New outer bounds are needed because existing one-sided-interference bounds can be arbitrarily loose in some parameter regimes.The paper derives additional bounds to cover parameter ranges where the previous bound is insufficiently tight.
  • Capacity regimes: Five regimes exhibit qualitatively different symmetric-capacity behavior, with the first three corresponding to weak interference and the last two to strong or very strong interference.In weak interference, treating interference as noise is optimal only when interference is very weak; partial decoding can improve performance otherwise, and capacity need not decrease monotonically with INR.
  • Generalized degrees of freedom: The results generalize degrees of freedom to interference-limited links by quantifying how mutual interference reduces useful communication dimensions.The generalized degrees of freedom are compared with orthogonalization and treating interference as noise; both baselines are strictly suboptimal over stated parameter ranges.

2 Model

The model is a two-user Gaussian interference channel with two transmitter-receiver pairs communicating over interfering links. Its capacity region is defined through asymptotically reliable code sequences under power constraints.

  • The channel has two transmitter-receiver pairs, each transmitter communicating with its corresponding receiver.The channel is represented by input-output equations, with each transmitter subject to an average power constraint and independent Gaussian noise at the receivers.
  • The channel is parameterized by each user’s signal-to-noise ratio and the other user’s interference-to-noise ratio.For user i, SNR_i = |h_ii|^2P_i/N_0, while INR_1 = |h_21|^2P_2/N_0 and INR_2 = |h_12|^2P_1/N_0.
  • A code consists of message-indexed codewords satisfying average power constraints and decoding functions that estimate each transmitted message from the channel outputs.For block length n, user i has 2^nR_i codewords, and receiver i decodes from its n observed outputs.
  • A rate pair is achievable when a sequence of codebook pairs and decoding functions has error probabilities for both users tending to zero as block length grows.The achievable-rate definition requires codewords to satisfy the respective power constraints P_1 and P_2.
  • The capacity region is the closure of all achievable rate pairs.

3 Symmetric Gaussian Interference Channel

A fixed Han–Kobayashi scheme sets private-message interference at the noise level and achieves rates within one bit/s/Hz of capacity across the symmetric channel. New outer bounds repair arbitrarily loose existing bounds, while the resulting characterization identifies distinct interference regimes and generalized degrees of freedom.

  • 3.2 A simple communication scheme: INRp = 1 balances a large private-message rate against limited interference at the other receiver.Reducing private-message power allows common interference to be decoded and subtracted while preserving substantial direct-link private information.
  • 3.2 A simple communication scheme: 2/3 < α < 1 activates the MAC sum-rate constraint (5), while 0 < α < 2/3 activates constraint (6), with an additional split at α = 1/2.The first max-term is active for 1/2 < α < 2/3, and the second for 0 < α < 1/2.
  • 3.3 Known upper bounds: Existing genie-aided outer bounds are arbitrarily loose in B2, whereas the new bound is within 1 bit/s/Hz of the achievable symmetric rate there.In B2, the genie releases the active constraint (6), explaining why the older bound fails; the new bound restores a finite gap.
  • 3.4 A new upper bound: 1 bit/s/Hz is the maximum gap between the simple scheme and symmetric capacity for all INR values.For INR ≥ 1, the new bounds give the one-bit result directly; for INR < 1, the single-user capacity supplies the upper bound.
  • 3.6 Generalized degrees of freedom: The weak-interference capacity has five qualitative regimes: treating interference as noise is optimal when interference is very weak, while partial decoding improves performance in regimes 2 and 3.The capacity in the first three regimes follows from the new results; regimes 4 and 5 follow from previous results.

4 Within One Bit of the General Capacity Region

The general Gaussian interference channel is divided into weak, mixed, and strong regimes according to cross-link and direct-link strengths. The paper targets within-one-bit characterization for weak and mixed channels, while strong-interference capacity is already known.

  • Channel regimes: The analysis partitions the channel into weak, mixed, and strong interference regimes.The regimes are defined by comparing INR1 with SNR2 and INR2 with SNR1.
  • Weak interference channel: Weak interference satisfies INR1 < SNR2 and INR2 < SNR1.
  • Mixed interference channel: Mixed interference has one cross-link at least as strong as the corresponding direct link and the other cross-link weaker.Its two equivalent parameter conditions are given explicitly by the paper.
  • Strong interference channel: Strong interference satisfies INR1 ≥SNR2 and INR2 ≥SNR1, and its capacity region is already known.
  • Scope: The paper shows that weak and mixed interference capacity regions can be approached within one bit.

4.1 Outer bound on the capacity region of the Gaussian interference channel

Existing capacity outer bounds can be arbitrarily loose, so the paper derives new bounds for weak and mixed Gaussian interference channels. These bounds use genie-aided constructions and are organized around individual, sum-rate, and weighted-sum-rate constraints.

  • Motivation: Existing outer bounds can be arbitrarily loose, motivating new bounds for weak and mixed interference channels.
  • Weak interference: For weak interference, the paper states an outer bound containing rate, sum-rate, and weighted-sum-rate constraints.The weak-channel condition is INR1 < SNR2 and INR2 < SNR1.
  • Genie-aided derivation: Genie-aided receivers provide side information such as x2, x1, s1, and s2 to derive the outer-bound constraints.The constructions include one-sided channels and duplicated receivers for bounding 2R1 + R2 or R1 + 2R2.
  • Weak interference: The weak-channel weighted-sum bounds include 2R1 + R2 ≤ log (1 + SNR1 + INR1) + log (1 + INR2 + SNR2).
  • Mixed interference: The mixed-channel outer bound replaces unavailable weak-interference constraints while retaining bounds whose derivations still satisfy INR2 < SNR1.For the violated INR1 < SNR2 condition, the proof uses a strong-interference one-sided-channel sum-rate bound and a new genie-aided construction.

4.2 Achievable scheme

The paper uses a simplified Han-Kobayashi scheme parameterized by fixed private-message power levels, avoiding the general scheme’s need to optimize over all power splits and time sharing. The resulting fixed-split regions remain close to the full achievable region.

  • Han-Kobayashi formulation: Han-Kobayashi is the best known achievable strategy, but evaluating its general region requires many power splits and time-sharing strategies.
  • Scheme structure: The simplified scheme uses Gaussian common and private messages under distributions that factor through the time-sharing variable q.The common information can be decoded at both receivers, while q represents time sharing.
  • Power selection: The private-message powers are chosen through the interference-to-noise ratios INRp2 and INRp1 at the unintended receivers.These parameters satisfy 0 ≤INRp2 ≤INR2 and 0 ≤INRp1 ≤INR1.
  • Fixed power splitting: With fixed power splitting and no time sharing, the scheme is denoted HK(INRp2, INRp1), with achievable region R(INRp2, INRp1).
  • Relation to general region: Fixed-split regions are subsets of the general Han-Kobayashi region, whose inclusion can be strict when varying power allocations and time sharing.

4.3 Within one bit of the capacity region

The paper defines within-one-bit approximation and proves that carefully selected fixed-split Han-Kobayashi regions achieve it for weak and mixed interference. The proof compares these achievable regions with the new outer bounds across parameter cases.

  • Definition and proof strategy: An achievable region is within one bit when every capacity-region rate pair reduced by one bit in each coordinate is achievable.
  • Definition and proof strategy: The proof compares fixed-split Han-Kobayashi regions against the new outer bounds by bounding coordinate and weighted-sum-rate gaps.
  • Weak interference: For weak interference, the paper verifies the one-bit gap across four private-power cases, including R(1,1), R(1,INR1), R(INR2,1), and R(INR2,INR1).The last region corresponds to treating the other user’s signal as noise.
  • Weak interference: The weak-interference achievable region is within one bit of capacity for all SNR1, SNR2, INR1, and INR2 satisfying INR1 < SNR2 and INR2 < SNR1.

4.4 Discussion on one-bit result

The paper shows that simplified Han–Kobayashi strategies approximate the Gaussian interference-channel capacity region within a constant gap, with especially strong relevance at high SNR and INR.

  • Regime interpretation: The one-bit approximation is particularly meaningful in high-SNR, high-INR regimes, while a one-bit loss can be large relative to rates at low SNR and INR.In the high-SNR, high-INR regime, user rates grow and one bit is relatively small.
  • Complementary approximation: The achievable region obtained by treating interference as noise is within half of the capacity region of the Gaussian weak interference channel.Treating interference as noise is a special case of the Han–Kobayashi scheme.
  • Parameter-specific result: Theorem 8 establishes a half-capacity approximation when INR1 ≥ SNR2 and INR2 < SNR1.The proof compares the achievable region with the corresponding outer bound.
  • Strategy simplification: Choosing private-message powers so that INRp is close to 1 provides a simple, effective Han–Kobayashi strategy without optimizing over all message splits.The paper emphasizes that little is lost by this simplification.

5 Generalized Degrees of Freedom Region

The paper extends degrees of freedom from point-to-point channels to interference-limited settings by retaining first-order logarithmic terms in the channel parameters. It derives generalized degrees-of-freedom regions for several Gaussian interference-channel regimes and compares strategies through those regions.

  • Definition and approximation: First-order capacity expansions have O(1) higher-order errors, so their relative error vanishes as SNR1 tends to infinity.These expansions support the generalized degrees-of-freedom analysis.
  • Definition and approximation: Generalized degrees of freedom scale each user’s interference-free rate, approximately log SNRi, by an interference-dependent factor di.The resulting region describes how interference affects communication.
  • General channel classes: For weak and mixed interference channels, first-order expansions of inner and outer bounds coincide, yielding generalized degrees-of-freedom regions.The weak-interference region is represented by inequalities including 2d1 + α1d2 and d1 + 2α1d2.
  • Symmetric channel: In the symmetric channel, the generalized degrees-of-freedom region is not monotonically decreasing with INR in the weak-interference regime.For α ≥ 2, the region corresponds to very strong interference, where interference does not reduce available degrees of freedom.
  • Symmetric channel: Orthogonalization is strictly suboptimal except at α = 1/2 and α = 1, while treating interference as noise is strictly suboptimal except for α ≤ 1/2.These comparisons are shown for the symmetric channel’s generalized degrees-of-freedom region.
  • One-sided channel: For the weak one-sided interference channel, the derived first-order achievable region is tight, whereas orthogonalization is suboptimal in both cases.Different corner points require either power adjustment with noise treatment or a private-common message split.

6 Private versus common information

The paper explains the simplified Han–Kobayashi split by assigning visible interference above the other receiver’s noise level to common information and hidden interference below it to private information. Decoding-order flexibility then creates gains unavailable when all interference is treated as noise.

  • Power split: Setting private-message powers so that INRp1 = 1 and INRp2 = 1 achieves within 1 bit/s/Hz of capacity and balances direct-link rate against induced interference.This choice keeps private interference near the other receiver’s Gaussian-noise level.
  • Differential-rate view: Differential rates r1(z) and r2(z) measure the marginal rate from a sub-message of power dz under interference levels z·SNR1 and z·INR2.They identify which signal levels favor private or common decoding.
  • Differential-rate view: When INR2·z ≪ 1, information should be private because the direct-link marginal rate exceeds the indirect-link rate; when INR2·z ≫ 1, it should be common.At high interference levels, r1(z) and r2(z) are approximately equal and scale as 1/z.
  • Decoding-order flexibility: Signal components above the other receiver’s noise level can be treated as common information, allowing decoding-order changes that improve one user’s rate while preserving the other’s.An ε-order swap raises c1’s rate from R to R + δ while receiver 2 can still decode it.
  • Decoding-order flexibility: Treating interference entirely as noise leaves exploitable structure unused because private-message decoding has fixed order and cannot exploit slack at one receiver.Viewing visible interference as common information exposes flexibility in the decoding order.

7 Connection to a Deterministic Interference Channel

The Gaussian analysis is connected to a deterministic interference channel where parts of interfering signals can be cleanly observed or completely hidden. This analogy motivates assigning visible components to common information and invisible components to private information.

  • Gaussian connection: The Gaussian strategy’s one-bit gap reflects that below-noise interference remains partially visible, unlike the completely invisible private component in the deterministic model.The above-noise common/below-noise private division is therefore only approximate.
  • Common and private information: Because part of each deterministic signal is invisible to the non-intended receiver, that part becomes private information while the observable interference is common information.This split is exactly optimal for the cited deterministic channel.
  • Deterministic model: The deterministic model assumes interference signals satisfy conditions enabling each receiver to observe a clean interfering signal after decoding its own message.These conditions support the capacity-region derivation.
  • Gaussian connection: In the Gaussian channel, s1 = h12x1 + z2 and s2 = h21x2 + z1 play analogous roles as common information observable after decoding the intended message.The Gaussian noise terms hide private information from the non-intended receiver.
  • Deterministic model: In the deterministic channel, outer bounds can be interpreted as genie-aided channels that provide combinations of inputs and interference signals to receivers.Analogous genie-aided channels are used for Gaussian weak and mixed interference outer bounds.

Appendix A: Analysis of upper bound of [6] Theorem 2

The appendix evaluates an existing symmetric-rate upper bound against the paper’s simple Han–Kobayashi scheme, finding a bounded 1 bit/s/Hz gap in B1 but an unbounded gap in B2.

  • Parameter range B2: In B2, the gap between the upper bound and the scheme can be arbitrarily large.Choosing INR = SNR makes the relevant difference diverge as SNR tends to infinity.
  • Overall comparison: Thus, Theorem 2 of does not characterize symmetric capacity more tightly than bound (12) across these parameter ranges.The appendix explicitly compares the two bounds in terms of symmetric-capacity characterization.
  • Normalization and specialization: Theorem 2 of is specialized to the complex symmetric interference channel using normalized channel parameters.The specialization replaces |hc|^2 with |hc|^2/|hd|^2 and P with |hd|^2P/N0, under 0 < INR < SNR.
  • Parameter range B1: 1 bit/s/Hz is attainable as the worst-case difference when INR = SNR^3/4 and SNR tends to infinity.For this choice, RUB1 − RHK1 approaches 1 as SNR approaches infinity.
  • Parameter range B1: In B1, the simple Han–Kobayashi scheme differs from the upper bound by at most 1 bit/s/Hz.B1 is the range where the first term of the minimum in (7) is active.
Loading cs/0702045v2…