Integer Least Squares Problem Application in MIMO systems: An LLL Reduction Aided Sphere Decoding Algorithm

Abstract

<p> Solving the integer least squares problem min ||Hs- x|| 2 , where the unknown vector s is comprised of integers, the coefficient matrix H and given vector x are comprised of real numbers arises in many applications and is equivalent to find the closest lattice point to a given one known as NP-hard. In multiple antenna systems, the received signal represented by vector xis not arbitrary, but an lattice point perturbed by an additive noise vector whose statistical properties are known. It has been shown the Sphere Decoding, in which the lattice points inside a hyper-sphere are generated and the closest lattice point to the received signal is determined, together with Maximum Likelihood (ML) method often yields a near-optimal performance on average (cubic) while the worst case complexity is still exponential. By using lattice basis reduction as pre-processing step in the sub-optimum decoding algorithms, we can show that the lattice reduction aided sphere decoding (LRSD) achieves a better performance than the maximum likelihood sphere decoding (MLSD) in terms of symbol error rate (SER) and average algorithm running time. In the FIR (Finite Impulse Response) MIMO channel, the channel matrix is Toeplitz and thus gives us the leverage to use the fact that all its column vectors all linearly independent and the matrix itself is often well-conditioned. </p> <p> In this thesis, we will develop a lattice reduction added sphere decoding algorithm along with an improved LLL algorithm, and provide the simulations to show that this new algorithm achieves a better performance than the maximum likelihood sphere decoding. </p> <p> In chapter 1, we define our system model and establish the foundations for understanding of mathematical model - namly the integer least squares problem, and thus the choice of the simulation data. In chapter 2, we explain the integer least squares problems and exploit serveral ways for solving the problems, then we introduce the sphere decoding and maximum likelihood at the end. In chapter 3, we explore the famous LLL reduction algorithm named after Lenstra, Lenstra and Lovasz in details and show an example how to break Merkle-Hellman code using the LLL reduction algorithm. Finally, in chapter 4 we give the LLL reduction aided sphere decoding algorithm and the experiment setup as well as the simulation results against the MLSD and conclusions, further research directions. </p>