A Near Maximum Likelihood Decoding Algorithm for MIMO Systems Based on Semi-Definite Programming
Preprint
Abstract
In Multi-Input Multi-Output (MIMO) systems, Maximum-Likelihood (ML) decoding is equivalent to finding the closest lattice point in an N-dimensional complex space. In general, this problem is known to be NP hard. In this paper, we propose a quasi-maximum likelihood algorithm based on Semi-Definite Programming (SDP). We introduce several SDP relaxation models for MIMO systems, with increasing complexity. We use interior-point methods for solving the models and obtain a near-ML performance with polynomial computational complexity. Lattice basis reduction is applied to further reduce the computational complexity of solving these models. The proposed relaxation models are also used for soft output decoding in MIMO systems.Keywords
All Related Versions
This publication has 27 references indexed in Scilit:
- Bounds for the quadratic assignment problem using the bundle methodMathematical Programming, 2006
- Layered space-time architecture for wireless communication in a fading environment when using multi-element antennasBell Labs Technical Journal, 2002
- Semidefinite programming relaxations for the graph partitioning problemDiscrete Applied Mathematics, 1999
- Semidefinite Programming Relaxations for the Quadratic Assignment ProblemJournal of Combinatorial Optimization, 1998
- A lift-and-project cutting plane algorithm for mixed 0–1 programsMathematical Programming, 1993
- On Lovász’ lattice reduction and the nearest lattice point problemCombinatorica, 1986
- Algorithms to construct minkowski reduced and hermite reduced lattice basesTheoretical Computer Science, 1985
- Cancellation techniques of co‐channel interference in asynchronous spread spectrum multiple access systemsElectronics and Communications in Japan (Part I: Communications), 1983
- Factoring polynomials with rational coefficientsMathematische Annalen, 1982
- Sur les formes quadratiquesMathematische Annalen, 1873