Skip to main content
Springer Nature Link
Log in

Algorithm and VLSI Implementation of K-Best Detection

  • Chapter
  • First Online:
Algorithms and VLSI Implementations of MIMO Detection

  • 335 Accesses

Abstract

The application of QR decomposition to the channel matrix transforms signal detection in a multiple-input multiple-output (MIMO) system into a tree search where the number of levels corresponds with the number of antennas, and the number of branches per node corresponds with the constellation points. The K-best detector utilises a breadth-first tree search strategy where a fixed number of nodes are extended from a level which gives it a constant complexity irrespective of the signal-to-noise (SNR) ratio. Unlike the depth-first sphere decoder, the K-best detector is well suited to a feed-forward pipelined hardware implementation which makes it a good candidate for applications requiring a high throughput performance. However, due to its breadth-first tree search, the K-best has a suboptimal performance compared to the maximum likelihood detector. In this chapter, we discuss the K-best algorithm in detail and provide the hardware implementation results of a K-best detector achieving a throughput of 3.2 Gbps at a clock frequency of 137 MHz and post-layout area of 2.74 mm2 for a 64-QAM 4 × 4 MIMO communication system.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
eBook
USD 79.99
Price excludes VAT (USA)
Softcover Book
USD 99.99
Price excludes VAT (USA)
Hardcover Book
USD 99.99
Price excludes VAT (USA)

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    The other case is when K = M. In this case, sorting is not required at the topmost level, and all the nodes are extended to the second level. In the sorting and path update steps at the second level, the nodes at the first level will be automatically reordered according to their PEDs.

  2. 2.

    The use of “first” here counter-intuitively refers to level 8, while the “last” level refers to level 1. This is because the tree search detection is done in reverse, from the topmost level at i = 2N T to the leaf nodes corresponding to i = 1.

References

  1. A. Burg, M. Borgmann, M. Wenk, M. Zellweger, W. Fichtner, H. Bolcskei, VLSI implementation of MIMO detection using the sphere decoding algorithm. IEEE J. Solid State Circuits 40(7), 1566–1577 (2005)

    Article  Google Scholar 

  2. B. Hassibi, H. Vikalo, On the sphere-decoding algorithm I. Expected complexity. IEEE Trans. Signal Process. 53(8), 2806–2818 (2005)

    Article  MathSciNet  Google Scholar 

  3. K.-w. Wong, C.-y. Tsui, R.-K. Cheng, W.-H. Mow, A VLSI architecture of a K-best lattice decoding algorithm for MIMO channels, in IEEE International Symposium on Circuits and Systems, 2002. ISCAS 2002, vol. 3 (2002), pp. III-273–III-276

    Google Scholar 

  4. J. Yue, K.J. Kim, J. Gibson, R. Iltis, Channel estimation and data detection for MIMO-OFDM systems, in IEEE Global Telecommunications Conference (IEEE Cat. No.03CH37489). GLOBECOM ’03, vol. 2 (2003), pp. 581–585

    Google Scholar 

  5. B.-s. Kim, K. Choi, A very low complexity QRD-M algorithm based on limited tree search for MIMO systems, in VTC Spring 2008 – IEEE Vehicular Technology Conference (2008), pp. 1246–1250. ISSN: 1550-2252

    Google Scholar 

  6. F. Jelinek, J Anderson, Instrumentable tree encoding of information sources (Cor-resp.). IEEE Trans. Inf. Theory 17(1), 118–119 (1971)

    Google Scholar 

  7. L. Barbero, J. Thompson, Rapid prototyping of a fixed-throughput sphere decoder for MIMO systems, in IEEE International Conference on Communications, 2006. ICC’06, vol. 7 (2006), pp. 3082–3087

    Google Scholar 

  8. L.G. Barbero, J.S. Thompson, Rapid prototyping of the sphere decoder for MIMO systems, in 2nd IEE/EURASIP Conference on DSPenabledRadio (2005), pp. 4–4

    Google Scholar 

  9. X. Chen, G. He, J. Ma, VLSI implementation of a high-throughput iterative fixed-complexity sphere decoder. IEEE Trans. Circuits Syst. Express Briefs 60(5), 272–276 (2013)

    Article  Google Scholar 

  10. L. Liu, J. Lofgren, P. Nilsson, Area-efficient configurable high-throughput signal detector supporting multiple MIMO modes. IEEE Trans. Circuits Syst. Regul. Pap. 59(9), 2085–2096 (2012)

    Article  MathSciNet  Google Scholar 

  11. M. Wenk, M. Zellweger, A. Burg, N. Felber, W. Fichtner, K-best MIMO detection VLSI architectures achieving up to 424 Mbps, in Proceedings of the 2006 IEEE International Symposium on Circuits and Systems, 2006. ISCAS 2006. (2006), pp. 1151–1154

    Google Scholar 

  12. M. Shabany, P. Gulak, Scalable VLSI architecture for K-best lattice decoders, in IEEE International Symposium on Circuits and Systems, 2008. ISCAS 2008 (2008), pp. 940–943

    Google Scholar 

  13. S. Mondal, A. Eltawil, C.-A. Shen, K. Salama, Design and implementation of a sort-free K-best sphere decoder. IEEE Trans. Very Large Scale Integr. VLSI Syst. 18(10), 1497–1501 (2010)

    Article  Google Scholar 

  14. K.E. Batcher, Sorting networks and their applications, in Proceedings of the April 30–May 2, 1968, Spring Joint Computer Conference (ACM, New York, 1968), pp. 307–314

    Google Scholar 

  15. T.-H. Kim, I.-C. Park, Small-area and low-energy-best MIMO detector using relaxed tree expansion and early forwarding. IEEE Trans. Circuits Syst. Regul. Pap. 57(10), 2753–2761 (2010)

    Article  MathSciNet  Google Scholar 

  16. Y. Dai, S. Sun, Z. Lei, A comparative study of QRD-M detection and sphere decoding for MIMO-OFDM systems, in IEEE 16th International Symposium on Personal, Indoor and Mobile Radio Communications, 2005. PIMRC 2005, vol. 1 (2005), pp. 186–190

    Google Scholar 

  17. Z. Guo, P. Nilsson, Algorithm and implementation of the K-best sphere decoding for MIMO detection. IEEE J. Select. Areas Commun. 24(3), 491–503 (2006)

    Article  Google Scholar 

  18. M. Shabany, P. Gulak, A 0.13μm CMOS 655Mb/s 4x4 64-QAM K-best MIMO detector, in IEEE International on Solid-State Circuits Conference – Digest of Technical Papers, 2009. ISSCC 2009 (2009). pp. 256–257

    Google Scholar 

  19. S. Mondal, K.N. Salama, W.H. Ali, A novel approach for K-Best MIMO detection and its VLSI implementation, in IEEE International Symposium on Circuits and Systems, 2008. ISCAS 2008. (2008), pp. 936–939

    Google Scholar 

  20. L. Azzam, E. Ayanoglu, Reduced complexity sphere decoding for square QAM via a new lattice representation, in IEEE Global Telecommunications Conference, 2007. GLOBECOM /07 (2007), pp. 4242–4246

    Google Scholar 

  21. N. Moezzi-Madani, T. Thorolfsson, P. Chiang, W.R. Davis, Area-efficient antenna-scalable MIMO detector for K-best sphere decoding. J. Signal Process. Syst. 68(2), 171–182 (2012)

    Article  Google Scholar 

  22. I.A. Bello, B. Halak, M. El-Hajjar, M. Zwolinski, VLSI implementation of a scalable K-best MIMO detector, in 2015 15th International Symposium on Communications and Information Technologies (ISCIT) (2015), pp. 281–286

    Google Scholar 

  23. M. Mahdavi, M. Shabany, A 13 Gbps, 0.13 μm CMOS, multiplication-free MIMO detector. J. Sign. Process. Syst. 88(3), 273–285 (2016)

    Google Scholar 

  24. I.A. Bello, B. Halak, M. El-Hajjar, M. Zwolinski, VLSI implementation of a fully-pipelined K-best MIMO detector with successive interference cancellation. Circuits Systems Signal Process. 38(10), 4739–4761 (2019)

    Article  Google Scholar 

  25. A. Wiesel, X. Mestre, A. Pages, J. Fonollosa, Efficient implementation of sphere demodulation, in 4th IEEE Workshop on Signal Processing Advances in Wireless Communications, 2003. SPAWC 2003 (2003), pp. 36–40

    Google Scholar 

  26. S.-H. Kang, I.-C. Park, High speed sphere decoding based on vertically incremental computation, in IEEE International Symposium on Circuits and Systems, 2007 ISCAS 2007 (2007), pp. 665–668

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dyson Technology Ltd., Bristol, UK

    Ibrahim Bello

  2. University of Southampton, Southampton, UK

    Basel Halak

Authors
  1. Ibrahim Bello
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Basel Halak
    View author publications

    You can also search for this author in PubMed Google Scholar

Appendix

Appendix

The MATLAB code for the K-best detector based on the Schnorr–Euchner enumeration is provided in Listing 4.1.

Listing 4.1 K-best algorithm MATLAB implementation

Rights and permissions

Reprints and permissions

Copyright information

© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this chapter

Check for updates. Verify currency and authenticity via CrossMark

Cite this chapter

Bello, I., Halak, B. (2022). Algorithm and VLSI Implementation of K-Best Detection. In: Algorithms and VLSI Implementations of MIMO Detection. Springer, Cham. https://doi.org/10.1007/978-3-031-04512-7_4

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-04512-7_4

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-04511-0

  • Online ISBN: 978-3-031-04512-7

  • eBook Packages: EngineeringEngineering (R0)

Publish with us

Policies and ethics

Search

Navigation