Randomized lattice decoding: bridging the gap between lattice reduction and sphere decoding

Shuiyin Liu, Cong Ling, Damien Stehlé

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

5 Citations (Scopus)
41 Downloads (Pure)


Sphere decoding achieves maximum-likelihood (ML) performance at the cost of exponential complexity; lattice reduction-aided decoding significantly reduces the decoding complexity, but exhibits a widening gap to ML performance as the dimension increases. To bridge the gap between them, this paper presents randomized lattice decoding based on Klein's randomized algorithm, which is a randomized version of Babai's nearest plane algorithm. The technical contribution of this paper is twofold: we analyze and optimize the performance of randomized lattice decoding resulting in reduced decoding complexity, and propose a very efficient implementation of random rounding. Simulation results demonstrate near-ML performance achieved by a moderate number of calls, when the dimension is not too large.
Original languageEnglish
Title of host publication2010 IEEE International Symposium on Information Theory
Subtitle of host publication(ISIT) : Austin, TX 13-18 June, 2010
Place of PublicationPiscataway, N.J.
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages5
ISBN (Print)9781424478910
Publication statusPublished - 2010
EventIEEE International Symposium on Information Theory - Austin, Texas
Duration: 13 Jun 201018 Jun 2010


ConferenceIEEE International Symposium on Information Theory
CityAustin, Texas

Bibliographical note

Copyright 2010 IEEE. Reprinted from 2010 IEEE International Symposium on Information Theory : (ISIT) : Austin, TX 13-18 June, 2010. This material is posted here with permission of the IEEE. Such permission of the IEEE does not in any way imply IEEE endorsement of any of Macquarie University’s products or services. Internal or personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution must be obtained from the IEEE by writing to pubs-permissions@ieee.org. By choosing to view this document, you agree to all provisions of the copyright laws protecting it.


  • decoding complexity
  • efficient implementation
  • information theory
  • maximum likelihood
  • spheres
  • decoding
  • exponential complexity
  • lattice decoding
  • lattice reduction
  • random rounding
  • randomized algorithms
  • simulation result
  • sphere decoding
  • technical contribution


Dive into the research topics of 'Randomized lattice decoding: bridging the gap between lattice reduction and sphere decoding'. Together they form a unique fingerprint.

Cite this