[IEEE Trans. on Information Theory, August 2002, pp. 2201-2214]
Closest Point Search in Lattices
Erik Agrell, Thomas Eriksson, Alexander Vardy, and Kenneth Zeger
Abstract
In this semi-tutorial paper, a comprehensive survey of closest-point
search methods for lattices without a regular structure is presented.
The existing search strategies are described in a unified framework,
and differences between them are elucidated. An efficient
closest-point search algorithm, based on the Schnorr-Euchner variation
of the Pohst method, is implemented. Given an arbitrary point
x ∈ Rm and a generator matrix for a lattice Λ, the
algorithm computes the point of Λ that is closest to x.
The algorithm is shown to be substantially faster than other known
methods, by means of a theoretical comparison with the Kannan
algorithm and an experimental comparison with the Pohst algorithm and
its variants, such as the recent Viterbo-Boutros decoder. The
improvement increases with the dimension of the lattice.
Modifications of the algorithm are developed to solve a~number of
related search problems for lattices, such as finding a shortest
vector, determining the kissing number, computing the Voronoi-relevant
vectors, and finding a Korkine-Zolotareff reduced basis.