由於多天線(Multiple Input Multiple Output ; MIMO)通訊技術能夠在不增加使用頻寬的狀況下，大幅提升傳輸品質與效率，使其在現代無線通訊系統中的重要性日益提升。然而應用MIMO技術將使得通訊系統的複雜度和執行運算時間因此而大幅增加。過去的研究顯示在MIMO通訊系統中應用結合偵測與解碼架構可有效降低系統複雜度並進一步提升傳輸品質。然而由於其設計上的限制，傳送端通道編碼器的編碼率和調變架構必須使用固定的組合，使得此架構只能滿足單一的通訊環境，而造成缺乏實用性的嚴重問題。本論文提出了可調式結合偵測與解碼架構，使其能夠應用於使用各種編碼器結構及調變架構的無線通訊環境，而從根本上解決了上述的問題。除此之外，為了應付不同的通訊環境，本論文針對此架構中所使用的樹狀搜尋演算法做更深入的探討。樹狀搜尋演算法的發展歷史久遠，擁有大量研究文獻可供參考，而不同的樹狀搜尋演算法應用於通訊系統中所展現出來的特性迥異，因此我們可以針對不同的通訊條件或系統配置，選用最適合的演算法。本論文探討了三種不同而各具代表性的樹狀搜尋演算法，其中包含了基於廣度優先演算法、基於深度優先的演算法，以及Fano演算法。我們針對這三種演算法的時間複雜度、空間複雜度和運算時間可預測性這三項指標，進行深入探討及綜合分析比較。透過這樣的深入研討我們冀望明確點出適用於各種無線通訊環境及系統的演算法則及系統配置。

Multi Input Multi Output (MIMO) technology plays an essential role in modern wireless communication system owing to its capability to significantly improve communication quality and efficiency without drastically increasing the occupied bandwidth. However, such lucrative features also come along with the prominent drawback of significantly increased system complexity, especially on the receiver side. It has been shown that the Joint MIMO Detection and Channel Decoding (JDD) scheme can effectively reduce the complexity and improve the signal quality of the MIMO receiver. However, this previously proposed structure can only be applied with the system using specific code rate as well as modulation scheme such that it cannot be utilized in practical wireless system. In this thesis, we present the Configurable Joint Detection-Decoding (CJDD) scheme which can be used with several combinations of system settings and thus resolve the previous limitation. Moreover, since the JDD/CJDD approach is based on the tree search algorithms and there exists many different kinds of such methods with various characteristics, it is of great importance to understand the trade-offs between each tree search algorithm and their impacts on different aspects of system performances. In this thesis, we investigate three types of tree search algorithms: breadth-first based approach, depth-first based approach, and the Fano algorithm. We explore each of these algorithms on the basis of timing complexity, area complexity, and run-time variation. Our aim is to shed more lights on the design and application of tree search type approaches on the MIMO wireless communication systems for various needs of the system considerations.

[1] D. Gesbert, M. Shafi, Da-Shan Shiu, P. J. Smith, and A. Naguib, “From theory to practice: An overview of MIMO space-time coded wireless systems,” IEEE Jour. Selected Areas in Comm., vol. 21, no. 3, pp. 281-302, Apr. 2003.
[2] G. Knagge, M. Bickerstaff, B. Ninness, S. Weller, and G. Woodward, “A VLSI 8x8 MIMO near-ML decoder engine,” IEEE Workshop Sign. Process. Syst. Design and Implem., Oct 2006, pp. 387-392.
[3] X. Huang, C. Liang, and J. Ma, “System architecture and implementation of MIMO sphere decoders on FPGA,” IEEE Trans. VLS Systems, vol. 16, no. 2, pp. 188-197, Feb 2008.
[4] A. Burg, M. Borgmann, M. Wenk, M. Zellweger, W. Fichtner, and H. Bolcskei, “VLSI implementation of MIMO detection using the sphere decoding,” IEEE Jour. Solid-State Circuits, vol. 40, no. 7, pp. 1566-1577, Jul 2005.
[5] T. Cui, T. Ho, and C. Tellambura, “Statistical pruning for near maximum likelihood detection of MIMO systems,” in Proc. IEEE Intl. Conf. Comm., Jun 2007, pp. 5462-5467.
[6] Z Guo and P. Nilsson, “Algorithm and implementation of the K-Best sphere decoding for MIMO detection,” IEEE Jour. Selected Areas in Comm. , vol. 24, no.3, pp. 491-503, Mar 2006.
[7] S. Chen and T. Zhang, "Relaxed K-Best MIMO signal detector design and VLSI Implementation," IEEE Trans. VLSI, vol. 15, no. 3, pp. 328-337, Mar 2007.
[8] C.-H. Liao, T.-P. Wang, and T.-D. Chiueh, "A 74.8 mW Soft-Output Detector IC for 8 × 8 Spatial Multiplexing MIMO Communications," IEEE J. Solid-State Circuits., vol. 45, no. 2, pp. 411-421, Feb 2010.
[9] L. Liu, F. Ye, X. Ma, T. Zhang, and J. Ren, “A 1.1-Gb/s 115-pJ/bit Configurable MIMO Detector Using 0.13-µm CMOS Technology,” IEEE Trans. Circuits Syst. II, vol.57, no. 9, pp. 701–705, Sep. 2010.
[10] C. P. Sukumar, C.-A. Shen, and A. M. Eltawil, " Joint Detection and Decoding for MIMO Systems Using Convolutional Codes: Algorithm and VLSI Architecture," IEEE Trans. Circuits Syst.-I, vol.59, no.9, pp. 1919-1931, Sep 2012.
[11] Blass, Andreas; Gurevich, Yuri (2003). "Algorithms: A Quest for Absolute Definitions". Bulletin of European Association for Theoretical Computer Science 81.
[12] de Jong, Y.L.C and Willink, T.J. “Iterative tree search detection for MIMO wireless systems,” in, IEEE Trans. Communications., vol.53, Issue: 6, June 2005
[13] J. B. Anderson and S. Mohan, "Sequential coding algorithms: A survey and cost analysis", IEEE Trans. Communications., vol.32, no.2, pp.169 -176, 1984
[14] John T. Robinson, “The K-D-B-tree: a search structure for large multidimensional dynamic indexes,” SIGMOD '81 Proceedings of the ACM SIGMOD international conference on Management of data, Pages 10-18, 1981
[15] R. Schwartz and S. Austin, "Efficient, High Performance Algorithms for N-Best Search", Proc. DARPA Speech and Natural Language Workshop, 1990
[16] David Carmel and Shaul Markovitch. Learning and Using Opponent Models in Adversary Search. 1996.
[17] Guillaume M. J. B. Chaslot, Mark H. M. Winands, and H. Jaap van den Herik. “Parallel Monte-Carlo Tree Search,” Computers and Games: 6th International Conference, CG 2008.
[18] D. E. Knuth and R. W. Moore. “An Analysis of Alpha-Beta Pruning,” Artificial Intelligence, 6:293–326, 1975.
[19] C. E. Shannon. Programming a Computer for Playing Chess. Philosophical Magazine, 41(314):256–275, 1950.
[20] Nathan Sturtevant. Current Challenges in Multi-Player Game Search. Computers and Games: 4th International Conference, CG 2004.
[21] B. De Backer, V. Furnon, P. Prosser, P. Kilby, and P. Shaw. Local search in constraint programming: Application to the vehicle routing problem. In A. Davenport and C. Beck, editors, Proceedings of the CP-97 workshop on Industrial Constraintbased Scheduling, 1997.
[22] N. Christofides, A. Mingozzi and P. Toth, “The vehicle routing problem”, in: N. Christofides, A. Mingozzi, P. Toth and C. Sandi, eds.,Combinatorial optimization (John Wiley and Sons, London, 1979).
[23] R. Baldacci, N. Christofides, A. Mingozzi, “An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts,” in Math Program, 115 (2008), pp. 351–385
[24] Shu Lin, Daniel J. Costello, Jr. 2004. Error Control Coding. 2nd ed., 620-626. Upper Saddle River: Pearson Education, Inc.