Reduced complexity closest point decoding algorithms for random lattices

Research output: Contribution to journalArticlepeer-review

45 Scopus citations


Closest point algorithms find wide applications in decoding block transmissions encountered with single- or multiuser communication links relying on a single or multiple antennas. Capitalizing on the random channel and noise models typically encountered in wireless communications, the sphere decoding algorithm (SDA) and related complexity-reducing techniques are approached in this paper from a probabilistic perspective. With both theoretical analysis and simulations, combining SDA with detection ordering is justified. A novel probabilistic search algorithm examining potential candidates in a descending probability order is derived and analyzed. Based on probabilistic search and an error-performance-oriented fast stopping criterion, a computationally efficient layered search is developed. Having comparable decoding complexity to the nulling-canceling (NC) algorithm with detection ordering, simulations confirm that the novel layered search achieves considerable error-performance enhancement.

Original languageEnglish (US)
Pages (from-to)101-111
Number of pages11
JournalIEEE Transactions on Wireless Communications
Issue number1
StatePublished - Jan 2006

Bibliographical note

Funding Information:
Manuscript received August 18, 2003; revised July 19, 2004; accepted October 1, 2004. The editor coordinating the review of this paper and approving it for publication is K. Narayanan. This paper was presented in part in the Proceedings of the 41st Allerton Conference, University of Illinois, Monticello, IL, October, 2003. This work was prepared through collaborative participation in the Communications and Networks Consortium sponsored by the U.S. Army Research Laboratory under the Collaborative Technology Alliance Program, Cooperative Agreement DAAD19-01-2-0011. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation thereon.


  • Closest point algorithm
  • Lenstra
  • Lovasz (LLL) lattice reduction
  • Multiuser detection
  • Random lattice decoding
  • Space-time
  • Sphere decoding


Dive into the research topics of 'Reduced complexity closest point decoding algorithms for random lattices'. Together they form a unique fingerprint.

Cite this