Efficient statistical pruning for maximum likelihood decoding

Abstract

In many communications problems, maximum-likelihood (ML) decoding reduces to finding the closest (skewed) lattice point in N-dimensions to a given point x∈C^N. In its full generality, this problem is known to be NP-complete and requires exponential complexity in N. Recently, the expected complexity of the sphere decoder, a particular algorithm that solves the ML problem exactly, has been computed; it is shown that, over a wide range of rates, SNRs and dimensions, the expected complexity is polynomial in N. We propose an algorithm that, for large N, offers substantial computational savings over the sphere decoder, while maintaining performance arbitrarily close to ML. The method is based on statistically pruning the search space. Simulations are presented to show the algorithm's performance and the computational savings relative to the sphere decoder.