PaperlayerView exact revision on arXiv

Source-linked AI summary

Lattice Strategies for the Dirty Multiple Access Channel

Tal Philosof, Ram Zamir, Uri Erez, Ashish Khisti

arXiv:0904.1892v1cs.IT

TL;DR

The paper asks how a multiple access channel behaves when each transmitter knows a different additive interference that the receiver does not know. It compares Costa-style random binning with lattice strategies and finds that lattice methods preserve positive rates under strong interference, are optimal at high SNR, and also handle helper and common-interference variants.

  • Problem

    The paper studies a Gaussian multiple access channel with two separate interferences known non-causally to the transmitters but unknown to the receiver.

  • Method

    The paper compares Costa-style random-binning strategies with one- and high-dimensional lattice strategies for doubly dirty, single-dirty-user, and common-interference MACs.

  • Results

    Lattice strategies achieve positive rates under strong interference and are asymptotically capacity achieving at high SNR, while the Costa-style strategy achieves no positive rates in the strong-interference limit.

  • Takeaways & Limitations

    Lattice coding can be superior to known random-binning techniques for dirty multiple access channels and can achieve capacity in identified high-SNR and common-interference settings.

Abstract

from arXiv · show

A generalization of the Gaussian dirty-paper problem to a multiple access setup is considered. There are two additive interference signals, one known to each transmitter but none to the receiver. The rates achievable using Costa's strategies (i.e. by a random binning scheme induced by Costa's auxiliary random variables) vanish in the limit when the interference signals are strong. In contrast, it is shown that lattice strategies ("lattice precoding") can achieve positive rates independent of the interferences, and in fact in some cases - which depend on the noise variance and power constraints - they are optimal. In particular, lattice strategies are optimal in the limit of high SNR. It is also shown that the gap between the achievable rate region and the capacity region is at most 0.167 bit. Thus, the dirty MAC is another instance of a network setup, like the Korner-Marton modulo-two sum problem, where linear coding is potentially better than random binning. Lattice transmission schemes and conditions for optimality for the asymmetric case, where there is only one interference which is known to one of the users (who serves as a "helper" to the other user), and for the "common interference" case are also derived. In the former case the gap between the helper achievable rate and its capacity is at most 0.085 bit.

I. INTRODUCTION

The paper studies a Gaussian multiple access channel with separate non-causal interference knowledge at the transmitters and compares Costa-style random binning with lattice strategies. It shows that lattice methods retain positive rates under strong interference, can be capacity-achieving at high SNR, and extend to asymmetric and common-interference settings.

  • The model has two additive interferences, each known non-causally to its respective transmitter but unknown to the receiver, with user power constraints P1 and P2.The channel is represented as Y = X1 + X2 + S1 + S2 + Z.
  • Lattice strategies achieve positive rates under strong interference, whereas the Costa-style random-binning generalization achieves no positive rates in that limit.This contrast motivates lattice precoding for the doubly dirty MAC.
  • At high SNR and sufficiently large lattice dimension, lattice strategies are asymptotically optimal and capacity achieving.The paper identifies high SNR as a condition under which lattice transmission reaches capacity.
  • The paper frames the dirty MAC as a setting where linear coding can outperform known random-binning techniques, paralleling the Korner–Marton problem.The comparison concerns achievable coding strategies rather than a general replacement of random binning.
  • The paper also analyzes the single-dirty-user helper setting, where the informed user assists the other transmitter using lattice-based transmission that is optimal at high SNR.The single-dirty-user case is treated separately rather than as a degeneration of the strong-interference doubly dirty MAC.
  • For common interference known to both users, the capacity region equals that of the clean Gaussian MAC, and lattice strategies achieve this region.This completes the paper’s treatment of full and partial non-causal interference knowledge.

B. The Gaussian Model

The Gaussian models include doubly dirty, single-dirty-user, helper, and common-interference MACs with noncausal transmitter-side interference knowledge. For strong interference, the paper derives outer bounds on their capacity regions, including a bound that contradicts the clean-MAC capacity conjecture.

  • Doubly dirty MAC: The doubly dirty Gaussian MAC is Y = X1 + X2 + S1 + S2 + Z, with independent interferences known noncausally to their respective transmitters and power constraints P1 and P2.Strong interference means arbitrary interference sequences or independent Gaussian interferences with variances tending to infinity.
  • Single dirty user and helper problem: The single-dirty-user model gives user 1 noncausal knowledge of S1, while user 2 is uninformed; the helper problem sets user 1's message rate to zero.The informed user can instead assist the uninformed user's transmission without sending its own information.
  • Common interference: The common-interference MAC has one interference Sc known noncausally to both encoders.This completes the framework spanning full and partial noncausal interference knowledge.
  • Outer bounds: Theorem 1 places the strong-interference single-dirty-user capacity region inside an outer bound, with separate cases for P1 ≤ P2 and P1 > P2.The corresponding bounds are depicted in Figures 4 and 5, and the helper rate is bounded by the specialized corollary.
  • Outer bounds: The doubly dirty MAC capacity region is contained in the intersection-based outer bound for strong independent interference, and this bound contradicts the conjecture that its capacity equals the clean MAC.The same sum-rate bound also upper-bounds common-message capacity.

IV. LATTICE BASED TRANSMISSION

The paper develops a general lattice-based transmission scheme for Gaussian dirty MACs using lattices, Voronoi regions, dithers, and modulo operations. Its main advantage is robustness: achievable rates do not depend on the exact interference distributions and therefore apply to arbitrary interference sequences.

  • Lattice operations: Modulo-lattice operations and nearest-neighbor quantization provide the algebraic structure used to combine lattice codewords while satisfying the transmission constraints.The modulo operation obeys a distributive property that supports the scheme's additive structure.
  • General scheme: The general lattice transmission scheme assigns user-specific scaling parameters, lattice choices, and an auxiliary lattice whose settings vary across channel scenarios.The scheme is presented as a common framework for the doubly dirty MAC and single-informed-user cases.
  • Canonical transmission scheme: The canonical scheme uses separate lattices and Voronoi regions for the two users, with uniformly distributed information-bearing points and independent receiver-known dither signals.The dithers make each transmitted signal uniform over its corresponding Voronoi region while preserving the power constraints.
  • Robustness: The lattice scheme's achievable rates are insensitive to the exact interference distributions, unlike the random-binning technique.This robustness makes the construction suitable for arbitrary interference sequences.

V. THE GAUSSIAN DOUBLY DIRTY MAC

For the doubly dirty Gaussian MAC, Costa-style random binning can lose all positive rates under strong interference, whereas periodic and high-dimensional lattice strategies retain positive rates. The paper shows lattice strategies are optimal in some regimes, including high SNR.

  • Random binning: Costa-style random binning achieves no positive rates as the independent interference variances tend to infinity.This failure occurs for the natural two-user extension of Costa's auxiliary random variables.
  • One-dimensional lattice strategies: Periodic auxiliary variables Ui = [Xi + αiSi + Di] mod ∆i yield positive rates despite strong interference.The construction is equivalent to a one-dimensional lattice strategy in the causal-strategy sense.
  • High-dimensional lattice strategies: High-dimensional lattice strategies are optimal for the doubly dirty MAC in some cases, including the high-SNR regime.The paper states that these strategies are capacity achieving in the high-SNR limit.
  • Capacity characterization: The high-SNR capacity region under strong interference is characterized by rate pairs satisfying the theorem's stated bounds.The result holds in the limit of strong interferences and as min{P1, P2} tends to infinity.
  • Transmission and decoding: The lattice construction reduces the received signal modulo a common lattice to Y′ = [V1 + V2 + Z] mod Λ, producing an equivalent additive modulo MAC.The achievable sum rate then follows from the modulo-channel analysis and lattices good for quantization.

B. Lattice Strategies for General SNR

Lattice strategies yield achievable rate regions for the doubly dirty MAC across SNR regimes, with asymptotic optimality at high SNR and a uniformly small gap to capacity.

  • High-SNR optimality: At high SNR, lattice strategies are asymptotically optimal and meet the outer bound in the strong-interference limit.The achievable region coincides with the outer bound in the stated high-SNR regime.
  • Transmission scheme: The lattice transmission scheme uses independent dithers and reduces the channel to an equivalent modulo-Λ MAC with effective noise independent of the messages.The equivalent channel is V1 + V2 + Zeq, with Zeq independent of V1 and V2.
  • Achievable region: The achievable rate sum is derived from the effective modulo channel and extended by time sharing and upper convexification over the power constraints.The construction satisfies the power constraints through dithered lattice signals.
  • Low-SNR behavior: At low SNR, pure lattice strategies achieve no positive rate for SNR ≤ 1/2, so time sharing is required.The time-sharing threshold is numerically SNR* ≈ 1.655.
  • Gap to capacity: At vanishing SNR, the inner and outer bounds scale as 0.425·P/N and 0.721·P/N, respectively, leaving a gap of approximately 2.3 dB.The rate-sum comparison is for the symmetric case P1 = P2.
  • Gap to capacity: For arbitrary power constraints, the gap is maximized in the symmetric case and is uniformly bounded at equality when P1 = P2 and P/N ≈ 1.155.The maximizing point follows from x* − 0.5 ≈ 1.155.

VI. THE GAUSSIAN MAC WITH A SINGLE DIRTY USER

For the MAC with one informed user, lattice strategies provide helper and rate-region bounds, attain capacity at high SNR, and require time sharing to improve low-SNR performance.

  • Transmission scheme: The general helper construction uses lattice sequences good for both quantization and AWGN channel decoding, with dithers and MMSE factors.The scheme is developed as a special case of the canonical lattice strategy.
  • Helper problem: When N ≤ |P1 − P2|, the helper capacity is characterized in the strong-interference limit.This is the complementary power-imbalance regime to |P1 − P2| < N.
  • Helper problem: At high SNR and |P1 − P2| < N, the lattice-based helper rate asymptotically meets the outer bound.The helper capacity is characterized with an o(1) term as P1 and P2 grow for fixed N.
  • Low-SNR behavior: At low SNR, pure lattice strategies are suboptimal because time sharing strictly increases the achievable helper rate.For SNR → 0, the time-shared inner bound scales as O(SNR), whereas the pure-lattice bound scales as O(SNR^2).

B. Capacity Region at High SNR

For the MAC with a single dirty user, lattice strategies characterize the high-SNR capacity region across power-imbalance regimes and identify boundary points achievable on the outer bound.

  • High-SNR capacity: At high SNR in the strong-interference limit, the capacity region of the MAC with a single informed user is characterized.The characterization holds as P1 and P2 tend to infinity.
  • Achievable region: The resulting achievable region includes the helper rate for arbitrary powers and the capacity region at high SNR.The region can also be obtained using random binning.
  • Power-imbalance regimes: When P1 ≤ P2 − N, time sharing between a point-to-point dirty-paper rate and the helper point achieves the outer bound.The corresponding capacity region is stated for this regime.
  • Power-imbalance regimes: When P1 > P2 − N, a lattice-achievable rate pair lies on the boundary of the capacity region.The boundary behavior is illustrated across the regimes P2 − N < P1 ≤ P2, P2 < P1 ≤ P2 + N, and P2 + N < P1.
  • Gap to capacity: At the helper point, the maximal gap between the inner and outer bounds is log2(3) − 3/2 ≈ 0.085 bit.This point is identified as the location where the gap is maximal.

VII. THE GAUSSIAN MAC WITH COMMON INTERFERENCE

With common interference known to both transmitters, lattice strategies recover the clean Gaussian MAC capacity region by sequentially decoding the users’ information-bearing lattice signals.

  • Capacity region: The dirty MAC with common interference has the same capacity region as the interference-free Gaussian MAC.The region is the clean-MAC pentagon.
  • Comparison with dirty-paper coding: Writing on dirty paper for each user provides the individual clean-MAC rates, while the lattice scheme supplies the joint corner-point construction.The residual common interference is incorporated into the successive decoding procedure.
  • Lattice construction: Lattice strategies achieve a corner point of the clean-MAC pentagon by using two lattices with second moments P1 and P2.The construction targets a corner with rates involving log2(1 + P1/N) and log2(1 + (P1 + P2)/N).
  • Lattice construction: Independent dithers make the information-bearing vectors independent of the transmitted lattice signals and ensure that the power constraints are satisfied.The dither quantization property underlies both claims.
  • Decoding: The decoder reconstructs the users’ information through three stages: decode user 1, estimate the effective noise, then decode user 2.A symmetric procedure obtains the other corner point by reversing the decoding order.

VIII. EXTENSIONS

The extensions cover correlated and common-interference MACs, symmetric K-user channels, and asymmetric helper settings. Lattice schemes achieve capacity in several cases and maintain bounded rate loss in the K-user extension.

  • Correlated interferences: The correlated-interference model decomposes the channel into two private Gaussian interferences and one common interference known non-causally at both encoders.
  • Correlated interferences: For strong correlated interferences with correlation magnitude below one, the correlated-interference capacity region equals both the common-interference and doubly dirty MAC capacity regions.
  • K-user extension: The symmetric K-user extension has independent interferences known non-causally only to their respective encoders, with equal power constraints and a stated strong-interference outer and achievable region.
  • K-user extension: The K-user rate loss between the outer and inner bounds is bounded by 1/2 bit for every K, although the relevant factor inside the logarithm decreases with K.
  • Scope and comparison: Distributed channel-state knowledge need not incur only a limited rate loss: in a multiplicative-interference model, strong interferences leave decoder uncertainty unresolved for any input set.
  • Asymmetric and common interference: The paper derives outer bounds and lattice schemes for asymmetric helper and common-interference cases, with lattice strategies meeting the outer bound under sufficient conditions.

APPENDIX I

The appendix develops lattice constructions for helper and asymmetric dirty-MAC rate points. These constructions use nested, quantization-good lattices and time sharing to achieve outer-bound regions under power-dependent conditions.

  • Helper case: When P1 < P2, the achievable rate for the complementary single-user point and time sharing between the two points recover the outer-bound region under the stated conditions.
  • Lattice constructions: Nested lattice constructions cancel interference through modulo operations, while quantization-good lattices yield the stated achievable rates for selected single-user rate points.
  • Power constraints: The asymmetric scheme restricts user powers when a lattice term must disappear after modulo reduction, making the power relationship part of the achievability condition.
  • Helper case: When P1 ≥ P2, the construction achieves the outer bound for the corresponding helper rate under the stated power conditions.

APPENDIX III

This appendix characterizes an upper-convex-envelope optimization used in the rate analysis. The maximizing point is obtained numerically at x* approximately 1.655.

  • Convexification: Because [f(x)]+ is not convex, its upper convex envelope is achieved by time sharing between x = 0 and x = x*.
  • Optimization: The optimizing point satisfies the defining equation for x* and evaluates numerically to x* ≈ 1.655.
  • Optimization: Since γ(x) decreases with x, γ(x) is maximized at x = x*.

APPENDIX IV

The appendix establishes lattice achievability for boundary points in the asymmetric dirty MAC using quantization- and AWGN-good lattices. The resulting inner bound meets the outer bound in specified power regimes, while the worst-case gap is bounded through a symmetric-power analysis.

  • Lattice construction: The constructions use lattices that are good for both quantization and AWGN channel coding, with dithering and modulo decoding producing equivalent channels.
  • Boundary achievability: For P2 = P1 + N, the lattice inner bound meets the outer bound, and for P2 ≥ P1 + N the outer bound reduces to 1/2 log2(1 + P1/N).
  • Boundary achievability: For P1 = P2 + N, the corresponding lattice construction also meets the outer bound and achieves 1/2 log2(1 + P2/N).
  • Proof completion: The proof takes the limit n → ∞ so the lattice approximation error ε tends to zero, and time sharing supplies the upper convex envelope.
  • Gap analysis: For fixed P1 with P1 ≤ P2, the gap γ(P1, P2) decreases as P2 increases, and the symmetric-power case bounds the general case by x* = 1/2.

APPENDIX VIII

The appendix develops lattice transmission schemes for different power orderings and shows when their achievable regions meet the outer bound, particularly at high SNR.

  • P1 ≤ P2: For P1 ≤ P2, the lattice-achievable region coincides with the outer bound.
  • P1 > P2: For P1 > P2, nested lattices with second moments P1 and P2 support successive decoding of V1 and V2.The decoder first decodes V1 while treating V2 as noise, then subtracts V1 and reduces modulo Λ2 to decode V2.
  • Lattice transmission: The lattice schemes use modulo-lattice equivalent channels to remove the known interference while preserving the users’ information-bearing lattice points.For P1 > P2, the equivalent channel is Y′ = [V1 + V2 + Z − QΛ1(V1 − S1)] mod Λ1.
  • Lattice transmission: The construction assumes nested lattices that are good for both quantization and AWGN channel coding.
  • P1 ≤ P2: At high SNR, time sharing among the lattice-achievable points coincides with the outer bound.The point (R1, 0) = (0.5 · log2(1 + P1/N), 0) is achievable for any SNR.
Loading 0904.1892v1…