A Near-Maximum-Likelihood Decoding Algorithm for MIMO Systems Based on Semi-Definite Programming

Author

Mobasher, Amin ; Taherzadeh, Mahmoud ; Sotirov, Renata ; Khandani, Amir K.

Author_Institution

Univ. of Waterloo, Waterloo

Volume

53

Issue

11

fYear

2007

Firstpage

3869

Lastpage

3886

Abstract

In multiple-input multiple-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, a quasi-ML algorithm based on semi-definite programming (SDP) is proposed. 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

MIMO communication; maximum likelihood decoding; polynomials; MIMO system; SDP relaxation model; interior-point method; lattice basis reduction; maximum-likelihood decoding algorithm; multiple-input multiple-output system; polynomial computational complexity; semidefinite programming; Computational complexity; Detectors; Fading; Information theory; Lattices; MIMO; Maximum likelihood decoding; Object detection; Polynomials; Transmitting antennas; Closest lattice point; computational complexity; decoding; lattice basis reduction; lattice decoding; multiple-input multiple-output (MIMO) systems; quasi-maximum likelihood; semi-definite programming (SDP);

fLanguage

English

Journal_Title

Information Theory, IEEE Transactions on

Publisher

ieee

ISSN

0018-9448

Type

jour

DOI

10.1109/TIT.2007.907472

Filename

4373418