Title :
An Algorithm to Compute the Nearest Point in the Lattice
Author :
McKilliam, Robby G. ; Clarkson, I. Vaughan L ; Quinn, Barry G.
Author_Institution :
Sch. of Inf. Technol. & Electr. Eng., Queensland Univ., Brisbane, QLD
Abstract :
The lattice A n * is an important lattice because of its covering properties in low dimensions. Clarkson described an algorithm to compute the nearest lattice point in A n * that requires O(n log n) arithmetic operations. In this correspondence, we describe a new algorithm. While the complexity is still O(n log n), it is significantly simpler to describe and verify. In practice, we find that the new algorithm also runs faster.
Keywords :
channel coding; direction-of-arrival estimation; frequency estimation; information theory; lattice theory; O(nlogn) arithmetic operations; lattice point; Arithmetic; Australia; Channel coding; Direction of arrival estimation; Frequency estimation; Frequency synchronization; Geometry; Lattices; Quantization; Sparse matrices; Channel coding; direction-of-arrival estimation; frequency estimation; lattice theory; nearest point algorithm; quantization; synchronization;
Journal_Title :
Information Theory, IEEE Transactions on
DOI :
10.1109/TIT.2008.928280