現在的無線通訊發展中，多輸入多輸出系統(MIMO)是常用來描述天線無線通訊系統的抽象模型，因為MIMO系統可以在不增加頻寬或發送功率的情況下大幅增加系統的吞吐量(throughput)以及傳送距離，因此這個技術被廣泛的研究和應用。然而一般的通訊系統中經常用到的解調方式最大概似偵測法(MLD)卻難以在MIMO系統中使用，主要的原因是雖然可以達到MLD的錯誤率，但是複雜度卻非常的高，因此有不少適用於MIMO系統上的新的偵測法被提出來，例如:ZF解調法和MMSE解調法，這兩個方法雖然可以有效降地複雜度，但是錯誤率會比MLD稍微略高一些。而球狀解碼(sphere decoding)也是在MIMO系統上的一個解調方式，但不同於上述兩個解調法，球狀解碼可以有效降低複雜度、錯誤率也可以維持在與MLD差不多，在這篇論文中我們研究球狀解碼，並且研究如何找尋更好的搜尋半徑，同時也會討論每一個階層的運算，使得搜尋範圍縮小進而降低運算複雜度。

In the recent development of wireless communications, the multiple input and multiple output (MIMO) system has gradually become an indispensable key technology. It has been extensively studied because MIMO systems have the advantages of increasing system throughput and getting diversity gain. Although the maximum-likelihood (ML) detection can reach the optimal performance of bit-error rate (BER), its complexity is also very high. Several detection methods have been proposed for the MIMO system, such as the zero-forcing (ZF) detection and minimum mean-squares error (MMSE) detection. Although these two methods can effectively reduce the complexity, the BER is still higher than that of the ML detection. Sphere decoding (SD) is also a detection method for the MIMO system, and it can efficiently attain the ML detection with reduced complexity. In this thesis, we will study on the sphere decoding and focus on reducing its complexity. We study how to find a better search center and search radius in the SD algorithm. We can find the initial radius and dynamically adjusting its value to reduce the computational complexity.
There are two main topics in this thesis: dynamic search of sphere decoding and pre-estimated radius for sphere decoding.

[1] B. Hassibi and H. Vikalo. On the expected complexity of sphere decoding. In Conference Record of Thirty-Fifth Asilomar Conference on Signals, Systems and Computers (Cat.No.01CH37256), volume 2, pages 1051–1055 vol.2, 2001.

[2] B. Hassibi and H. Vikalo. On the sphere-decoding algorithm i. expected complexity. IEEE Trans. on Signal Processing, 53(8):2806–2818, 2005.

[3] Mohamed-Achraf Khsiba and Ghaya Rekaya-Ben Othman. Sphere decoder with dichotomic search. In 2017 IEEE 28th Annual International Symposium on Personal, Indoor, and Mobile Radio Communications (PIMRC), pages 1–7, 2017.

[4] Haitao Li. Sphere decoding for mimo ofdm with the aid of harq. In 2007 International Symposium on Microwave, Antenna, Propagation and EMC Technologies for Wireless Communications, pages 260–264, 2007.

[5] Fa-Long Luo. Machine Learning–Based Nonlinear MIMO Detector, pages 181–195. 2020.

[6] Mohammad Harun Rashid and Miguel A. Mosteiro. A greedy-genetic local-search heuristic for the traveling salesman problem. In 2017 IEEE International Symposium on Parallel and Distributed Processing with Applications and 2017 IEEE International Conference on Ubiquitous Computing and Communications (ISPA/IUCC), pages 868– 872, 2017.

[7] Pei-Hua Wu and Ming-Xian Chang. Detection of mimo systems based on dynamic search for high-order modulations. In 2019 IEEE 90th Vehicular Technology Conference (VTC2019-Fall), pages 1–5, 2019.

[8] Wei Xu, B. Zheng, and J. Zhang. Efficient restarted radius bisection algorithm for sphere decoding with applications to multiple-in multiple-out systems. Communications, IET, 6:3140–3149, 12 2012.

[9] Wanlun Zhao and G.B. Giannakis. Sphere decoding algorithms with improved radius search. IEEE Trans. Commun., 53(7):1104–1109, 2005.