Maximum likelihood detection for the linear MIMO channel

Sammanfattning: this thesis the problem of maximum likelihood (ML) detection for the linear multiple-input multiple-output (MIMO) channel is considered. The thesis investigates two algorithms previously proposed in the literature for implementing the ML detector, namely semide nite relaxation and sphere decoding.The first algorithm, semide nite relaxation, is a suboptimal implementation of the ML detector meaning that it is not guaranteed to solve the maximum likelihood detection problem. Still, numerical evidence suggests that the performance of the semide nite relaxation detector is close to that of the true ML detector. A contribution made in this thesis is to derive conditions under which the semide nite relaxation estimate can be guaranteed to coincide with the ML estimate.The second algorithm, the sphere decoder, can be used to solve the ML detection problem exactly. Numerical evidence has previously shown that the complexity of the sphere decoder is remarkably low for problems of moderate size. This has led to the widespread belief that the sphere decoder is of polynomial expected complexity. This is however unfortunately not true. Instead, in most scenarios encountered in digital communications, the expected complexity of the algorithm is exponential in the number of symbols jointly detected. However, for high signal to noise ratio the rate of exponential increase is small. In this thesis it is proved that for a large class of detection problems the expected complexity is lower bounded by an exponential function. Also, for the special case of an i.i.d. Rayleigh fading channel, an asymptotic analysis is presented which enables the computation of the expected complexity up to the linear term in the exponent.