Journal
IEEE TRANSACTIONS ON INFORMATION THEORY
Volume 48, Issue 8, Pages 2201-2214Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TIT.2002.800499
Keywords
closest point search; kissing number; Korkine-Zolotareff (KZ) reduction; lattice decoding; lattice quantization; nearest neighbor; shortest vector; Voronoi diagram
Ask authors/readers for more resources
In this semitutorial 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 is an element of R-m and a generator matrix for a lattice A, the algorithm computes the point of A 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. 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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available