A polynomial time algorithm for exact maximum likelihood decoding of MIMO channels: a discrete geometric approach

The information capacity of wireless communication systems may be increased dramatically by employing multiple transmit and receive antennas. Often the optimal receiver in Maximum likelihood sequence detector (MLSD), which is considered to be practically infeasable due to high computational complexity. Therefore, in practice one often settles with less complex suboptimal receiver structure. In this chapter, we propose a polynomial time algorithm for exact maximum likelihood (ML) decoding for MIMO channels. The problem is posed as maximizing a quadratic form in _ binary variables (BPSK case) with the vertices of a hypercube as constraint. We consider _ receive antennas and _ transmit antennas. We assume that _ _ _ , and that _ is fixed. The maximization of ML cost function with vertices of hypercube, i.e., _____ _____ , as constraints, translates to having a symmetric matrix in quadratic form with fixed rank, _ and with the hypercube constraint. With singular value decomposition (SVD) of the symmetric matrix and suitable affine transformation of the hypercube constraint one ends up with maximizing a quadratic function (Euclidean distance) over extreme points (vertices) of zonotope (definition of zonotope will be given later). Using a classical theorem of discrete geometry, it is shown that the vertices search can be done in polynomial time, ___ _________ . The overall complexity of the algorithm is the complexity to find extreme point of zonotope plus the complexity of the SVD operation plus the evaluation of the objective function at the vertices. To find the vertices of zonotopes, an efficient algorithm called reverse search algorithm can be employed [1,6,7]. Our approach has potential benefits over currently popular sphere decoding scheme [3]. The average case complexity of sphere decoding scheme is ___ _____ plus the complexity to perform QR decomposition ____ _____ of the channel, when radius, r, is correctly chosen (which is NP-hard problem). Also at low SNRs the complexity of the sphere decoder explodes. The other problem with to choose the radius of hypersphere. On the contrary, the proposed method has polynomial complexity independent of SNR and also no heuristic is used in the algorithm.