An Analysis of Valid Nodes Distribution for Sphere Decoding in the MIMO Wireless Communication System

  • Nguyễn Minh Thường VCNTT
  • Xuan Nam Tran
  • Vũ Đức Ngô
  • Quang Kiên Trịnh
  • Đức Thắng Nguyễn
  • Tiến Anh Vũ
Keywords: Multi-input multi-output (MIMO), maximum likelihood (ML), Sphere Decoding (SD)


Sphere Decoding (SD) algorithms can achieve a quasi-maximum likelihood (ML) decoder performance over Gaussian multiple input-multiple output (MIMO) channels with much lower complexity compared to the exhaustive search method. The SD algorithm is based on a closest lattice point search over a limited search space (hypersphere). On top of that, QR-decomposition simplifies the SD linear system's matrix to be an upper triangle matrix. The solution solver then is done by searching in the exponentially expanding search tree, started from the top with only a single node then increases by M times every level (in $N_T\times N_R$ MIMO system). Fortunately, the SD algorithm shrinks its hypersphere at every level (once the level node is determined) and phases out a vast number of the candidates, remaining only specific valid nodes in the current considered level. In this work, we proposed the statistical approach for evaluating the adequate number of valid search nodes at every level of the search tree, aiming to optimize the overall computational workload. We use a massive number of inputs patterns and extensive simulation to project the number of remaining valid nodes during the searching process. The simulations have been conducted for $4\times 4$ and $8\times 8$ MIMO systems. Our results indicate that for a particular targeted BER, choosing an appropriate sphere radius is essentially important and the number of necessary calculations increases only at the middle layer and can be generically quantified regardless of the system characteristics. This finding is beneficial for the hardware implementation of the SD, where the number of computational units has to be fixed in advance.


E. Telatar, "Capacity of multi-antenna Gaussian channels," Eur. Trans. Telecommun., vol. 10, no. 6, pp. 585-596, 1999.

X. Chen, S. Zhang and Q. Li, "A Review of Mutual Coupling in MIMO Systems," IEEE Access, vol. 6, pp. 24706-24719, 2018.

U. Fincke, M. Pohst, "Improved methods for calculating vectors of short length," Mathematics of Computation, 1985.

M. Pohst, "On the computation of lattice vectors of minimal length, successive minima," SIGSAM Bull., vol. 15, no. 1, pp. 37-44, 1981.

H. Jang, S. Nooshabadi, K. Kim and H. Lee, "Circular Sphere Decoding: A Low Complexity Detection for MIMO

Systems With General Two-dimensional Signal Constellations," IEEE Transactions on Vehicular Technology, vol. 66, no. 3, pp. 2085-2098, March 2017.

W. Hwang, J. Park, J. Kim and H. -S. Lim, "Optimal Precoder Selection for Spatially Multiplexed Multiple-Input

Multiple-Output Systems With Maximum Likelihood Detection: Exploiting the Concept of Sphere Decoding," IEEE

Access, vol. 8, pp. 223859-223868, 2020.

J. Liu, S. Xing and L. Shen, "Lattice-Reduction-Aided Breadth-First Tree Searching Algorithm for MIMO Detection," IEEE Communications Letters, vol. 21, no. 4, pp. 845- 848, April 2017

C. P. Schnorr and M. Euchner, "Lattice Basis Reduction: Improved Practical Algorithms and Solving Subset Sum Problems," Math. Program, vol. 66, p. 181-191, 1994.

X. Nguyen, M. Le, N. Pham and V. Ngo, "A pipelined Schnorr-Euchner sphere decoder architecture for MIMO systems," 2015 International Conference on Advanced Technologies for Communications (ATC), Ho Chi Minh, Viet Nam, 2015.

B. Shim and I. Kang, "Sphere Decoding With a Probabilistic Tree Pruning," IEEE Transactions on Signal Processing, vol. 56, no. 10, pp. 4867-4878, Oct. 2008

K. Nikitopoulos, A. Karachalios and D. Reisis, "Exact MaxLog MAP Soft-Output Sphere Decoding via Approximate Schnorr–Euchner Enumeration," IEEE Transactions on Vehicular Technology, vol. 64, no. 6, pp. 2749-2753, June 2015

I.A. Bello, B. Halak, M. El-Hajjar, et al. "VLSI Implementation of a Fully-Pipelined K-Best MIMO Detector with

Successive Interference Cancellation" Circuits Syst Signal Process 38, 4739-4761, 2019.

Y. Ding, N. Li, Y. Wang, S. Feng and H. Chen, "Widely Linear Sphere Decoder in MIMO Systems by Exploiting the Conjugate Symmetry of Linearly Modulated Signals," IEEE Transactions on Signal Processing, vol. 64, no. 24, pp. 6428- 6442, 15 Dec.15, 2016

X. Jun, G. Diyuan and W. Zengye, "Research of Improved Sphere Decoding Algorithm," 2019 Chinese Control And Decision Conference (CCDC), pp. 1043-1047, 2019.

B. Shim and I. Kang, "Sphere Decoding With a Probabilistic Tree Pruning," IEEE Transactions on Signal Processing, vol. 56, pp. 4867-4878, Oct. 2008.

Y. Sonoda and H. Zhao, "Improved sphere decoding algorithm with low complexity for MIMO systems," 2014

IEEE/CIC International Conference on Communications in China (ICCC), pp. 11-15, 2014.

M. -T. Nguyen, V. -D. Ngo, X. -N. Tran and M. -T. Le, "Design and Implementation of Signal Processing Unit

for Two-Way Relay Node in MIMO-SDM-PNC System," 2019 26th International Conference on Telecommunications (ICT), 2019

Trần Xuân Nam, Lê Minh Tuấn, "Xử lý tín hiệu không gian thời gian", Nhà xuất bản khoa học và kỹ thuật, 2013