On the Sphere-Decoding Algorithm I.
Expected Complexity
Abstract—The problem of finding the least-squares solution
to a system of linear equations where the unknown vector is
comprised of integers, but the matrix coefficient and given vector
are comprised of real numbers, arises in many applications:
communications, cryptography, GPS, to name a few. The problem
is equivalent to finding the closest lattice point to a given point and
is known to be NP-hard. In communications applications, however, the given vector is not arbitrary but rather is an unknown
lattice point that has been perturbed by an additive noise vector
whose statistical properties are known. Therefore......
1