Statistical pruning for near-maximum likelihood decoding

In many communications problems, maximum-likelihood (ML) decoding reduces to nding the closest (skewed) lattice point in N-dimensions to a given point x 2 CN. In its full generality, this problem is known to be NP-complete and requires complexity exponential in N. Recently, the expected complexity of the sphere decoder, a particular algorithm that solves the ML problem exactly, has been computed where it is shown that over a wide range of rates, SNRs and dimensions the expected computation involves no more than N 3 computa-tions. In this paper, we propose an algorithm that, for large N, offers substantial computational savings over the sphere decoder, while maintaining performance arbitrarily close to ML. We statistically prune the search space to a subset that, with high probability, contains the optimal solution, thereby reducing the complexity of the search. Bounds on the error performance of the new method are proposed. The complexity of the new algorithm is analysed in three ways. One is an asymptotic analysis and holds for very large dimensions and the other two are an upper bound and approximation that are of interest in small to moderately large dimensions. Simulations are presented to compare the algorithm with the original sphere decoder.