New techniques for lattice problems in communications
Creators: name: Lyu, Shanxiang
Publisher: name: Imperial College London
Year: 2018

description: The approach to solving problems in communications from the perspective of lattice coding and decoding has received much attention in recent years as simple and elegant solutions can often be obtained. In this thesis, we develop several new techniques for the lattice problems involved, that allow the performance limit of lattice coding and the complexity-performance trade-off of lattice decoding to be better understood. First, we propose a greedy technique for lattice reduction (LR) which is usually taken as a preprocessing step in lattice decoding. Realizing the size reduction operations in LR can possibly increase the lengths of basis vectors, it motivates us to replace the size reduction steps through defining length-reduction operations. The principle of such operations is to be greedy because we need to pursuit the shortest possible candidates. The length-reduction technique is incorporated into the popular Korkine-Zolotarev (KZ) and Lenstra-Lenstra-Lov\'asz (LLL) algorithms. The resulted boosted KZ reduction is shown to have the tightest bounds on lengths in all LR algorithms. We apply the boosted KZ and LLL algorithms to designing integer-forcing linear receivers for multiple-input and multiple-output (MIMO) communications. Our simulations confirm their rate and complexity advantages. Second, we consider a graphical technique for the closest vector problem in vector perturbation (VP) precoding. The approximate message passing (AMP) algorithm based on factor graphs has become perhaps the most popular low-complexity algorithm for solving convex problems in compressed sensing. It is however unclear whether AMP can be beneficial for a lattice decoding problem which is NP-hard. We propose a hybrid framework to improve the performance of LR aided decoding, which particularly suits VP. Our work shows that the AMP algorithm can be beneficial for a lattice decoding problem whose data symbols lie in integers $\mathbb{Z}$ and entries of the lattice basis may bot be i.i.d. Gaussian. Numerical results confirm the low-complexity AMP algorithm can improve the symbol error rate performance of LR aided precoding significantly. Lastly, the hybrid scheme is also proved effective when solving the data detection problem of massive MIMO systems without using LR. Third, we examine algebraic lattice reduction in Compute-and-Forward that employs lattice codes based on the rings of complex quadratic fields. As the underlying lattices are complex, we first examine Hermite's constant and Minkowski's theorems in this context. Then we present an algebraic LLL algorithm to reduce these complex lattices. We show that the lower bound of Lov\'asz's constant in algebraic LLL depends on the covering radius of rings, while the upper bound of it implies that only norm-Euclidean domains can be proper. The rotation step in algebraic LLL can be simplified after introducing quaternions. Finally, we propose a novel scheme for Compute-and-Forward in block-fading channels, which is referred to as Ring Compute-and-Forward because the fading coefficients are quantized to the canonical embedding of a ring of algebraic integers. Thanks to the multiplicative closure of the algebraic lattices employed, a relay is able to decode an algebraic-integer linear combination of lattice codewords. We analyze its achievable computation rates and show it outperforms conventional Compute-and-Forward based on $\mathbb{Z}$-lattices. By investigating the effect of Diophantine approximation by algebraic conjugates, we prove that the degrees-of-freedom (DoF) of the computation rate is $n/L$, while the DoF of the sum-rate is $n$, where $n$ is the number of blocks and $L$ is the number of users.