{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:55:39Z","timestamp":1760241339462,"version":"build-2065373602"},"reference-count":29,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2018,1,19]],"date-time":"2018-01-19T00:00:00Z","timestamp":1516320000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>The Lenstra-Lenstra-Lov\u00e1sz (LLL) lattice reduction algorithm and many of its variants have been widely used by cryptography, multiple-input-multiple-output (MIMO) communication systems and carrier phase positioning in global navigation satellite system (GNSS) to solve the integer least squares (ILS) problem. In this paper, we propose an n-dimensional LLL reduction algorithm (n-LLL), expanding the Lov\u00e1sz condition in LLL algorithm to n-dimensional space in order to obtain a further reduced basis. We also introduce pivoted Householder reflection into the algorithm to optimize the reduction time. For an m-order positive definite matrix, analysis shows that the n-LLL reduction algorithm will converge within finite steps and always produce better results than the original LLL reduction algorithm with n &gt; 2. The simulations clearly prove that n-LLL is better than the original LLL in reducing the condition number of an ill-conditioned input matrix with 39% improvement on average for typical cases, which can significantly reduce the searching space for solving ILS problem. The simulation results also show that the pivoted reflection has significantly declined the number of swaps in the algorithm by 57%, making n-LLL a more practical reduction algorithm.<\/jats:p>","DOI":"10.3390\/s18010283","type":"journal-article","created":{"date-parts":[[2018,1,22]],"date-time":"2018-01-22T04:51:13Z","timestamp":1516596673000},"page":"283","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["N-Dimensional LLL Reduction Algorithm with Pivoted Reflection"],"prefix":"10.3390","volume":"18","author":[{"given":"Zhongliang","family":"Deng","sequence":"first","affiliation":[{"name":"School of Electronic Engineering, Beijing University of Posts and Telecommunications, No. 10 Xitucheng Road, Beijing 100876, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Di","family":"Zhu","sequence":"additional","affiliation":[{"name":"School of Electronic Engineering, Beijing University of Posts and Telecommunications, No. 10 Xitucheng Road, Beijing 100876, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4978-8439","authenticated-orcid":false,"given":"Lu","family":"Yin","sequence":"additional","affiliation":[{"name":"School of Electronic Engineering, Beijing University of Posts and Telecommunications, No. 10 Xitucheng Road, Beijing 100876, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2018,1,19]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1002\/1099-1247(200007\/10)18:4\/5<223::AID-SAT660>3.0.CO;2-J","article-title":"Implementation of a european infrastructure for satellite navigation: From system design to advanced technology evaluation","volume":"18","author":"Provenzano","year":"2015","journal-title":"Int. J. Satell. Commun. Netw."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1007\/s00190-008-0300-3","article-title":"The international GNSS service in a changing landscape of global navigation satellite systems","volume":"83","author":"Dow","year":"2009","journal-title":"J. Geodesy"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1127\/pfg\/2016\/0284","article-title":"Accuracy analysis of photogrammetric UAV image blocks: Influence of onboard RTK-GNSS and cross flight patterns","volume":"2016","author":"Gerke","year":"2016","journal-title":"Photogramm. Fernerkund. Geoinf."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Tahar, K.N., Ahmad, A., Wan, A.A.W.M.A., and Wan, M.N.W.M. (2013). Unmanned aerial vehicle photogrammetric results using different real time kinematic global positioning system approaches. Lecture Notes in Geoinformation & Cartography, Springer.","DOI":"10.1007\/978-3-642-36379-5_8"},{"key":"ref_5","unstructured":"Woo, H.J., Yoon, B.J., Cho, B.G., and Kim, J.H. (2009, January 18\u201321). Research into navigation algorithm for unmanned ground vehicle using real time kinemtatic (RTK)-GPS. Proceedings of the 2009 ICCAS-SICE, Fukuoka, Japan."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Hatch, R. (1991). Instantaneous Ambiguity Resolution, Springer.","DOI":"10.1007\/978-1-4612-3102-8_27"},{"key":"ref_7","unstructured":"Forssell, B., Martinneira, M., and Harrisz, R.A. (1997, January 16\u201319). Carrier phase ambiguity resolution in GNSS-2. Proceedings of the 10th International Technical Meeting of the Satellite Division of The Institute of Navigation (ION GPS 1997), Kansas City, MO, USA."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/BF00863419","article-title":"The least-squares ambiguity decorrelation adjustment: A method for fast GPS integer ambiguity estimation","volume":"70","author":"Teunissen","year":"1995","journal-title":"J. Geodesy"},{"key":"ref_9","unstructured":"Teunissen, P.J.G. (, January August). Least-Squares Estimation of the Integer GPS Ambiguities. Invited lecture, Section IV \u201cTheory and Methodology\u201d. Proceedings of the General Meeting of the International Association of Geodesy, Beijing, China."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"408","DOI":"10.1007\/s001900100192","article-title":"Random simulation and gps decorrelation","volume":"75","author":"Xu","year":"2001","journal-title":"J. Geodesy"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"552","DOI":"10.1007\/s00190-005-0004-x","article-title":"MLAMBDA: A modified LAMBDA method for integer least-squares estimation","volume":"79","author":"Chang","year":"2005","journal-title":"J. Geodesy"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/s00190-011-0490-y","article-title":"Parallel cholesky-based reduction for the weighted integer least squares problem","volume":"86","author":"Xu","year":"2012","journal-title":"J. Geodesy"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"2938","DOI":"10.1109\/78.726808","article-title":"Integer parameter estimation in linear models with applications to GPS","volume":"46","author":"Hassibi","year":"1998","journal-title":"IEEE Trans. Signal Process."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1007\/BF01457454","article-title":"Factoring polynomials with rational coefficients","volume":"261","author":"Lenstra","year":"1982","journal-title":"Math. Ann."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"1965","DOI":"10.1109\/LCOMM.2017.2712600","article-title":"GfcLLL: A greedy selection-based approach for fixed-complexity LLL Reduction","volume":"21","author":"Wen","year":"2017","journal-title":"IEEE Commun. Lett."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"4801","DOI":"10.1109\/TIT.2007.909169","article-title":"LLL reduction achieves the receive diversity in MIMO decoding","volume":"53","author":"Taherzadeh","year":"2007","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_17","first-page":"2701","article-title":"Complex lattice reduction algorithm for low-complexity MIMO detection","volume":"5","author":"Ying","year":"2006","journal-title":"IEEE Trans. Signal Process."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1007\/PL00012840","article-title":"Mixed integer-real valued adjustment (IRA) problems: GPS initial cycle ambiguity resolution by means of the LLL algorithm","volume":"4","author":"Grafarend","year":"2000","journal-title":"GPS Solut."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Ngu\u00ean, P.Q., and Stehl\u00e9, D. (2005). Floating-Point LLL Revisited, Springer.","DOI":"10.1007\/11426639_13"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/BF01581144","article-title":"Lattice basis reduction: Improved practical algorithms and solving subset sum problems","volume":"66","author":"Schnorr","year":"1994","journal-title":"Math. Program."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1016\/0304-3975(87)90064-8","article-title":"A hierarchy of polynomial time basis reduction algorithms","volume":"53","author":"Schnorr","year":"1987","journal-title":"Theor. Comput. Sci."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1007\/s10623-014-9918-8","article-title":"PotLLL: A polynomial time version of LLL with deep insertions","volume":"73","author":"Fontein","year":"2014","journal-title":"Des. Codes Cryptogr."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Babai, L. (1985, January 3\u20135). On Lov\u00e1sz\u2019 lattice reduction and the nearest lattice point problem. Proceedings of the STACS 85 Symposium on Theoretical Aspects of Computer Science, Saarbr\u00fccken, Germany.","DOI":"10.1007\/BFb0023990"},{"key":"ref_24","unstructured":"W\u00fcbben, D., Bohnke, R., Ku\u0308Hn, V., and Kammeyer, K.D. (2003, January 6\u20139). MMSE extension of V-BLAST based on sorted QR decomposition. Proceedings of the Vehicular Technology Conference, Orlando, FL, USA."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"1634","DOI":"10.1109\/TSP.2008.2011827","article-title":"Fixed complexity LLL algorithm","volume":"57","author":"Vetter","year":"2009","journal-title":"IEEE Trans. Signal Process."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1179\/1752270612Y.0000000029","article-title":"On \u201cdecorrelation\u201d in solving integer least-squares problems for ambiguity determination","volume":"46","author":"Borno","year":"2014","journal-title":"Emp. Surv. Rev."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"3122","DOI":"10.1109\/TIT.2006.883538","article-title":"Voronoi cells, probabilistic bounds, and hypothesis testing in mixed integer linear models","volume":"52","author":"Xu","year":"2006","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_28","unstructured":"Jonge, P.P.D., and Tiberius, C. (1994, January 20\u201323). On the spectrum of the GPS DD-ambiguities. Proceedings of the 7th International Technical Meeting of the Satellite Division of the Institute of Navigation, Salt Lake City, UT, USA."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1007\/s001900050127","article-title":"The least-squares ambiguity decorrelation adjustment: Its performance on short GPS baselines and short observation spans","volume":"71","author":"Teunissen","year":"1997","journal-title":"J. Geodesy"}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/18\/1\/283\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T14:51:52Z","timestamp":1760194312000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/18\/1\/283"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1,19]]},"references-count":29,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2018,1]]}},"alternative-id":["s18010283"],"URL":"https:\/\/doi.org\/10.3390\/s18010283","relation":{},"ISSN":["1424-8220"],"issn-type":[{"type":"electronic","value":"1424-8220"}],"subject":[],"published":{"date-parts":[[2018,1,19]]}}}