Design and evaluation of sphere decoder accelerator on reconfiguration hardware



  • Nguyen Minh Thuong Academy of Military Science and Technology
  • Tran Xuan Nam Military Technical Academy
  • Nguyen Duc Thang Military Technical Academy
  • Vu Tien Anh Military Technical Academy
  • Trinh Quang Kien (Corresponding Author) Military Technical Academy





 The Maximum likelihood (ML) detection can achieve the best bit error rate but requires very high computational complexity. The latter makes this algorithm is not practically applicable. Many decoder architectures hence have been proposed to overcome the ML high complexity. The sphere decoding (SD) algorithm is one of the most promising approaches that offer quasi-ML performance with a reasonable computing workload. This paper proposes an efficient and practical approach for a sphere decoder design on reconfigurable hardware (FPGA). The design is evaluated to yield a quality approximation of the Maximum Likelihood (ML) method but with significantly reduced computational complexity.


[1]. T. X. Nam, L. M. Tuấn, Xử lý tín hiệu không gian thời gian, NXB Khoa học và kỹ thuật, (2013).

[2]. Zekry, Abdelhalim, "FPGA Implementation of Sphere Detector for Spatial Multiplexing MIMO System," International Journal of Electronics and Telecommunications, vol. 65, pp. 245–252, (2019).

[3]. M. O. Damen, H. E. Gamal, and G. Caire, "On maximum likelihood detection and the search for the closest lattice point," IEEE Trans. Inform. Theory, vol. 49, pp. 2389–2402, (2003).

[4]. U. Fincke, M. Pohst, "Improved methods for calculating vectors of short length," Mathematics of Computation, (1985).

[5]. Biglieri, E. Viterbo and E., "A universal decoding algorithm for lattice codes", Colloque GRETSI, vol. 14, pp. 611–614, (1993).

[6]. D. Wubben, R. Bohnke, V. Kuhn, and K.-D. Kammeyer, "MMSE extension of V-BLAST based on sorted QR decomposition," in Proc. IEEE 58th Vehicular Technology Conference (VTC), vol. 1, no. 1, pp. 508–512, (2003).

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

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

[9]. P. Tsai, W. Chen, X. Lin and M. Huang, "A 4×4 64-QAM reduced-complexity K-best MIMO detector up to 1.5Gbps," Proceedings of 2010 IEEE International Symposium on Circuits and Systems, pp. 3953-3956, (2010).

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

[11]. K.-W. Wong, C.-Y. Tsui, R. S.-K. Cheng, and W.-H. Mow, "A VLSI Architecture of a K-Best Lattice Decoding Algorithm for MIMO Channels," in Proc. IEEE International Symposium on Circuits and Systems (ISCAS), vol. 3, no. 1, pp. 273–276, (2002).

[12]. Vikalo, B. Hassibi and H., "On the expected complexity of sphere decoding," in Proc. Thirty-Fifth Asilomar Conference on Signals, Systems and Computers, vol. 2, pp. 1051–1055, (2001).

[13]. C. P. Schnorr and M. Euchner, "Lattice Basis Reduction: Improved Practical Algorithms and Solving Subset Sum Problems," Math.Program, vol. 66, pp. 181–191, (1994).

[14]. Nilsson, Z. Guo and P., "Reduced complexity Schnorr-Euchner decoding algorithms for MIMO systems," IEEE Communications Letters, vol. 8, pp. 286–288, (2004).

[15]. Ibrahim A, Bello, Basel Halak, Mohammed El-Hajjar, Mark Zwolinski, "VLSI Implementation of a Fully-Pipelined K-Best MIMODetector with Successive Interference Cancellation," in Circuits Systems and Signal Processing, (2019).



How to Cite

Nguyễn Minh Thường, Trần Xuân Nam, Nguyễn Đức Thắng, Vũ Tiến Anh, and Trịnh Quang Kiên. “Design and Evaluation of Sphere Decoder Accelerator on Reconfiguration Hardware”. Journal of Military Science and Technology, no. 80, June 2022, pp. 80-91, doi:10.54939/1859-1043.j.mst.80.2022.80-91.



Research Articles