<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> / Thesis / Master of Science (MSc)
| Identifer | oai:union.ndltd.org:mcmaster.ca/oai:macsphere.mcmaster.ca:11375/21287 |
| Date | 04 1900 |
| Creators | Guo, Jin |
| Contributors | Qiao, Sanzheng, Computing and Software |
| Source Sets | McMaster University |
| Language | English |
| Detected Language | English |
Page generated in 0.0011 seconds