PaperlayerView exact revision on arXiv

Source-linked AI summary

Joint Physical Layer Coding and Network Coding for Bi-Directional Relaying

Makesh Pravin Wilson, Krishna Narayanan, Henry Pfister, Alex Sprintson

arXiv:0805.0012v2cs.IT

TL;DR

The paper addresses reliable bidirectional exchange through a relay over synchronized, power-constrained AWGN channels. It uses structured lattice coding to decode a modulo-lattice sum at the relay, alongside joint MAC decoding at low SNR, and reports near-optimal rates in the corresponding regimes. These schemes, including minimum angle decoding and time sharing, outperform analog network coding across the SNR range.

  • Problem

    Two transmitters need to exchange information through a relay over synchronized AWGN channels, with direct transmitter-to-transmitter communication unavailable.

  • Method

    The paper uses lattice codes and decoding to recover a modulo-lattice sum at the relay, and also considers joint decoding of both MAC transmissions.

  • Results

    Lattice schemes approach the upper bound at high SNR, while joint decoding approaches it at low SNR; time sharing outperforms analog network coding across the SNR range.

  • Takeaways & Limitations

    Structured lattice codes can outperform random-code-based approaches for this networking problem, with minimum angle decoding attaining the lattice scheme's rate.

Abstract

from arXiv · show

We consider the problem of two transmitters wishing to exchange information through a relay in the middle. The channels between the transmitters and the relay are assumed to be synchronized, average power constrained additive white Gaussian noise channels with a real input with signal-to-noise ratio (SNR) of snr. An upper bound on the capacity is 1/2 log(1+ snr) bits per transmitter per use of the medium-access phase and broadcast phase of the bi-directional relay channel. We show that using lattice codes and lattice decoding, we can obtain a rate of 1/2 log(0.5 + snr) bits per transmitter, which is essentially optimal at high SNRs. The main idea is to decode the sum of the codewords modulo a lattice at the relay followed by a broadcast phase which performs Slepian-Wolf coding with structured codes. For asymptotically low SNR's, jointly decoding the two transmissions at the relay (MAC channel) is shown to be optimal. We also show that if the two transmitters use identical lattices with minimum angle decoding, we can achieve the same rate of 1/2 log(0.5 + snr). The proposed scheme can be thought of as a joint physical layer, network layer code which outperforms other recently proposed analog network coding schemes.

I. INTRODUCTION, SYSTEM MODEL AND PROBLEM STATEMENT

The paper studies bidirectional information exchange through a three-node AWGN relay network with orthogonal MAC and broadcast phases. It develops lattice-based and joint-decoding schemes, achieving near-optimal performance in complementary SNR regimes and outperforming analog network coding.

  • System model: Two users exchange information through a relay because they cannot communicate directly, using synchronized AWGN links in a three-node linear network.Communication is divided into multiple-access and broadcast phases.
  • System model: The MAC and broadcast phases use separate time slots, each with n channel uses, and all transmissions have SNR snr = P/σ2.Both user rates are assumed equal.
  • Main results: The exchange capacity is upper bounded because the MAC and broadcast phases each consist of n AWGN channel uses.This establishes the benchmark for the proposed rates.
  • Main results: Lattice coding with lattice decoding achieves an exchange rate that approaches the upper bound at high SNR.The same rate is also achievable without dithering using minimum angle decoding.
  • Main results: Joint decoding of both transmissions achieves an exchange rate that approaches the upper bound at low SNR.This scheme is based on optimal coding for the MAC channel.
  • Main results: Time sharing between lattice decoding and joint decoding outperforms the recently proposed analog network coding scheme across the entire SNR range.Any rate βRex,JD + (1 −β)Rex,Lattice is achievable for 0 ≤β ≤1.

IV. AN OPTIMAL TRANSMISSION SCHEME FOR THE BSC CHANNEL

For the binary symmetric channel, identical linear codes let the relay decode the modulo-2 sum of both codewords, enabling optimal information exchange. This structured-code principle motivates analogous lattice methods for Gaussian channels.

  • BSC transmission scheme: 1 − H(q) is achieved as the exchange rate, matching the BSC exchange-capacity upper bound.After broadcasting the decoded sum, each node uses its own codeword to recover the other.
  • BSC transmission scheme: Linear codes let the relay decode x1 ⊕ x2 as a valid codeword from the same capacity-achieving code.The code's group structure makes the sum decodable at the relay.
  • Structured versus random codes: Random codes cannot generally decode x1 ⊕ x2 at the relay, whereas structured linear codes exploit group structure for this task.The comparison identifies algebraic structure as the key distinction between the schemes.
  • Motivation for lattice coding: Lattices extend the linear-code idea to Gaussian channels because they are closed under real vector addition.The paper introduces lattices as additive subgroups and then develops nested-lattice coding for the relay problem.
  • Nested-lattice scheme: The nested-lattice scheme maps both users' information vectors to fine-lattice points, adds dithers, and lets the relay decode their modulo-coarse-lattice sum.The broadcast phase forwards this decoded function so each node can recover the other user's codeword using its own side information.

B. Achievable rate

The achievable-rate analysis shows that nested lattices can reliably decode the modulo-coarse-lattice sum in the MAC phase and recover each user's codeword after broadcast. The resulting rate approaches the Gaussian exchange upper bound at high SNR.

  • MAC phase: The modulo sum t is uniformly distributed over the fine-lattice codebook because of the lattice's group structure.This property supports treating the decoded sum as a valid codeword for reliable lattice decoding.
  • Achievable rate: Any exchange rate Rex,lattice < 1/2 log(0.5 + P/σ2) is achievable with nested lattices and lattice decoding.The theorem establishes reliable decoding for a sequence of suitable nested lattices as block dimension grows.
  • MAC phase: The relay forms an estimate of t = (t1 + t2) mod Λc and decodes the nearest fine-lattice point.Dithers and an MMSE-scaled received signal produce an equivalent-noise decoding problem.
  • Broadcast phase: Broadcasting the decoded index lets node A compute (t − t1) mod Λc = t2, while node B similarly recovers t1.The broadcast channel supports transmission of the decoded sum, and each node supplies the other codeword as side information.
  • Conclusion: At high SNR, the lattice scheme approaches the upper bound and is therefore nearly optimal.The broadcast stage is interpreted as Slepian-Wolf coding with nested lattices, combined with decode-and-forward of the codeword function.

VII. LATTICE CODING WITH MINIMUM ANGLE DECODING

This section considers minimum angle decoding for lattice codes as an alternative to nested lattice decoding. It is introduced after the preceding lattice-decoding rate analysis.

  • Minimum angle decoding: Minimum angle decoding is studied as a suboptimal decoder after nested lattice decoding achieves the stated lattice-based exchange rate.The supplied passage frames the decoder as an alternative performance question.
  • Minimum angle decoding: The section concerns whether another decoding rule can improve performance over lattice decoding alone.No further result is stated in the supplied passages.

A. Description

The minimum angle decoder uses lattice points from a thin spherical shell to decode the sum of two synchronized transmissions. The construction bounds error by exploiting concentration of lattice-point sums and angular separation.

  • Encoding and target: Each transmitter synchronously selects a lattice point from a power-constrained sphere, and the relay decodes their sum rather than the individual codewords.No nested lattice construction or dither is used in this scheme.
  • Minimum angle decoding: The decoder selects the lattice-sum point whose projection onto a thin spherical shell has the smallest angle to the received vector.The shell has radius approximately √(2P), with a small nonzero width parameter.
  • Achievable rate: An n-dimensional lattice exists for which exchange rates below 1/2 log(1/2 + SNR) are achievable as n approaches infinity.This is the main minimum-angle-decoding theorem for the bi-directional relaying problem.
  • Shell concentration: Blichfeldt’s principle supplies translations whose lattice-point sums concentrate on the shell, enabling the minimum angle analysis.The lattice must also function as a good channel code, supported by the Minkowski-Hlawka argument.
  • Error analysis: The analysis partitions codeword pairs according to whether their sum lies inside the thin shell and bounds the resulting average error probability.Pairs outside the shell contribute a separate error term, while projected shell points are handled by the angular decoder.

D. Relationship with ML decoder

Minimum angle decoding can approximate maximum-likelihood decoding when codewords concentrate on a narrow shell and shell points are sufficiently represented by codewords. The final condition may fail at low SNR, causing suboptimality.

  • Conditions for equivalence: For Gaussian noise, maximum-likelihood decoding is equivalent to minimum-distance decoding.This establishes the first condition supporting the relationship between ML and minimum-angle decoding.
  • Conditions for equivalence: A narrow shell makes minimum-distance comparisons approximately equivalent to comparing angles because codewords have nearly equal distance from the origin.The argument assumes most codewords lie in the thin shell.
  • Shell concentration: Blichfeldt’s principle provides shell concentration, supporting the condition that most relevant codewords lie near the shell surface.The shell width is then allowed to become arbitrarily small, bringing the decoder closer to ML decoding.
  • Low-SNR limitation: At low SNR, not all lattice points in the thin shell may be codewords, so minimum angle decoding can become suboptimal.The theorem gives zero rate for SNR < 1/2, while joint decoding with random Gaussian codebooks can still work in that regime.

VIII. JOINT DECODING BASED SCHEME

The joint-decoding scheme addresses the poor low-SNR performance of the lattice scheme by decoding both messages at the relay before broadcasting their network-coded combination. Time sharing improves rates over an intermediate SNR range.

  • Joint decoding: For P/σ2 < 1/2, joint MAC decoding can recover both users’ messages at the relay before it broadcasts uA ⊕ uB.Any coding scheme optimal for the multiple-access channel can be used for this low-SNR regime.
  • Low-SNR performance: The joint-decoding scheme is asymptotically optimal at low SNR because log(1+snr) approximately equals snr as snr approaches zero.This matches the low-SNR behavior of the exchange-capacity upper bound.
  • Comparison: The proposed schemes outperform analog network coding across the displayed achievable-rate comparison.The paper notes that the proposed approach requires perfect phase synchronization, unlike analog network coding.
  • Time sharing: Time sharing between lattice-based and joint-decoding schemes gives better rates than either individual scheme from -0.659 dB to 3.46 dB.The achievable rate has the form βRex,JD + (1 −β)Rex,Lattice.
  • Scope boundary: Relaxing the equal n-use allocation between MAC and broadcast phases, or changing power sharing, may enable better schemes.The stated results mainly impose exactly n channel uses for each phase.

IX. EXTENSION TO MULTIPLE HOPS

Structured lattice coding extends the exchange scheme to multiple relay hops. The paper claims an achievable rate across finite-hop networks and a growing advantage over amplify-and-forward as hops increase.

  • Network model: The multi-hop model allows each relay and endpoint to transmit only to its two nearest nodes.The network contains L relay hops between nodes A and B.
  • Comparison with amplify-and-forward: The proposed multi-hop scheme has a more pronounced advantage over amplify-and-forward as hop count increases because amplify-and-forward accumulates amplified channel noise.The conclusion attributes the stronger multi-hop advantage to this noise amplification.
  • Packet flow: Packets are forwarded through alternating transmission slots, with relays decoding lattice-point functions of newly transmitted packets.After an initial 2L-slot delay, a new packet is received every two slots.
  • Packet flow: The same exchange-rate expression remains achievable for the two-relay example using staggered transmissions and decoding.The construction uses alternating active transmitters across successive slots.
  • Multi-hop achievable rate: Structured coding achieves an exchange rate of 1/2 log(1/2 + P/σ2) in the multi-hop setting.The result is stated for the extended relay network and also described for nested lattice encoding and decoding.

APPENDIX A BLICHFELDT’S PRINCIPLE AND MINKOWSKI-HLAWKA THEOREM

This appendix introduces Blichfeldt’s principle and Minkowski-Hlawka, then applies them to relate lattice-point sums, integrals, and pair counts under translations.

  • Blichfeldt’s principle applies to integrable functions with bounded support over a lattice fundamental region.
  • The corollary relates the square of an n-dimensional sphere’s volume to the number of lattice-point pairs under two translations.M⊕(Λn, s1, s2) counts pairs of lattice points for translations s1 and s2.
  • Minkowski-Hlawka provides a lattice-existence result connecting discrete lattice sums with continuous integrals.The appendix notes that this connection is used in probability-of-error calculations.

APPENDIX B HYPER VOLUME CONCENTRATION LEMMA

This appendix analyzes the hypervolume of intersecting n-dimensional spheres and bounds the resulting integral, showing that the relevant terms vanish as dimension grows.

  • The integral represents the hypervolume of intersection between two hyper-spheres whose centers are separated by ∥x∥.The intersection is decomposed into a conical section and a cone for evaluation.
  • The geometry is evaluated using the half-angle θ and spherical-coordinate integration.The figure supports the interpretation of the sphere intersection and its conical decomposition.
  • The integral is split into terms and bounded using Shannon’s bound, sin ψ ≤ 1, trigonometric bounds, and a factorial bound.
  • Both resulting terms tend to 0 as n →∞, establishing the lemma.

APPENDIX C APPLICATION OF BLICHFELDT’S PRINCIPLE TO SHOW EXISTENCE OF GOOD TRANSLATIONS

This appendix applies Blichfeldt’s principle to show that suitable translations of a lattice exist, while bounding pair counts through integrals and lattice-point enumerations.

  • Lemma 13 defines translated lattice-point sets and bounds the associated integral using relationships among product regions.
  • δn > 0 can be made arbitrarily small for sufficiently large n.
  • The lattice-point sums factor into counts M(Λn, s1) and M(Λn, s2) for the two translations.
  • Blichfeldt’s principle is applied repeatedly to simplify the integrals and bound the number of summed lattice-point pairs.
  • A non-zero measure for the admissible translation set implies that at least one translation pair satisfies the required bounds.

APPENDIX D MINKOWSKI-HLAWKA THEOREM TO SHOW GOOD LATTICES EXIST

This appendix uses Minkowski-Hlawka to establish the existence of a lattice whose relevant summation is bounded by an integral, supporting the existence of good lattice constructions.

  • Lemma 14 asserts the existence of translational vectors satisfying the required bound.
  • The proof defines a nonnegative integrable function with bounded support and applies Minkowski-Hlawka to obtain a suitable lattice.
  • The resulting lattice summation is bounded by a continuous integral after changes of variables, integration-order exchanges, and spherical-coordinate evaluation.
  • Minkowski-Hlawka proves that such a lattice exists but does not provide a method for finding it.
  • The conditional probability is interpreted geometrically as the cross-sectional area of a hypercone intersecting a hyper-sphere.
Loading 0805.0012v2…