Boosted KZ and LLL algorithms
File(s)1703.03303.pdf (502.06 KB)
Accepted version
Author(s)
Lyu, Shanxiang
Ling, Cong
Type
Journal Article
Abstract
There exist two issues among popular lattice reduction algorithms that should cause our concern. The first one is Korkine-Zolotarev (KZ) and Lenstra-Lenstra-Lovász (LLL) algorithms may increase the lengths of basis vectors. The other is KZ reduction suffers worse performance than Minkowski reduction in terms of providing short basis vectors, despite its superior theoretical upper bounds. To address these limitations, we improve the size reduction steps in KZ and LLL to set up two new efficient algorithms, referred to as boosted KZ and LLL, for solving the shortest basis problem with exponential and polynomial complexity, respectively. Both of them offer better actual performance than their classic counterparts, and the performance bounds for KZ are also improved. We apply them to designing integer-forcing (IF) linear receivers for multi-input multioutput communications. Our simulations confirm their rate and complexity advantages.
Date Issued
2017-09-15
Date Acceptance
2017-04-30
Citation
IEEE Transactions on Signal Processing, 2017, 65 (18), pp.4784-4796
ISSN
1053-587X
Publisher
Institute of Electrical and Electronics Engineers
Start Page
4784
End Page
4796
Journal / Book Title
IEEE Transactions on Signal Processing
Volume
65
Issue
18
Copyright Statement
© 2017 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Identifier
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000405705900007&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=1ba7043ffcc86c417c072aa74d649202
Subjects
Science & Technology
Technology
Engineering, Electrical & Electronic
Engineering
Lattice reduction
KZ
LLL
shortest basis problem
integer-forcing
LATTICE BASIS REDUCTION
LINEAR RECEIVERS
COMPLEXITY
SYSTEMS
Publication Status
Published
Date Publish Online
2017-05-24