Lattices from codes for harnessing interference: An overview and generalizations
---
paper_title: Lattices which are good for (almost) everything

paper_content:

Using random coding techniques, we show that, in high dimensions, there exist lattices which are simultaneously good as sphere packings, sphere coverings, AWGN channel and MSE quantization codes. These lattices are produced by a construction, similar to construction A (Conway, J.H. and Sloane, N.J.A., 1988), and a randomly chosen set of generating vectors.
---
paper_title: Compute-and-Forward: Harnessing Interference Through Structured Codes

paper_content:

Interference is usually viewed as an obstacle to communication in wireless networks. This paper proposes a new strategy, compute-and-forward, that exploits interference to obtain significantly higher rates between users in a network. The key idea is that relays should decode linear functions of transmitted messages according to their observed channel coefficients rather than ignoring the interference as noise. After decoding these linear equations, the relays simply send them towards the destinations, which given enough equations, can recover their desired messages. The underlying codes are based on nested lattices whose algebraic structure ensures that integer combinations of codewords can be decoded reliably. Encoders map messages from a finite field to a lattice and decoders recover equations of lattice points which are then mapped back to equations over the finite field. This scheme is applicable even if the transmitters lack channel state information.
---
paper_title: Lattices Over Eisenstein Integers for Compute-and-Forward

paper_content:

In this paper, we consider the use of lattice codes over Eisenstein integers for implementing a compute-and-forward protocol in wireless networks when channel state information is not available at the transmitter. We extend the compute-and-forward paradigm of Nazer and Gastpar to decoding Eisenstein integer combinations of transmitted messages at relays by proving the existence of a sequence of pairs of nested lattices over Eisenstein integers in which the coarse lattice is good for covering and the fine lattice can achieve the Poltyrev limit. Using this result, we show that both the outage performance and error-correcting performance of the nested lattice codebooks over Eisenstein integers surpass those of lattice codebooks over integers considered by Nazer and Gastpar with no additional computational complexity.
---
paper_title: The Approximate Sum Capacity of the Symmetric Gaussian K-User Interference Channel

paper_content:

Interference alignment has emerged as a powerful tool in the analysis of multi-user networks. Despite considerable recent progress, the capacity region of the Gaussian K-user interference channel is still unknown in general, in part due to the challenges associated with alignment on the signal scale using lattice codes. This paper develops a new framework for lattice interference alignment, based on the compute-and-forward approach. Within this framework, each receiver decodes by first recovering two or more linear combinations of the transmitted codewords with integer-valued coefficients and then solving these equations for its desired codeword. For the special case of symmetric channel gains, this framework is used to derive the approximate sum capacity of the Gaussian interference channel, up to an explicitly defined outage set of the channel gains. The key contributions are the capacity lower bounds for the weak through strong interference regimes, where each receiver should jointly decode its own codeword along with part of the interfering codewords. As part of the analysis, it is shown that decoding K linear combinations of the codewords can approach the sum capacity of the K-user Gaussian multiple-access channel up to a gap of no more than K log(K)/2 bits.
---
paper_title: An algebraic approach to physical-layer network coding

paper_content:

The problem of designing new physical-layer network coding (PNC) schemes via lattice partitions is considered. Building on a recent work by Nazer and Gastpar, who demonstrated its asymptotic gain using information-theoretic tools, we take an algebraic approach to show its potential in non-asymptotic settings. We first relate Nazer-Gastpar's approach to the fundamental theorem of finitely generated modules over a principle ideal domain. Based on this connection, we generalize their code construction and simplify their encoding and decoding methods. This not only provides a transparent understanding of their approach, but more importantly, it opens up the opportunity to design efficient and practical PNC schemes. Finally, we apply our framework for PNC to a Gaussian relay network and demonstrate its advantage over conventional PNC schemes.
---
paper_title: Compute-and-Forward: Harnessing Interference Through Structured Codes

paper_content:

Interference is usually viewed as an obstacle to communication in wireless networks. This paper proposes a new strategy, compute-and-forward, that exploits interference to obtain significantly higher rates between users in a network. The key idea is that relays should decode linear functions of transmitted messages according to their observed channel coefficients rather than ignoring the interference as noise. After decoding these linear equations, the relays simply send them towards the destinations, which given enough equations, can recover their desired messages. The underlying codes are based on nested lattices whose algebraic structure ensures that integer combinations of codewords can be decoded reliably. Encoders map messages from a finite field to a lattice and decoders recover equations of lattice points which are then mapped back to equations over the finite field. This scheme is applicable even if the transmitters lack channel state information.
---
paper_title: An algebraic approach to physical-layer network coding

paper_content:

The problem of designing new physical-layer network coding (PNC) schemes via lattice partitions is considered. Building on a recent work by Nazer and Gastpar, who demonstrated its asymptotic gain using information-theoretic tools, we take an algebraic approach to show its potential in non-asymptotic settings. We first relate Nazer-Gastpar's approach to the fundamental theorem of finitely generated modules over a principle ideal domain. Based on this connection, we generalize their code construction and simplify their encoding and decoding methods. This not only provides a transparent understanding of their approach, but more importantly, it opens up the opportunity to design efficient and practical PNC schemes. Finally, we apply our framework for PNC to a Gaussian relay network and demonstrate its advantage over conventional PNC schemes.
---
paper_title: Lattices which are good for (almost) everything

paper_content:

Using random coding techniques, we show that, in high dimensions, there exist lattices which are simultaneously good as sphere packings, sphere coverings, AWGN channel and MSE quantization codes. These lattices are produced by a construction, similar to construction A (Conway, J.H. and Sloane, N.J.A., 1988), and a randomly chosen set of generating vectors.
---
paper_title: Sphere Packings, Lattices and Groups

paper_content:

The second edition of this book continues to pursue the question: what is the most efficient way to pack a large number of equal spheres in n-dimensional Euclidean space? The authors also continue to examine related problems such as the kissing number problem, the covering problem, the quantizing problem, and the classification of lattices and quadratic forms. Like the first edition, the second edition describes the applications of these questions to other areas of mathematics and science such as number theory, coding theory, group theory, analog-to-digital conversion and data compression, n-dimensional crystallography, and dual theory and superstring theory in physics.
---
paper_title: Lattices Over Eisenstein Integers for Compute-and-Forward

paper_content:

In this paper, we consider the use of lattice codes over Eisenstein integers for implementing a compute-and-forward protocol in wireless networks when channel state information is not available at the transmitter. We extend the compute-and-forward paradigm of Nazer and Gastpar to decoding Eisenstein integer combinations of transmitted messages at relays by proving the existence of a sequence of pairs of nested lattices over Eisenstein integers in which the coarse lattice is good for covering and the fine lattice can achieve the Poltyrev limit. Using this result, we show that both the outage performance and error-correcting performance of the nested lattice codebooks over Eisenstein integers surpass those of lattice codebooks over integers considered by Nazer and Gastpar with no additional computational complexity.
---
paper_title: New results on Construction A lattices based on very sparse parity-check matrices

paper_content:

We address the problem of transmission of information over the AWGN channel using lattices. In particular, we will deal with previously introduced LDA lattices which are obtained by Construction A from LDPC codes over the finite field Fp. We will show how to build a particular ensemble of LDA lattices related to bipartite graphs with good expansion properties. We investigate the quality of this family under lattice decoding and show that a random member in it can be reliably decoded for any value of the channel noise variance up to Poltyrev limit. Values of p and the parameters for which optimal performance is guaranteed under lattice decoding are in accordance with the optimal parameters found experimentally under iterative decoding.
---
paper_title: Spatially-coupled low density lattices based on construction a with applications to compute-and-forward

paper_content:

We consider a class of lattices built using Construction A, where the underlying code is a non-binary spatially-coupled low density parity check code. We refer to these lattices as spatially-coupled LDA (SCLDA) lattices. SCLDA lattices can be constructed over integers, Gaussian integers and Eisenstein integers. We empirically study the performance of SCLDA lattices under belief propagation (BP) decoding. Ignoring the rate loss from termination, simulation results show that the BP thresholds of SCLDA lattices over integers is 0.11 dB (0.34 dB with the rate loss) and the BP thresholds for SCLDA lattices over Eisenstein integers are 0.08 dB from the Poltyrev limit (0.19 dB with the rate loss). Motivated by this result, we use SCLDA lattice codes over Eisenstein integers for implementing a compute-and-forward protocol. For the examples considered in this paper, the thresholds for the proposed lattice codes are within 0.28 dB from the achievable rate of this coding scheme and within 1.06 dB from the achievable computation rate of Nazer and Gastpar's coding scheme in [6] extended to Eisenstein integers.
---
paper_title: Integer low-density lattices based on construction A

paper_content:

We describe a new family of integer lattices built from construction A and non-binary LDPC codes. An iterative message-passing algorithm suitable for decoding in high dimensions is proposed. This family of lattices, referred to as LDA lattices, follows the recent transition of Euclidean codes from their classical theory to their modern approach as announced by the pioneering work of Loeliger (1997), Erez, Litsyn, and Zamir (2004–2005). Besides their excellent performance near the capacity limit, LDA lattice construction is conceptually simpler than previously proposed lattices based on multiple nested binary codes and LDA decoding is less complex than real-valued message passing.
---
paper_title: New lattice packings of spheres

paper_content:

A > — Qn + o(n) in [21]. The latter two families of packings were obtained by applying Construction C of [15] to certain sequences of codes. Our first construction, Construction D (see 2.1), resembles Construc­tion C in that it is also based on a sequence of codes, but differs in pro­ducing lattices provided only that the codes are binary, linear and nested. In this way we obtain new record densities for lattices in dimensions 36, 64, etc., and an infinite sequence of lattices with log
---
paper_title: Sphere-bound-achieving coset codes and multilevel coset codes

paper_content:

A simple sphere bound gives the best possible tradeoff between the volume per point of an infinite array L and its error probability on an additive white Gaussian noise (AWGN) channel. It is shown that the sphere bound can be approached by a large class of coset codes or multilevel coset codes with multistage decoding, including certain binary lattices. These codes have structure of the kind that has been found to be useful in practice. Capacity curves and design guidance for practical codes are given. Exponential error bounds for coset codes are developed, generalizing Poltyrev's (1994) bounds for lattices. These results are based on the channel coding theorems of information theory, rather than the Minkowski-Hlawka theorem of lattice theory.
---
paper_title: Construction of turbo lattices

paper_content:

In this work we introduce and establish the concept of turbo lattices. We employ a routine method for constructing lattices, called Construction D, to construct turbo lattices. This kind of construction needs a set of nested linear codes as its underlying structure. We benefit from turbo codes as our bases codes. Therefore, we first build a set of nested turbo codes based on nested interleavers and nested convolutional codes. Then by means of these codes, along with construction D, we construct turbo lattices. Several properties of Construction D lattices and specially many characteristics of turbo lattices including the minimum distance, coding gain, kissing number and the probability of error under a maximum likelihood decoder over AWGN channel are investigated.
---
paper_title: Compute-and-Forward: Harnessing Interference Through Structured Codes

paper_content:

Interference is usually viewed as an obstacle to communication in wireless networks. This paper proposes a new strategy, compute-and-forward, that exploits interference to obtain significantly higher rates between users in a network. The key idea is that relays should decode linear functions of transmitted messages according to their observed channel coefficients rather than ignoring the interference as noise. After decoding these linear equations, the relays simply send them towards the destinations, which given enough equations, can recover their desired messages. The underlying codes are based on nested lattices whose algebraic structure ensures that integer combinations of codewords can be decoded reliably. Encoders map messages from a finite field to a lattice and decoders recover equations of lattice points which are then mapped back to equations over the finite field. This scheme is applicable even if the transmitters lack channel state information.
---
paper_title: Multistage compute-and-forward with multilevel lattice codes based on product constructions

paper_content:

A novel construction of lattices is proposed. This construction can be thought of as Construction A with codes that can be represented as the Cartesian product of $L$ linear codes over $\mathbb{F}_{p_1},\ldots,\mathbb{F}_{p_L}$, respectively; hence, is referred to as the product construction. The existence of a sequence of such lattices that are good for quantization and Poltyrev-good under multistage decoding is shown. This family of lattices is then used to generate a sequence of nested lattice codes which allows one to achieve the same computation rate of Nazer and Gastpar for compute-and-forward under multistage decoding, which is referred to as lattice-based multistage compute-and-forward. Motivated by the proposed lattice codes, two families of signal constellations are then proposed for the separation-based compute-and-forward framework proposed by Tunali \textit{et al.} together with a multilevel coding/multistage decoding scheme tailored specifically for these constellations. This scheme is termed separation-based multistage compute-and-forward and is shown having a complexity of the channel coding dominated by the greatest common divisor of the constellation size (may not be a prime number) instead of the constellation size itself.
---
paper_title: An algebraic approach to physical-layer network coding

paper_content:

The problem of designing new physical-layer network coding (PNC) schemes via lattice partitions is considered. Building on a recent work by Nazer and Gastpar, who demonstrated its asymptotic gain using information-theoretic tools, we take an algebraic approach to show its potential in non-asymptotic settings. We first relate Nazer-Gastpar's approach to the fundamental theorem of finitely generated modules over a principle ideal domain. Based on this connection, we generalize their code construction and simplify their encoding and decoding methods. This not only provides a transparent understanding of their approach, but more importantly, it opens up the opportunity to design efficient and practical PNC schemes. Finally, we apply our framework for PNC to a Gaussian relay network and demonstrate its advantage over conventional PNC schemes.
---
paper_title: Multistage compute-and-forward with multilevel lattice codes based on product constructions

paper_content:

A novel construction of lattices is proposed. This construction can be thought of as Construction A with codes that can be represented as the Cartesian product of $L$ linear codes over $\mathbb{F}_{p_1},\ldots,\mathbb{F}_{p_L}$, respectively; hence, is referred to as the product construction. The existence of a sequence of such lattices that are good for quantization and Poltyrev-good under multistage decoding is shown. This family of lattices is then used to generate a sequence of nested lattice codes which allows one to achieve the same computation rate of Nazer and Gastpar for compute-and-forward under multistage decoding, which is referred to as lattice-based multistage compute-and-forward. Motivated by the proposed lattice codes, two families of signal constellations are then proposed for the separation-based compute-and-forward framework proposed by Tunali \textit{et al.} together with a multilevel coding/multistage decoding scheme tailored specifically for these constellations. This scheme is termed separation-based multistage compute-and-forward and is shown having a complexity of the channel coding dominated by the greatest common divisor of the constellation size (may not be a prime number) instead of the constellation size itself.
---
paper_title: Optimality of linear codes over PAM for the modulo-additive Gaussian channel

paper_content:

It has long been known that linear codes achieve the capacity of additive channels over finite fields. Much less has been known about the performance of linear codes over Z m , when used for communication over channels that are additive with respect to this group. Further, linear codes over Z m play an important role in construction of lattices in Euclidean space. When a construction-A lattice is used for communication over an additive white Gaussian noise channel, a modulo-MZ additive channel with unimodal noise is induced at the receiver. In this paper it is shown that linear codes over Z m achieve the capacity of such channels when the cardinality of the alphabet is a power of a prime.
---
paper_title: Phase precoded compute-and-forward with partial feedback

paper_content:

ard (CoF) protocol. We derive the phase precoded computation rate and show that it is greater than the original computation rate of CoF protocol without precoder. To maximize the phase precoded computation rate, we need to 'jointly' find the optimum phase precoding matrix and the cor­ responding network equation coefficients. This is a mixed integer programming problem where the optimum precoders should be obtained at the transmitters and the network equation coefficients have to be computed at the relays. To solve this problem, we introduce phase precoded CoF with partial feedback. It is a quantized precoding system where the relay jointly computes both a quasi-optimal precoder from a finite codebook and the corresponding network equations. The index of the obtained phase precoder within the codebook will then be fedback to the transmitters. A "deep hole phase precoder" is presented as an example of such a scheme. We further simulate our scheme with a lattice code carved out of the Gosset lattice and show that significant coding gains can be obtained in terms of equation error performance. Index Terms-Compute-an d-forward, lattice codes, phase pre­ coding.
---
paper_title: Construction A of Lattices over Number Fields and Block Fading Wiretap Coding

paper_content:

We propose a lattice construction from totally real and complex multiplication fields, which naturally generalizes Construction A of lattices from $p$ -ary codes obtained from the cyclotomic field $ \mathbb {Q}(\zeta _{p})$ , $p$ a prime, which in turn contains the so-called Construction A of lattices from binary codes as a particular case. We focus on the maximal totally real subfield $ \mathbb {Q}(\zeta _{p^{r}}\,+\,\zeta _{p}^{-r})$ of the cyclotomic field $ \mathbb {Q}(\zeta _{p^{r}})$ , $r\geq 1$ . Our construction has applications to coset encoding of algebraic lattice codes for block fading channels, and in particular for block fading wiretap channels.
---

Title: Lattices from codes for harnessing interference: An overview and generalizations

Section 1: INTRODUCTION
Description 1: Provide an overview of the problem of interference in multi-user communications, the novel perspective of managing interference with structured codes, and the relevance of lattices constructed from codes.

Section 2: PROBLEM STATEMENT AND THE COMPUTE-AND-FORWARD PARADIGM
Description 2: Discuss the compute-and-forward network, including the framework proposed by Nazer and Gastpar, and explain the channel model, encoding strategies, and the computation rates achievable.

Section 3: SOME KNOWN CONSTRUCTIONS FROM CODES
Description 3: Review the known lattice constructions from codes that are suitable for the compute-and-forward paradigm, including detailed explanations of Construction A, Construction D, and Construction π A.

Section 4: GENERALIZATIONS
Description 4: Explore two generalizations of lattice constructions that expand the design space, including the novel Construction π D and lattices over rings of algebraic integers, and discuss the benefits and challenges associated with these generalizations.