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

Shuiyin Liu; Cong Ling; Damien Stehlé

doi:10.1109/ISIT.2010.5513543

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

Shuiyin Liu, Cong Ling, Damien Stehlé

School of Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

5 Citations (Scopus)

41 Downloads (Pure)

Abstract

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 language	English
Title of host publication	2010 IEEE International Symposium on Information Theory
Subtitle of host publication	(ISIT) : Austin, TX 13-18 June, 2010
Place of Publication	Piscataway, N.J.
Publisher	Institute of Electrical and Electronics Engineers (IEEE)
Pages	2263-2267
Number of pages	5
ISBN (Print)	9781424478910
DOIs	https://doi.org/10.1109/ISIT.2010.5513543
Publication status	Published - 2010
Event	IEEE International Symposium on Information Theory - Austin, Texas Duration: 13 Jun 2010 → 18 Jun 2010

Conference

Conference	IEEE International Symposium on Information Theory
City	Austin, Texas
Period	13/06/10 → 18/06/10

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.

Keywords

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

Access to Document

10.1109/ISIT.2010.5513543

Publisher version (open access)Final published version, 234 KBLicence: Unspecified

Cite this

@inproceedings{2de473860edf4ff1b91042315c995775,

title = "Randomized lattice decoding: bridging the gap between lattice reduction and sphere decoding",

abstract = "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.",

keywords = "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",

author = "Shuiyin Liu and Cong Ling and Damien Stehl{\'e}",

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{\textquoteright}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.; IEEE International Symposium on Information Theory ; Conference date: 13-06-2010 Through 18-06-2010",

year = "2010",

doi = "10.1109/ISIT.2010.5513543",

language = "English",

isbn = "9781424478910",

pages = "2263--2267",

booktitle = "2010 IEEE International Symposium on Information Theory",

publisher = "Institute of Electrical and Electronics Engineers (IEEE)",

address = "United States",

}

Liu, S, Ling, C & Stehlé, D 2010, Randomized lattice decoding: bridging the gap between lattice reduction and sphere decoding. in 2010 IEEE International Symposium on Information Theory: (ISIT) : Austin, TX 13-18 June, 2010. Institute of Electrical and Electronics Engineers (IEEE), Piscataway, N.J., pp. 2263-2267, IEEE International Symposium on Information Theory, Austin, Texas, 13/06/10. https://doi.org/10.1109/ISIT.2010.5513543

Randomized lattice decoding: bridging the gap between lattice reduction and sphere decoding. / Liu, Shuiyin; Ling, Cong; Stehlé, Damien.
2010 IEEE International Symposium on Information Theory: (ISIT) : Austin, TX 13-18 June, 2010. Piscataway, N.J.: Institute of Electrical and Electronics Engineers (IEEE), 2010. p. 2263-2267.

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

TY - GEN

T1 - Randomized lattice decoding

T2 - IEEE International Symposium on Information Theory

AU - Liu, Shuiyin

AU - Ling, Cong

AU - Stehlé, Damien

N1 - 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.

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

KW - decoding complexity

KW - efficient implementation

KW - information theory

KW - maximum likelihood

KW - spheres

KW - decoding

KW - exponential complexity

KW - lattice decoding

KW - lattice reduction

KW - random rounding

KW - randomized algorithms

KW - simulation result

KW - sphere decoding

KW - technical contribution

U2 - 10.1109/ISIT.2010.5513543

DO - 10.1109/ISIT.2010.5513543

M3 - Conference proceeding contribution

SN - 9781424478910

SP - 2263

EP - 2267

BT - 2010 IEEE International Symposium on Information Theory

PB - Institute of Electrical and Electronics Engineers (IEEE)

CY - Piscataway, N.J.

Y2 - 13 June 2010 through 18 June 2010

ER -

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

Abstract

Conference

Bibliographical note

Keywords

Access to Document

Fingerprint

Cite this