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.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 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.
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
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)
B. Hassibi, H. Vikalo, On the sphere-decoding algorithm I. Expected complexity. IEEE Trans. Signal Process. 53(8), 2806–2818 (2005)
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
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
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
F. Jelinek, J Anderson, Instrumentable tree encoding of information sources (Cor-resp.). IEEE Trans. Inf. Theory 17(1), 118–119 (1971)
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
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
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)
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)
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
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
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)
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
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)
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
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)
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
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
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
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)
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
M. Mahdavi, M. Shabany, A 13 Gbps, 0.13 μm CMOS, multiplication-free MIMO detector. J. Sign. Process. Syst. 88(3), 273–285 (2016)
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)
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
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
Author information
Authors and Affiliations
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
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this chapter
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)