Speeding up the Sphere Decoder With H∞ and SDP Inspired Lower Bounds

It is well known that maximum-likelihood (ML) decoding in many digital communication schemes reduces to solving an integer least-squares problem, which is NP hard in the worst-case. On the other hand, it has recently been shown that, over a wide range of dimensions N and signal-to-noise ratios (SNRs), the sphere decoding algorithm can be used to find the exact ML solution with an expected complexity that is often less than N³. However, the computational complexity of sphere decoding becomes prohibitive if the SNR is too low and/or if the dimension of the problem is too large. In this paper, we target these two regimes and attempt to find faster algorithms by pruning the search tree beyond what is done in the standard sphere decoding algorithm. The search tree is pruned by computing lower bounds on the optimal value of the objective function as the algorithm proceeds to descend down the search tree. We observe a tradeoff between the computational complexity required to compute a lower bound and the size of the pruned tree: the more effort we spend in computing a tight lower bound, the more branches that can be eliminated in the tree. Using ideas from semidefinite program (SDP)-duality theory and H^infin estimation theory, we propose general frameworks for computing lower bounds on integer least-squares problems. We propose two families of algorithms, one that is appropriate for large problem dimensions and binary modulation, and the other that is appropriate for moderate-size dimensions yet high-order constellations. We then show how in each case these bounds can be efficiently incorporated in the sphere decoding algorithm, often resulting in significant improvement of the expected complexity of solving the ML decoding problem, while maintaining the exact ML-performance.     

Exact bit error probabilities and packet error statistics for SVD transmission over time-varying dual-branch MIMO systems obtained by a Markov model

Using a finite state Markov channel model, we develop an analytical method for evaluation of the packet error structure in multiple-input multiple-output (MIMO) systems based on singular value decomposition (SVD). We consider dual-branch MIMO systems, with either two transmit and arbitrary number of receive antennas, or arbitrary number of transmit and two receive antennas. The corresponding Markov model parameters are obtained using a novel closed-form expressions for probability density function and level crossing rate of the signal-to-noise ratio at the output of eigenchannels in a MIMO system, derived for a case of Rayleigh propagation, imperfect channel state information and any fixed power allocation. The exact bit error rate for the transmission of quadrature amplitude modulated (QAM) symbols through the eigenchannels is derived in polynomial closed form. Furthermore, by using the developed Markov model, the packet error statistics in the corresponding eigenchannels are determined, and the closed-form analytical expression for the system throughput is derived when ‘go-back-N’ automatic repeat request procedure is applied in time-varying eigenchannels. The analytical results are validated by using Monte Carlo simulations.