Reduced complexity closest point decoding algorithms for random lattices

Wanlun Zhao; Georgios B Giannakis

doi:10.1109/TWC.2006.1576534

Reduced complexity closest point decoding algorithms for random lattices

Wanlun Zhao, Georgios B Giannakis

Electrical and Computer Engineering

Research output: Contribution to journal › Article › peer-review

46 Scopus citations

Abstract

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 language	English (US)
Pages (from-to)	101-111
Number of pages	11
Journal	IEEE Transactions on Wireless Communications
Volume	5
Issue number	1
DOIs	https://doi.org/10.1109/TWC.2006.1576534
State	Published - 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.

Keywords

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

Publisher link

10.1109/TWC.2006.1576534

Find It

Find It at U of M Libraries

Cite this

@article{ea0f749e4eee489bb2b40508705d00db,

title = "Reduced complexity closest point decoding algorithms for random lattices",

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

keywords = "Closest point algorithm, Lenstra, Lovasz (LLL) lattice reduction, Multiuser detection, Random lattice decoding, Space-time, Sphere decoding",

author = "Wanlun Zhao and Giannakis, {Georgios B}",

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

year = "2006",

month = jan,

doi = "10.1109/TWC.2006.1576534",

language = "English (US)",

volume = "5",

pages = "101--111",

journal = "IEEE Transactions on Wireless Communications",

issn = "1536-1276",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "1",

}

TY - JOUR

T1 - Reduced complexity closest point decoding algorithms for random lattices

AU - Zhao, Wanlun

AU - Giannakis, Georgios B

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

PY - 2006/1

Y1 - 2006/1

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

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

KW - Closest point algorithm

KW - Lenstra

KW - Lovasz (LLL) lattice reduction

KW - Multiuser detection

KW - Random lattice decoding

KW - Space-time

KW - Sphere decoding

UR - http://www.scopus.com/inward/record.url?scp=31144444294&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=31144444294&partnerID=8YFLogxK

U2 - 10.1109/TWC.2006.1576534

DO - 10.1109/TWC.2006.1576534

M3 - Article

AN - SCOPUS:31144444294

SN - 1536-1276

VL - 5

SP - 101

EP - 111

JO - IEEE Transactions on Wireless Communications

JF - IEEE Transactions on Wireless Communications

IS - 1

ER -

Reduced complexity closest point decoding algorithms for random lattices

Abstract

Bibliographical note

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this