在空間多工的多輸入多輸出之樹狀搜尋偵測演算法中，固定複雜度球體解碼利用固定路徑數搭配對特定偵測順序排序的搜尋方式，藉此使錯誤率效能接近最佳，同時也可以在硬體實作上進行平行處理、管線處理並且有固定的吞吐量，使其架構非常適合硬體實作，但也因此提升了搜尋以及前置處理兩階段的複雜度。在搜尋階段由於固定複雜度球體解碼的搜尋路徑數保持固定不根據通道狀況改變，使得固定複雜度球體解碼在通道狀況較好的時候還是耗費了不必要的複雜度進行搜尋；在偵測順序的排序上，由於需要計算多次不同的虛擬反矩陣，也因此提高了前置處理階段的複雜度。在本文中，我們在保留固定複雜度球體解碼實作優點的前提下，提出根據通道狀況調整固定複雜度球體解碼搜尋路徑數的演算法以降低搜尋階段的平均複雜度；同時在前置處理階段改用排序QR分解進一步降低前置處理的複雜度。模擬結果顯示，我們提出的演算法的確可以大幅降低搜尋及前置處理階段的複雜度，代價則是會犧牲一點可接受的錯誤率。

Among the existing spatial-multiplexing multiple-input multiple-output (MIMO) detection algorithms, the fixed-complexity sphere decoder (FCSD) could achieve a quasi-ML performance by its unique search structure that visits a fixed number of predetermined paths with a special detection ordering scheme. Such a structure gives a constant complexity and allows for parallel and pipeline processing, which is very beneficial in hardware implementation. On the other hand, it yields a relatively high complexity in search and pre-processing due to the following reasons. Firstly, FCSD always searches through a fixed number of paths (which takes into account the worst-case channel conditions) regardless of the channel conditions, resulting in an un-necessarily high complexity at favorable channels. Secondly, FCSD needs to compute several pseudo-inverse matrices to determine the detection order in the preprocessing step. In the thesis, methods are proposed to reduce the complexity in these two aspects. Firstly, we propose a mechanism to adapting the number of paths to reduce the average complexity in the search step, while preserving most of the implementation advantages of FCSD. Secondly, the sorted QR decomposition (SQRD) is used in conjunction with the adaptive algorithm to reduce the complexity of pre-processing. The simulation results show that the proposed algorithm greatly reduces the complexity with little performance loss.

[1] P. W. Wolniansky, G. J. Foschini, G. D. Golden, and R. A. Valenzuela, “V-BLAST: An architecture for realizing very high data rates over the rich-scattering wireless channel,” in Proc. URSI ISSSE, pp. 295–300, Sep. 1998.
[2] R. B¨ohnke, D. W¨ubben, V. K¨uhn, and K. D. Kammeyer, “Reduced Complexity MMSE Detection for BLAST Architectures,” in Proc. IEEE Global Communications Conference, pp.2258-2261 Dec. 2003.
[3] K. J. Kim, J. Yue, R. A. Iltis, and J. D. Gibson, “A QRD-M/Kalman filter-based detection and channel estimation algorithm for MIMO-OFDM systems,” IEEE Trans. Wireless Commun., vol. 4, pp. 710-721, Mar. 2005.
[4] B. Hassibi and H. Vikalo, “On the sphere-decoding algorithm I: expected complexity,” IEEE Trans. Signal Processing, vol. 53, no. 8. pp. 2806-2818, Aug. 2005.
[5] M. O. Damen, H. El Gamal, and G. Caire, “On maximum-likelihood detection and the search for the closest lattice point, ” IEEE Trans. Inform.Theory, vol. 49, no. 10, pp. 2389-2402, Oct. 2003.
[6] A. Burg, M. Borgmann, M. Wenk, M. Zellweger, W. Fichtner, and H. B¨olcskei,“VLSI implementation of MIMO detection using the sphere decoding algorithm,” IEEE J. Solid-State Circuits, vol. 40, no. 7, pp. 1566–1577, July 2005.
[7] L. G. Barbero and J. S. Thompson, “Fixing the complexity of the sphere decoder for MIMO detection,” IEEE Trans. Wireless Commun., vol. 7, no. 6, pp. 2131-2142, June 2008.
[8] J. Jalden, L. G. Barbero, B. Ottersten, and J. S. Thompson, “The error probability of the fixed-complexity sphere decoder,” IEEE Trans. Signal Process., vol. 57, no. 7, pp. 2711-2720, Jul. 2009.
[9] Sheng Lei, Cong Xiong, Xin Zhang, Dacheng Yang, “Adaptive Control of Surviving Branches for Fixed-Complexity Sphere Decoder,” in Proc IEEE VTC , pp.1-5 , May 2010.
[10] C. Xiong, X. Zhang, K. Wu, and D. Yang, "A simplified fixedcomplexity sphere decoder for V-BLAST systems," IEEE Commun. Lett., vol.13, no.8, pp. 582-584, Aug. 2009.
[11] K. C. Lai and L. W. Lin, “Low-Complexity adaptive tree search algorithm for MIMO detection, ”IEEE Trans. On wireless Communications, vol. 8, pp.3716-3726, July 2009
[12] Proakis/Salehi, “Digital Communications”, 5th edition
[13] D. W¨ubben, J. Rinas, R. B¨ohnke, V. K¨uhn, and K. D. Kammeyer,“Efficient algorithm for Detecting Layered Space-Time Codes,” in Proc.ITG Conference on Source and Channel Coding, 2002, pp. 399–405.
[14] D. W¨ubben, R. R¨ohnke, V. K¨uhn, and K.-D. Kammeyer, “MMSE extension of V-BLAST based on sorted QR decomposition,” in Proceedings of the Vehicular Technology Conference VTC, pp. 508- 512, Oct. 2003.
[15] Mohaisen, M., KyungHi Chang, “On Improving the Efficiency of the Fixed-Complexity Sphere Decoder,”in Proc. IEEE VTC, pp.1-5, Sept 2009.
[16] B. Hassibi, “An Efficient Square-Root Algorithm for blast,” in Proc. IEEE Intl.Conf. Acoustic, Speech, Signal Processing, pp. 5–9, June 2000.