多重輸入多重輸出(MIMO、massive MIMO)技術在未來的第五代行動通訊系統(5G)是極為熱門的研究領域，MIMO技術可以增加頻譜的使用效率並大幅的提高通訊的吞吐量，但也因此增加了接收端偵測器的複雜度，尤其是當傳輸的系統中使用了錯誤控制編碼或是天線數量的遽增，其接收端的軟式輸入軟式輸出偵測器之設計則顯的更為重要。針對此問題，本論文提出三種高效率的MIMO偵測方法，我們首先提出不同階層的差分度量(differential metrics)之遞歸關係式，利用差分度量結合梯度搜尋方式再加上指示函數(indicative functions)判定來減少偵測器的複雜度。我們所提出的梯度搜尋演算法(GSA)可以在效能與複雜度之間取得良好的平衡，並一併提出擁有固定複雜度之梯度搜尋演算法能適用於流水線硬體實現。
本論文接著提出一個新穎的maximum-likelihood (ML)檢測器，其藉由指示函數來進一步提升ML的樹狀搜尋能力。本論文所提出之演算法不需要使用QR分解與逆矩陣之運算，且在搜尋的過程中只需使用到加法運算，乘法運算皆只需於前置運算中處理。最後，我們提出一高效率的軟式檢測器，可以計算出近似的對數相似比值(Log-likelihood Ratio)。實驗模擬結果顯示我們所提出的方法皆具有優越的性能。除此之外，我們也與其他學者們所提之先進方法做比較，在主觀與客觀的實驗中，本論文所提之方法皆有良好的效能。

The multiple-input multiple-output (MIMO) system makes efficient use of spectrum and increases the transmission throughput in wireless communications. Designing low-complexity detection algorithms with high performance for the MIMO system has been an important issue. In this thesis, we propose three efficient detection algorithms for MIMO systems based on differential metrics. We first define differential metrics and derive the associated recursive calculation of different orders. Based on differential metrics, we give the principle of gradient search. We then propose a gradient search algorithm (GSA) that can provide a good trade-off between performance and complexity. The GSA applies the indicative functions such that we can determine in advance some ML bits of the initial sequence and reduce the searching range. The GSA also uses a stop condition with which we can stop the search if the proper condition is satisfied. We also propose a fixed-complexity GSA, which has fixed number of operations during the searching process and is appropriate for pipelined hardware implementation.
For the exact maximum-likelihood (ML) detection, we propose a novel ML detection algorithm based on differential metrics. The indicative functions are further applied to implement an efficient tree search for ML detection. The proposed algorithms do not need QR decomposition and matrix inversion. The multiplicative operations are only necessary before the searching process, during which only the additive operations are needed. Finally, we propose a novel soft detection algorithm that can generate the values of log-likelihood ratios (LLR) and provide a trade-off between performance and complexity. The numerical results validate the efficiency of the proposed algorithms.

Contents
1 Introduction 1
2 Preliminaries 6
2.1 System Model 6
2.2 SD and FSD Algorithm 7
2.2.1 K-Best and QRD-M Algorithm 9
2.3 Soft Detection Algorithm 10
2.3.1 Exact MAP Detection 10
2.3.2 Max-Log Approximation Detection 10
2.3.3 List-Sphere Decoding 11
3 The Proposed Gradient Search Algorithm 12
3.1 Differential Metrics 12
3.2 The Gradient-Search Algorithm 15
3.3 For Large-Scaled MIMO Systems 18
3.4 Fixed-Complexity Gradient Algorithm 19
3.5 Numerical Results and Complexity Assessment 21
3.6 Summary 28
4 The Proposed Efficient ML Detection 31
4.1 Indicative Functions 31
4.2 The ML Detection 35
4.3 Discussions 42
4.3.1 Convergence Analysis 42
4.3.2 Complexity Comparison 44
4.3.3 Memory Use 44
4.3.4 Parallel Processing 45
4.3.5 Soft Output 45
4.4 High-Order Modulation (QAM) 47
4.5 Numerical Results 50
4.6 Summary 56
5 The Proposed Efficient Soft MIMO Detection 62
5.1 GSA for Max-Log Approximation 62
5.2 List Gradient Algorithm 63
5.3 Soft Output GSA 63
5.4 Numerical Results 65
6 Conclusions and Future Work 70

[1] J. Benesty, Y. Huang and J. Chen , A fast recursive algorithm for optimum sequential signal detection in a BLAST system, IEEE Trans. Signal Process., vol. 51, no. 7, pp. 1722-1730, July 2003.
[2] D. Gesbert, M. Shafi, D.-S. Shiu, and P. J. Smith, From theory to practice: an overview of MIMO space-time coded wireless systems, IEEE J. Sel. Areas Commun., vol. 21, pp. 281-302, Apr. 2003.
[3] Y. Fadlallah, A. Aissa-El-Bey, K. Amis, D. Pastor and R. Pyndiah, New iterative detector of MIMO transmission using sparse decomposition, IEEE Trans. Veh. Technol., vol. 64, no. 8, pp. 3458-3464, Aug. 2015.
[4] C. Li, Y. Huang, M. Di Renzo, J. Wang, and Y. Cheng, Low-Complexity ML detection for spatial modulation MIMO with APSK constellation, IEEE Trans. Veh. Technol., vol. 64, no. 9, pp. 4315-4321, May 2015.
[5] A. G. D. Uchoa, C. T. Healy and R. C. de Lamare, Iterative Detection and Decoding Algorithms For MIMO Systems in Block-Fading Channels Using LDPC Codes, IEEE Trans. Veh. Technol., vol. 65, no. 4, pp. 2735-2741, May 2015.
[6] M. Di Renzo and H. Haas, Bit error probability of SM-MIMO over generalized fading channels, IEEE Trans. Veh. Technol., vol. 61, no. 3, pp. 1124-1144, Mar. 2012.
[7] M. O. Damen, H. El Gamal and G. Caire, On maximum-likelihood detection and the search for the closest lattice point, IEEE Trans. Inf. Theory, vol. 49, no. 10, pp. 2389-2402, Oct. 2003.
[8] Z. Guo and P. Nilsson, Reduced complexity Schnorr-Euchner decoding algorithms for MIMO systems, IEEE Commun. Lett., vol. 8, no. 5, pp. 286-288, May. 2004.
[9] J. C. Braz and R. S. Neto, Low-complexity sphere decoding detector for generalized spatial modulation systems, IEEE Commun. Lett., vol. 18, no. 6, pp. 949-952, Apr. 2014.
[10] S. Chen and Y. Yang, Low-complexity MMSE-SIC equalizer employing LDL^H factorization for OFDM systems Over time-varying channels, IEEE Trans. Veh. Technol., vol. 59, no. 8, pp. 4128-4131, Aug. 2010.
[11] R. Ghaffar, R. Knopp, and P. H. Ho, Low complexity BICM MIMO OFDM demodulator, IEEE Trans. Wireless Commun., vol. 14, no. 1, pp. 558-569, Sep. 2014.
[12] L. G. Barbero and J. S. Thompson, Fixing the complexity of the sphere decoder for MIMO detection, IEEE Trans. Wireless Commun., vol.~7, no.~7, pp. 2131-2142, June 2008.
[13] C. Zheng, X. Chu, J. McAllister, and R. Woods , Real-valued fixed-complexity sphere decoder for high dimensional QAM-MIMO systems, IEEE Trans. Signal Process., vol. 59, no. 9, pp. 4493-4499, Sept. 2011.
[14] Z. Guo and P. Nilsson, Algorithm and implementation of the K-best sphere decoding for MIMO detection, IEEE J. Sel. Areas Commun., vol. 24, no. 3, pp. 491-503, Mar. 2006.
[15] C. F. Liao, J. Y. Wang and Y. H. Huang, A 3.1 Gb/s 8X8 sorting reduced K-Best detector with lattice reduction and QR decomposition, IEEE Trans. VLSI. Syst., vol. 22, no. 12, pp. 2675-2688, Feb. 2014.
[16] C. Tao and C. Tellambura, Improved K-Best sphere detection for uncoded and coded MIMO Systems, IEEE Wireless Commun. Lett., vol. 1, no. 5, pp. 472-475, Oct. 2012.
[17] J.-S. Kim, S.-H. Moon, and I. Lee, A new reduced complexity ML detection scheme for MIMO systems, IEEE Trans. Commun., vol.~58, no. 4, pp. 1302-1310, Apr. 2010.
[18] C. Studer and H. Bolcskei Soft-input soft-output single tree-search sphere decoding, IEEE Trans. Inf. Theory, vol. 56, no. 10, pp. 4827-4842, Oct. 2010.
[19] M. M. Mansour, S. P. Alex, and L. M.A. Jalloul, Reduced complexity soft-output MIMO sphere detectors part I: algorithmic optimalizations, IEEE Trans. Signal Process., vol. 62, no. 21, pp. 5505-5520, Nov. 2014.
[20] M. M. Mansour, S. P. Alex, and L. M.A. Jalloul, Reduced complexity soft-output MIMO sphere detectors part II: architectural optimizations, IEEE Trans. Signal Process., vol. 62, no. 21, pp. 5521-5535, Nov. 2014.
[21] S. Yang and L. Hanzo, Fifty years of MIMO detection: the road to large-scale MIMOs, IEEE Commun. Surveys Tuts., vol. 17, no. 4, pp. 1941-1988, 4th QUARTER 2015.
[22] T. H. Kim, Low-complexity sorted QR decomposition for MIMO systems based on pairwise column symmetrization, IEEE Trans. Wireless Commun., vol. 13, no. 3, pp. 1388-1396, Mar. 2014.
[23] M. Cirkic and E. G. Larsson, SUMIS: Near-Optimal Soft-In Soft-Out MIMO Detection With Low and Fixed Complexity, IEEE Trans. Signal Process., vol. 62, no. 12, pp. 3084-3097, June 2014.
[24] M.-X. Chang and W.-Y. Chang, Efficient detection for MIMO systems based on gradient search, IEEE Trans. Veh. Technol., vol. 65, no. 12, pp. 10057-10063, Dec. 2016.
[25] M.-Wu, B. Yin, G. Wang, C. Dick, J. R. Cavallaro, and C. Studer, Large-scale MIMO detection for 3GPP LTE: algorithms and FPGA implementations, IEEE J. Sel. Topics Signal Process., vol. 8, pp. 916-929, Oct. 2014.
[26] R. Hunger, Floating Point Operations in Matrix-Vector Calculus, Munich Univ. of Technology, Inst. for Circuit Theory and Signal Processing, 2005.
[27] P. Odling and H. B. Eriksson, Making MLSD decisions by thresholding the matched filter output, IEEE Trans. Commun., vol. 48, no. 2, pp. 324-332, Feb. 2014.
[28] P. Svac, F. Meyer, E. Riegler, and F. Hlawatsch, Low-complexity detection for large MIMO systems using partial ML detection and genetic programming, in Proc. IEEE SPAWC 2012, pp. 585-589, June 2012.
[29] H. A. Taha, Integer Programming, Theory, Applications, and Computations, New York: Academic, 1975.
[30] S. Yang, T. Lv, R. G. Maunder, and L. Hanzo, Unified bit-based probabilistic data association aided MIMO detection for high-order QAM constellations, IEEE Trans. Vehl. Tech., vol. 60, no. 3, pp. 981-991, Mar. 2011.
[31] S. Yang, T. Lv, and L. Hanzo, Semidefinite programming relaxation based virtually antipodal detection for MIMO systems using Gray-coded high-order QAM, IEEE Trans. Vehl. Tech., vol. 62, no. 4, pp. 981-991, May. 2013.
[32] C. Studer, A. Burg, and H. Bolcskei, Soft-output sphere decoding: algorithms and VLSI implementation, IEEE J. Sel. Areas Commun., vol. 26, no. 2, pp. 290-300, Feb. 2008.
[33] M.-X. Chang and W.-Y. Chang, Efficient maximum-likelihood detection for the MIMO system based on differential metrics, in Proc. IEEE WCNC 2015, pp. 603-608, Mar. 2015.
[34] E. G. Larsson and J. Jalden, Fixed-complexity soft MIMO detection via partial marginalization, IEEE Trans. Signal Process., vol. 56, no. 8, pp. 3397-3407, Aug. 2008.
[35] J. Pan, W.-K. Ma, and J. Jalden, MIMO Detection by Lagrangian Dual Maximum-Likelihood Relaxation: Reinterpreting Regularized Lattice Decoding, IEEE Trans. Signal Process., vol. 62, no. 2, pp. 511-524, Jan. 2014.
[36] J. Chen, J. Hu, and G. E. Sobelman, Stochastic MIMO Detector Based on the Markov Chain Monte Carlo Algorithm, IEEE Trans. Signal Process., vol. 62, no. 6, pp. 1454-1463, Jan. 2014.
[37] M.-X. Chang and W.-Y. Chang, Maximum-Likelihood Detection for MIMO Systems Based on Differential Metrics, IEEE Trans. Signal Process., vol. 65, no. 14, pp. 3718-3732, July 2017.
[38] W.-Y. Chang and M.-X. Chang, An Efficient Soft MIMO Detection Algorithms Based on Differential Metrics, in Proc. IEEE VTC-Spring 2017, June 2017.