NDLI: Reduced and Fixed-Complexity Variants of the LLL Algorithm for Communications

Content Provider	IEEE Xplore Digital Library
Author	Ling, Cong Mow, Wai Ho Howgrave-Graham, Nick
Copyright Year	1972
Abstract	The Lenstra-Lenstra-Lovász (LLL) algorithm is a popular lattice reduction algorithm in communications. In this paper, variants of the LLL algorithm with either reduced or fixed complexity are proposed and analyzed. Specifically, the use of effective LLL reduction for lattice decoding is presented, where size reduction is only performed for pairs of consecutive basis vectors. Its average complexity (measured by the number of floating-point operations and averaged over i.i.d. standard normal lattice bases) is shown to be O(n^3 log n), where n is the lattice dimension. This average complexity is an order lower than previously thought. To address the issue of variable complexity of the LLL algorithm, two fixed-complexity approximations are proposed. One is fixed-complexity effective LLL, for which the first vector of the basis is proven to be bounded in length; the other is fixed-complexity LLL with deep insertion, which is shown to be closely related to the well known V-BLAST algorithm. Such fixed-complexity structures are much desirable in hardware implementation since they allow straightforward constant-throughput implementation.
Starting Page	1040
Ending Page	1050
Page Count	11
File Size	431172
File Format	PDF
ISSN	00906778
Volume Number	61
Issue Number	3
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2013-03-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Complexity theory Vectors Lattices Standards Decoding Approximation algorithms Matrix decomposition multi-input multi-output communications Fixed-complexity implementation lattice coding lattice reduction LLL algorithm
Content Type	Text
Resource Type	Article
Subject	Electrical and Electronic Engineering

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Research Progress of Lattice Bases Reduction Algorithms

Fixed-Complexity LLL-Based Signal Detection for MIMO Systems

HKZ and Minkowski Reduction Algorithms for Lattice-Reduction-Aided MIMO Detection

Full-Diversity Approximated Lattice Reduction Algorithm for Low-Complexity MIMO Detection

Random selection LLL algorithm and its fixed complexity variant for MIMO detection

A Diagonal Lattice Reduction Algorithm for MIMO Detection

Complex lattice reduction algorithms for low-complexity MIMO detection (2006)

A fast complex lattice reduction algorithm for SIC-based MIMO detection

Complex lattice reduction algorithm for low-complexity mimo detection (2006).

Reduced and Fixed-Complexity Variants of the LLL Algorithm for Communications

Similar Documents

Research Progress of Lattice Bases Reduction Algorithms

Fixed-Complexity LLL-Based Signal Detection for MIMO Systems

HKZ and Minkowski Reduction Algorithms for Lattice-Reduction-Aided MIMO Detection

Full-Diversity Approximated Lattice Reduction Algorithm for Low-Complexity MIMO Detection

Random selection LLL algorithm and its fixed complexity variant for MIMO detection

A Diagonal Lattice Reduction Algorithm for MIMO Detection

Complex lattice reduction algorithms for low-complexity MIMO detection (2006)

A fast complex lattice reduction algorithm for SIC-based MIMO detection

Complex lattice reduction algorithm for low-complexity mimo detection (2006).

Reduced and Fixed-Complexity Variants of the LLL Algorithm for Communications