More Web Proxy on the site http://driver.im/

research-article

Efficient Greedy LLL Algorithms for Lattice Decoding

Authors:

Xiaoli MaAuthors Info & Claims

IEEE Transactions on Wireless Communications, Volume 15, Issue 5

Pages 3560 - 3572

https://doi.org/10.1109/TWC.2016.2523513

Published: 01 May 2016 Publication History

Abstract

The Lenstra-Lenstra-Lovász (LLL) algorithm has been adopted as a lattice reduction (LR) technique for multiple-input multiple-output (MIMO) communications to improve performance with low complexity. However, implementing the LLL algorithm is still challenging due to slow convergence especially for large channel matrices. One of the main reasons is that the column swap may not happen in some LLL iterations, which leads to more iterations. To address it, some greedy LLL algorithms have recently been proposed, which only perform the iterations with column swaps. In this paper, we propose two efficient greedy LLL algorithms for various LR-aided MIMO detectors. First, both algorithms use a relaxed Lovász condition to search the candidate set of LLL iterations. Then, to select an LLL iteration in the candidate set each time, one is based on a relaxed decrescence of LLL potential, and the other takes the error performance of the LR-aided MIMO detectors into consideration. The proposed two algorithms are proved to collect full receive diversity in both LR-aided linear and successive-interference-cancellation detectors. Furthermore, compared to existing greedy LLL algorithms, simulations show that the proposed two algorithms not only converge faster but also exhibit much lower complexity while maintaining comparable error performance in LR-aided MIMO detectors.

References

[1]

A. Paulraj, D. Gore, R. Nabar, and H. Bolcskei, “An overview of MIMO communications—A key to gigabit wireless,” Proc. IEEE, vol. 92, no. 2, pp. 198–218, Feb. 2004.

[2]

J. Mietzner, R. Schober, L. Lampe, W. H. Gerstacker, and P. A. Hoeher, “Multiple-antenna techniques for wireless communications—A comprehensive literature survey,” IEEE Commun. Surveys Tuts., vol. 11, no. 2, pp. 87–105, Second Quart. 2009.

[3]

E. G. Larsson, “MIMO detection methods: How they work,” IEEE Signal Process. Mag., vol. 26, no. 3, pp. 91–95, May 2009.

[4]

D. Tse and P. Viswanath, Fundamentals of Wireless Communication. Cambridge, U.K.: Cambridge Univ. Press, 2005.

[5]

E. Agrell, T. Eriksson, A. Vardy, and K. Zeger, “Closest point search in lattices,” IEEE Trans. Inf. Theory, vol. 48, no. 8, pp. 2201–2214, Aug. 2002.

Digital Library

[6]

J. Jaldén and B. Ottersten, “On the complexity of sphere decoding in digital communications,” IEEE Trans. Signal Process., vol. 53, no. 4, pp. 1474–1484, Apr. 2005.

Digital Library

[7]

W. Zhang and X. Ma, “Lattice reduction aided equalization for wireless applications,” in The Digital Signal Processing Handbook, 2nd ed., V. Madisetti, Ed. Boca Raton, FL, USA: CRC Press, 2009, ch. 30, pp. 30-1–30-16.

[8]

D. Wübben, D. Seethaler, J. Jaldén, and G. Matz, “Lattice reduction,” IEEE Signal Process. Mag., vol. 28, no. 3, pp. 70–91, May 2011.

[9]

H. Yao and G. W. Wornell, “Lattice-reduction-aided detectors for MIMO communication systems,” in Proc. IEEE Global Telecommun. Conf. (GLOBECOM), Taipei, Taiwan, Nov. 2002, pp. 424–428.

[10]

C. Windpassinger and R. Fischer, “Low-complexity near-maximum-likelihood detection and precoding for MIMO systems using lattice reduction,” in Proc. IEEE Inf. Theory Workshop (ITW), Paris, France, Mar. 2003, pp. 345–348.

[11]

M. Taherzadeh, A. Mobasher, and A. Khandani, “LLL reduction achieves the receive diversity in MIMO decoding,” IEEE Trans. Inf. Theory, vol. 53, no. 12, pp. 4801–4805, Dec. 2007.

Digital Library

[12]

W. H. Mow, “Universal lattice decoding: A review and some recent results,” in Proc. IEEE Int. Conf. Commun. (ICC), Paris, France, Jun. 2004, pp. 2842–2846.

[13]

X. Ma and W. Zhang, “Performance analysis for MIMO systems with lattice-reduction aided linear equalization,” IEEE Trans. Commun., vol. 56, no. 2, pp. 309–318, Feb. 2008.

[14]

Y. H. Gan, C. Ling, and W. H. Mow, “Complex lattice reduction algorithm for low-complexity full-diversity MIMO detection,” IEEE Trans. Signal Process., vol. 57, no. 7, pp. 2701–2710, Jul. 2009.

Digital Library

[15]

D. Wübben, R. Böhnke, V. Kühn, and K. D. Kammeyer, “Near-maximum-likelihood detection of MIMO systems using MMSE-based lattice reduction,” in Proc. IEEE Int. Conf. Commun. (ICC), vol. 2, Paris, France, Jun. 2004, pp. 798–802.

[16]

M. Shabany and P. Glenn Gulak, “The application of lattice-reduction to the K-Best algorithm for near-optimal MIMO detection,” in Proc. IEEE Int. Symp. Circuits Syst. (ISCAS), Seattle, WA, USA, May 2008, pp. 316–319.

[17]

Q. Zhou and X. Ma, “An improved LR-aided K-best algorithm for MIMO detection,” in Proc. IEEE Int. Conf. Wireless Commun. Signal Process. (WCSP), Huangshan, China, Oct. 2012, pp. 1–5.

[18]

Q. Wen, Q. Zhou, C. Zhao, and X. Ma, “Fixed-point realization of lattice-reduction aided MIMO receivers with complex K-best algorithm,” in Proc. IEEE Int. Conf. Acoust. Speech Signal Process. (ICASSP), Vancouver, BC, Canada, May 2013, pp. 5031–5035.

[19]

D. Seethaler, G. Matz, and F. Hlawatsch, “Low-complexity MIMO data detection using Seysen’s lattice reduction algorithm,” in Proc. IEEE Int. Conf. Acoust. Speech Signal Process. (ICASSP), Honolulu, HI, USA, Apr. 2007, pp. 53–56.

[20]

W. Zhang, X. Ma, and A. Swami, “Designing low-complexity detectors based on Seysen’s algorithm,” IEEE Trans. Wireless Commun., vol. 9, no. 10, pp. 3301–3311, Oct. 2010.

Digital Library

[21]

N.-C. Wang, E. Biglieri, and K. Yao, “Systolic arrays for lattice-reduction-aided MIMO detection,” J. Commun. Netw., vol. 13, no. 5, pp. 481–493, Oct. 2011.

[22]

B. Gestner, W. Zhang, X. Ma, and D. Anderson, “Lattice reduction for MIMO detection: From theoretical analysis to hardware realization,” IEEE Trans. Circuits Syst. I, Reg. Papers, vol. 58, no. 4, pp. 813–826, Apr. 2011.

[23]

M. Shabany, A. Youssef, and G. Gulak, “High-throughput 0.13-CMOS lattice reduction core supporting 880 Mb/s detection,” IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol. 21, no. 5, pp. 848–861, May 2013.

Digital Library

[24]

C. Senning, L. Bruderer, J. Hunziker, and A. Burg, “A lattice reduction-aided MIMO channel equalizer in 90 nm CMOS achieving 720 Mb/s,” IEEE Trans. Circuits Syst. I, Reg. Papers, vol. 61, no. 6, pp. 1860–1871, Jun. 2014.

[25]

A. K. Lenstra, H. W. Lenstra, and L. Lovász, “Factoring polynomials with rational coefficients,” Math. Ann., vol. 261, no. 4, pp. 515–534, 1982.

[26]

J. Jaldén, D. Seethaler, and G. Matz, “Worst-and average-case complexity of LLL lattice reduction in MIMO wireless systems,” in Proc. IEEE Int. Conf. Acoust. Speech Signal Process. (ICASSP), Las Vegas, NV, USA, Mar. 2008, pp. 2685–2688.

[27]

C. Ling, “Approximate lattice decoding: Primal versus dual basis reduction,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Seattle, WA, USA, Jul. 2006, pp. 1–5.

[28]

D. Wübben and D. Seethaler, “On the performance of lattice reduction schemes for MIMO data detection,” in Proc. Asilomar Conf. Signals Syst. Comput., Pacific Grove, CA, USA, Nov. 2007, pp. 1534–1538.

[29]

M. Seysen, “Simultaneous reduction of a lattice basis and its reciprocal basis,” Combinatorica, vol. 13, no. 3, pp. 363–376, Sep. 1993.

[30]

L. G. Barbero, T. Ratnarajah, and C. Cowan, “A comparison of complex lattice reduction algorithms for MIMO detection,” in Proc. IEEE Int. Conf. Acoust. Speech Signal Process. (ICASSP), Las Vegas, NV, USA, Mar. 2008, pp. 2705–2708.

[31]

K. Zhao, Y. Li, H. Jiang, and S. Du, “A low complexity fast lattice reduction algorithm for MIMO detection,” in Proc. IEEE Int. Symp. Pers. Indoor Mobile Radio Commun. (PIMRC), Sydney, Australia, Sep. 2012, pp. 1612–1616.

[32]

W. Zhang, S. Qiao, and Y. Wei, “A diagonal lattice reduction algorithm for MIMO detection,” IEEE Signal Process. Lett., vol. 19, no. 5, pp. 311–314, May 2012.

[33]

Q. Wen and X. Ma, “An efficient Greedy LLL algorithm for MIMO detection,” in Proc. Military Commu. Conf. (MILCOM), Baltimore, MD, USA, Oct. 2014, pp. 550–555.

[34]

D. Wübben, R. Böhnke, V. Kühn, and K. D. Kammeyer, “MMSE extension of V-BLAST based on sorted QR decomposition,” in Proc. IEEE 58th Veh. Technol. Conf. (VTC2003-Fall), Orlando, FL, USA, Oct. 2003, pp. 508–512.

[35]

A. Murugan, H. El Gamal, M. O. Damen, and G. Caire, “A unified framework for tree search decoding: Rediscovering the sequential decoder,” IEEE Trans. Inf. Theory, vol. 52, no. 3, pp. 933–953, Mar. 2006.

Digital Library

[36]

J. C. Lagarias, H. W. Lenstra Jr., and C.-P. Schnorr, “Korkin-zolotarev bases and successive minima of a lattice and its reciprocal lattice,” Combinatorica, vol. 10, no. 4, pp. 333–348, 1990.

[37]

C. Ling, “On the proximity factors of lattice reduction-aided decoding,” IEEE Trans. Signal Process., vol. 59, no. 6, pp. 2795–2808, Jun. 2011.

Digital Library

[38]

N. Howgrave-Graham, “Finding small roots of univariate modular equations revisited,” in Proc. 6th IMA Int. Conf. Crypt. Coding (IMACC), Cirencester, U.K., Dec. 1997, pp. 131–142.

Digital Library

[39]

C. Ling and N. Howgrave-Graham, “Effective LLL reduction for lattice decoding,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Nice, France, Jun. 2007, pp. 196–200.

[40]

Q. Zhou and X. Ma, “Element-based lattice reduction algorithms for large MIMO detection,” IEEE J. Sel. Areas Commun., vol. 31, no. 2, pp. 274–286, Feb. 2013.

[41]

V. Tarokh, H. Jafarkhani, and A. R. Calderbank, “Space-time block coding for wireless communications: Performance results,” IEEE J. Sel. Areas Commun., vol. 17, no. 3, pp. 451–460, Mar. 1999.

Digital Library

[42]

J. Choi and F. Adachi, “User selection criteria for multiuser systems with optimal and suboptimal LR based detectors,” IEEE Trans. Signal Process., vol. 58, no. 10, pp. 5463–5468, Oct. 2010.

Digital Library

[43]

J. G. Proakis, Digital Communications, 4th ed. New York, NY, USA: McGraw-Hill, 2001.

[44]

Z. Wang and G. B. Giannakis, “Complex-field coding for OFDM over fading wireless channels,” IEEE Trans. Inf. Theory, vol. 49, no. 3, pp. 707–720, Mar. 2003.

Digital Library

Cited By

Jiang HKong LDu S(2022)Vandermonde-Based Unitary Precoding Method for Integer-Forcing DesignWireless Communications & Mobile Computing10.1155/2022/35605142022Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1155/2022/3560514
Challa NBagadi K(2021)Design of Large Scale MU-MIMO System with Joint Precoding and Detection Schemes for Beyond 5G Wireless NetworksWireless Personal Communications: An International Journal10.1007/s11277-021-08688-6121:3(1627-1646)Online publication date: 1-Dec-2021
https://dl.acm.org/doi/10.1007/s11277-021-08688-6
Lyu SLing C(2017)Boosted KZ and LLL AlgorithmsIEEE Transactions on Signal Processing10.1109/TSP.2017.270802065:18(4784-4796)Online publication date: 12-Jul-2017
https://dl.acm.org/doi/10.1109/TSP.2017.2708020

Index Terms

Efficient Greedy LLL Algorithms for Lattice Decoding
1. Mathematics of computing
  1. Information theory
    1. Coding theory
  2. Mathematical analysis
2. Security and privacy
  1. Cryptography
    1. Mathematical foundations of cryptography

Index terms have been assigned to the content through auto-classification.

Recommendations

An Efficient Greedy LLL Algorithm for MIMO Detection
MILCOM '14: Proceedings of the 2014 IEEE Military Communications Conference

Lenstra-Lenstra-Lovász (LLL) algorithm has been adopted as a lattice reduction (LR) technique for multiple-input multiple-output (MIMO) detection to improve error performance without exponential complexity. However, implementing the LLL algorithm is ...
LLL Reduction Achieves the Receive Diversity in MIMO Decoding

Diversity order is an important measure for the performance of communication systems over multiple-input-multiple-output (MIMO) fading channels. In this correspondence, we prove that in MIMO multiple- access systems (or MIMO point-to-point systems with ...
Reduced-complexity LLL algorithm for lattice-reduction-aided MIMO detection
Asilomar'09: Proceedings of the 43rd Asilomar conference on Signals, systems and computers

In this paper, we propose a low-complexity constant-throughput LLL algorithm for lattice-reduction-aided (LRA) multi-input multi-output (MIMO) detection. The traditional LLL algorithm for the lattice reduction has a drawback of varying throughput due to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Wireless Communications

IEEE Transactions on Wireless Communications Volume 15, Issue 5

May 2016

678 pages

ISSN:1536-1276

Issue’s Table of Contents

Copyright © 2016.

Publisher

IEEE Press

Publication History

Published: 01 May 2016

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Jiang HKong LDu S(2022)Vandermonde-Based Unitary Precoding Method for Integer-Forcing DesignWireless Communications & Mobile Computing10.1155/2022/35605142022Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1155/2022/3560514
Challa NBagadi K(2021)Design of Large Scale MU-MIMO System with Joint Precoding and Detection Schemes for Beyond 5G Wireless NetworksWireless Personal Communications: An International Journal10.1007/s11277-021-08688-6121:3(1627-1646)Online publication date: 1-Dec-2021
https://dl.acm.org/doi/10.1007/s11277-021-08688-6
Lyu SLing C(2017)Boosted KZ and LLL AlgorithmsIEEE Transactions on Signal Processing10.1109/TSP.2017.270802065:18(4784-4796)Online publication date: 12-Jul-2017
https://dl.acm.org/doi/10.1109/TSP.2017.2708020

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents