在現代無線通訊系統中，多輸入多輸出(Multi-input multi-output, MIMO)技術已被廣泛地使用來增加傳輸速率與改善傳輸品質，並且已經有數個多輸入多輸出偵測演算法發展出來，使得接收端收到的訊號能夠被有效的解回成傳送端送出的訊號。在這些演算法中，固定複雜度球形解碼(Fixed-complexity sphere decoding, FSD)演算法因為有著低複雜度與適合高平行化架構的特性，使其適合用於硬體設計上而被廣泛地使用。為了提供更加準確的軟式資訊給軟式輸入軟式輸出解碼器，擴充列表演算法已被應用在固定複雜度球形解碼演算法上，然而這些方法卻會對複雜度造成很大的負擔。
在本論文中，我們針對固定複雜度球形解碼演算法的軟式輸出提出增強技術，藉由使用K-best演算法與固定複雜度球形解碼演算法的結合而發展出新的擴充列表方式，使得計算軟式資訊所需的候選集合能夠更有效率的獲得，因此所提出的演算法能夠以較少數量的擴充節點達到較佳的效能。在16-QAM調變的4×4迭代渦輪多輸入多輸出系統架構下，若與現有之列表球形解碼(List sphere decoding, LSD)演算法相比，本論文所提出的演算法能夠減少大約59%的搜尋節點複雜度。

In modern wireless communication systems, multiple-input multi-output (MIMO) technique is widely used to enhance the throughput and improve the signal quality. To recover the transmitted signals from the received signals efficiently, several MIMO detection algorithms have been developed. Among these algorithms, a fixed-complexity sphere decoding (FSD) algorithm is a popular one due to its low computational complexity and highly parallel architecture. For providing more accurate soft information to soft-input soft-output decoder, some list extension algorithms were applied into the original FSD algorithm. However, a large effort is needed to improve on the reliability of soft information.
In this thesis, we presented a soft-output enhancement technique for the original FSD algorithm. By using a modified list extension scheme with the combination of K-best algorithm and FSD algorithm, an efficient candidate list is obtained for calculating the soft-output information. Hence, the proposed algorithm can achieve superior performance with lower number of extended node. Compared to the LSD algorithm, the proposed algorithm can reduce the complexity of overall searched nodes about 59% in a 4×4 iterative turbo-MIMO system with 16-QAM modulation.

[1] L. Azzam and E. Ayanoglu, “Reduced complexity sphere decoding for square QAM via a new lattice representation,” in Proc. IEEE Global Telecommun. Conf., Nov. 2007, pp. 4242–4246.
[2] U. Fincke and M. Pohst, “Improved methods for calculating vectors of short length in a lattice, including a complexity analysis,” Math. Comput., vol. 44, pp. 463-471, Apr. 1985.
[3] C. P. Schnorr and M. Euchner, “Lattice basis reduction: Improved practical algorithms and solving subset sum problems,” Math. Program., vol. 66, no. 2, pp. 181-199, Sep. 1994.
[4] K. Wong, C. Tsui, R. Cheng, and W. Mow, “A VLSI architecture of a K-Best lattice decoding algorithm for MIMO channels,” in Proc. IEEE ISCAS 2002, May 2002, pp. 273-276.
[5] 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.
[6] L. G. Barbero and J. S. Thompson, “A fixed-complexity MIMO detector based on the complex sphere decoder,” in Proc. IEEE Workshop Signal Processing Advances in Wireless Commun. (SPAWC’06), July 2006, vol. 1, pp. 1-5.
[7] B. Wu and G. Masera, “A novel VLSI architecture of fixed-complexity sphere decoder,” in Proc. Euromicro Conf. Digital Syst. Design: Architectures, Methods Tools (DSD’10), Sep. 2010, pp. 737-744.
[8] J. Jaldén, L. G. Barbero, B. Ottersten, and J. S. Thompson, “Full diversity detection in MIMO systems with a fixed-complexity sphere decoder,” in Proc. IEEE Int. Conf. Acoust., Speech and Signal Processing (ICASSP’07), Apr. 2007, vol. 3, pp. 49-52.
[9] J. B. Anderson and S. Mohan, “Sequential coding algorithms: a survey and cost analysis,” IEEE Trans. Commun., vol. COM-32, no. 2, pp. 169-176, Feb. 1984.
[10] K. Amiri, C. Dick, R. Rao, and J. Cavallaro, “Novel sort-free detector with modified real-valued decomposition (M-RVD) ordering in MIMO systems,” in Proc. Globecom, Dec. 2008, pp. 1-5.
[11] J. S. Lin, S. H. Fang, M. D. Shieh, and Y. H. Jen, “Design of high-throughput MIMO detectors using sort-free and early-pruned techniques,” in Proc. IEEE Region 10 Conf. (TENCON’10), Nov. 2010, pp. 1513-1516.
[12] B. Hochwald and S. Brink, “Achieving near-capacity on a multiple-antenna channel,” IEEE Trans. Commun., vol. 51, no. 3, pp. 389-399, Mar. 2003.
[13] D. W. Waters and J. R. Barry, “The Chase family of detection algorithms for multiple-input multiple-output channels,” IEEE Trans. Signal Processing, vol. 56, no. 2, pp. 739-747, Feb. 2008.
[14] R. Wang and G.B. Giannakis, “Approaching MIMO channel capacity with reduced-complexity soft sphere decoding,” in Proc. IEEE Wireless Commun. and Network Conf. (WCNC’04), Mar. 2004, vol.3, pp. 1620-1625.
[15] P. Marsch, E. Zimmermann, and G. Fettweis, “Smart candidate adding: A new low-complexity approach towards near-capacity MIMO detection,” in Proc. 13th Eur. Signal Process. Conf. (EUSIPCO’05), Sep. 2005, pp.1-4.
[16] C. Studer, A. Burg, and H. Bölcskei, “Soft-output sphere decoding: Algorithms and VLSI implementation,” IEEE J. Sel. Areas Commun., vol. 26, no. 2, pp. 290-300, Feb. 2008.
[17] C. Studer and H. Bölcskei, “Soft-input soft-output single tree-search sphere decoding,” IEEE Trans. Inform. Theory, vol. 56, no. 10, pp. 4827-4842, Oct. 2010.
[18] J. Jaldén and B. Ottersten, “Parallel implementation of a soft output sphere decoder,” in Proc. Asilomar Conf. Signals, Systems and Computers, Nov. 2005, pp. 581-585.
[19] E. M. Witte, F. Borlenghi, G. Ascheid, R. Leupers, and H. Meyr, “A scalable VLSI architecture for soft-input soft-output single tree-search sphere decoding,” IEEE Trans. Circuits Syst. II, vol. 57, no. 9, pp. 706-710, Sep. 2010.
[20] S. Baero, J. Hagenauer, and M. Witzke, “Iterative detection of MIMO transmission using a list-sequential (LISS) detector,” in Proc. IEEE Int. Conf. Commun. (ICC’03), May 2003, vol. 4, pp. 2653-2657.
[21] J. Hagenauer and C. Kuhn, “The list-sequential (LISS) algorithm and its application,” IEEE Trans. Commun., vol. 55, no. 5, pp. 918-928, May 2007.
[22] K. K. Y. Wong and P. J. McLane, “Bi-directional soft-output M-algorithm for iterative decoding,” in Proc. IEEE Int. Conf. Commun. (ICC’04), June 2004, vol. 2, pp. 792-797.
[23] Y. L. C. de Jong and T. J. Wilink, “Iterative tree search detection for MIMO wireless systems,” IEEE Trans. Commun., vol. 53, no. 6, pp. 930-935, June 2005.
[24] J. W. Choi, B. Shim, and A. C. Singer, “Efficient soft-input soft-output tree detection via an improved path metric,” IEEE Trans. Inform. Theory, vol. 58, pp. 1518-1533, Mar. 2012.
[25] Yang Yu, S. Handa, F. Sasamori, and O. Takyu, “Improved soft-output M-algorithm for differential encoded LDPC coded systems with multiple-symbol differential detection,” IEEE Int. Symp. Personal Indoor and Mobile Radio Commun. (PIMRC’12), Sep. 2012, pp. 1985-1991.
[26] L. G. Barbero and J. S. Thompson, “Extending a fixed-complexity sphere decoder to obtain likelihood information for turbo-MIMO systems,” IEEE Trans. Veh. Technol., vol. 57, no. 5, pp. 2804-2814, Sep. 2008.
[27] L. G. Barbero, T. Ratnarajah, and C. Cowan, “A low-complexity soft-MIMO detector based on the fixed-complexity sphere decoder,” in Proc. IEEE Inf. Conf. Acoust., Speech and Signal Processing (ICASSP’08), Apr. 2008, pp. 2669-2672.
[28] C. P. Huang, “Efficient turbo-MIMO systems based on fixed-complexity sphere detector,” M. S. Thesis, Department of Electrical Engineering, National Cheng Kung Uni., Tainan, Taiwan, July 2014.
[29] X. Chen, G. He, and J. Ma, “VLSI implementation of a high-throughput iterative fixed-complexity sphere decoder,” IEEE Trans. Circuits Syst. II, vol. 60, no. 5, pp. 272-276, May 2013.
[30] L. Liu, “High-throughput hardware-efficient soft-input soft-output MIMO detector for iterative receivers,” in Proc. IEEE Int. Symp. Circuits and Syst. (ISCAS’13), May 2013, pp. 2151-2154.
[31] J. S. Lin, S. H. Fang, C. F. Lin, and M. D. Shieh, “High-performance turbo-MIMO system design with iterative soft-detection and decoding,” in Proc. Signal and Inform. Processing Association Annual Summit and Conf. (APSIPA ASC’12), Dec. 2012, pp. 1-4.
[32] C. F. Lin, “Efficient fixed-complexity sphere detector for turbo-MIMO Systems,” M. S. Thesis, Department of Electrical Engineering, National Cheng Kung Uni., Tainan, Taiwan, June 2012.
[33] E. Zimmermann, S. Bittner, and G. Fettweis, “Complexity reduction in iterative MIMO receivers based on EXIT chart analysis,” 4th Int. Sym. Turbo Codes&Related Topics; 6th Int. ITG-Conf. Source and Channel Coding (TURBOCODING’06), Apr. 2006, pp. 1-6.
[34] L. Liu, J. Lofgren and P. Nilsson, "Area-efficient configurable high-throughput signal detector supporting multiple MIMO modes," IEEE Trans. Circuits Syst. I, Reg. Papers, vol. 59, no. 9, pp. 2085-2096, Sep. 2012.