A Caltech Library Service

A new exact closest lattice point search algorithm using linear constraints

Xu, Weiyu and Hassibi, Babak (2007) A new exact closest lattice point search algorithm using linear constraints. In: Signal Processing Advances in Wireless Communications, 2007. IEEE , pp. 1-5. ISBN 978-1-4244-0955-6.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


The problem of finding the closest lattice point arises in several communications scenarios and is known to be NP-hard. We propose a new closest lattice point search algorithm which utilizes a set of new linear inequality constraints to reduce the search of the closest lattice point to the intersection of a polyhedron and a sphere. This set of linear constraints efficiently leverage the geometric structure of the lattice to reduce considerably the number of points that must be visited. Simulation results verify that this algorithm offers substantial computational savings over standard sphere decoding when the dimension of the problem is large.

Item Type:Book Section
Related URLs:
URLURL TypeDescription*%26searchField%3DSearch+AllPublisherUNSPECIFIED
Additional Information:© 2007 IEEE. Issue Date: 17-20 June 2007; date of current version: 12 December 2007. This work was supported by the Caltech Information Science and Technology Fellowship and Caltech’s Lee Center for Advanced Networking.
Funding AgencyGrant Number
Information Science and Technology Fellowship, CaltechUNSPECIFIED
Lee Center for Advanced Networking, CaltechUNSPECIFIED
Subject Keywords:closest lattice point search, convex programming, sphere decoder, maximum-likelihood, complexity
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number9855749
Record Number:CaltechAUTHORS:20100507-094336274
Persistent URL:
Official Citation:Weiyu Xu; Hassibi, B.; , "A new exact closest lattice point search algorithm using linear constraints," Signal Processing Advances in Wireless Communications, 2007. SPAWC 2007. IEEE 8th Workshop on , vol., no., pp.1-5, 17-20 June 2007 doi: 10.1109/SPAWC.2007.4401291 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:18184
Deposited By: Jason Perez
Deposited On:03 Jun 2010 21:11
Last Modified:03 Oct 2019 01:39

Repository Staff Only: item control page