The problem of finding the least-squares solution to a system of linear equations where the unknown vector is comprised of integers, while the given vector and the coefficient matrix are comprised of real entries, arises in many applications: digital communications, cryptography, GPS, to name a few. This problem is equivalent to the closest-point search in a lattice and is known to be NP-hard. However, in communications applications, where maximum-likelihood detection often reduces to solving an integer-least-squares problem, the given vector is not arbitrary, but rather is an unknown point in a finite lattice that has been perturbed by an additive noise vector of known statistical properties. We study the expected complexity of the integer-least-squares problem, averaged over the noise and over the lattice. For the "sphere decoding" algorithm of Fincke and Pohst we find analytic expressions for the expected complexity. We show that for a wide range of signal-to-noise ratios the expected complexity is polynomial, in fact often sub-cubic. Many communication systems operate at noise levels for which this is the case, suggesting that the maximum-likelihood detection, which was hitherto thought to be computationally intractable, can in fact be implemented with the complexity similar to the heuristic methods, but with significant performance gains--a result with many practical implications.
In addition, extending the sphere-constrained search idea of the Fincke-Pohst algorithm, we develop algorithms that solve several important integer least-squares related problems in the communications setting. For channels with memory, we propose a combination of the constrained search technique of sphere decoding and the dynamic programming principles of the Viterbi algorithm. The resulting algorithm has the worst-case complexity of the Viterbi algorithm but is significantly faster on average. Furthermore, motivated by the prospect of high reliability that iterative decoding techniques have been shown to provide on single-antenna channels, and by the absence of efficient techniques to obtain the soft-information in multiple-antenna systems, we propose an algorithm that solves the maximum a posteriori detection problem and efficiently approximates the required soft-information. Finally, we develop a new algorithm for efficient joint maximum-likelihood detection and decoding of the linear block codes.
My Research