在現代無線通訊系統中，多輸入多輸出(Multiple-input multiple-output, MIMO)技術被廣泛地採用來提升傳輸量。為了有效解回傳送端的資訊，在接收端採用渦輪多輸入多輸出系統(Turbo-MIMO system)的疊代架構被進一步地提出。渦輪多輸入多輸出系統藉由疊代計算所謂的軟式資訊(Soft information)來增進接收端偵測器和解碼器之間的解碼效率，其中，軟式資訊由對數相似比值(Log-likelihood ratio, LLR)表示。在系統內偵測器的部分，固定複雜度球型偵測器(Fixed complexity sphere detector, FSD)的演算法因其具有低複雜度，以及在硬體實現上具有高平行化架構的特性而經常被使用。然而，由於固定複雜度球型偵測器輸出的軟式資訊較不可靠，因而造成系統的效能損失。雖然軟式資訊的準確度可以藉由多次的系統疊代來改善，但這會降低系統的傳輸量。若要增加渦輪多輸入多輸出系統的效率，設計一個具有較可靠軟式資訊輸出的低複雜度偵測器是不可或缺的一環。
在本論文中，我們呈現了一個更有效率來更新軟式資訊的渦輪多輸入多輸出系統。本文首先提出新的額外樹狀搜尋方式來改善偵測器一開始輸出的軟式資訊，從而減少整體疊代的次數，接著提出候選節點選擇法來縮減計算軟式資訊時所需的記憶體需求量，最後提供調整渦輪內部疊代次數組合的策略來進一步增進系統的整體效率。在16-QAM調變的4×4多輸入多輸出架構下，和使用球型列表列舉法(List sphere decoding, LSD)的渦輪多輸入多輸出系統相比，本論文所提出的方式在對數相似比值計算的記憶體需求量以及節點搜尋的數量上分別可以減少94.68%和61.57%。

The multiple-input multiple-output (MIMO) technique has been widely adopted in modern wireless communication systems to enhance the throughput rate. Among various decoding techniques, the turbo-MIMO systems are introduced to further improve the decoding efficiency between the detector and decoder. For MIMO detector design, the fixed-complexity sphere decoding (FSD) algorithm features low computational complexity with acceptable performance and is suitable for highly parallel architecture development. However, unreliable soft information provided from the output of FSD detector usually leads to performance degradation. Although the turbo-MIMO system can update this soft information with multiple iterations, the overall throughput rate will be reduced accordingly. Design of low-complexity detectors with reliable soft information output is thus essential in efficient turbo-MIMO systems.
In this thesis, we presented an efficient turbo-MIMO system to update the soft information between the detector and decoder. An extended tree search technique is developed to improve the initial soft information of the soft-MIMO detector. Furthermore, a candidate node selection scheme is proposed to reduce the memory requirement of log-likelihood ratio (LLR) computation. A strategy of iteration profile is also provided to enhance the throughput. Compared to the LSD algorithm, the proposed scheme can reduce the complexity of LLR computation and the number of overall searched nodes by about 94.68% and 61.57% respectively, in 4×4 turbo-MIMO systems with 16-QAM modulation.

[1] 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.
[2] 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.
[3] 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.
[4] 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.
[5] 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.
[6] 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.
[7] 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.
[8] 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.
[9] 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.
[10] 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.
[11] 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.
[12] 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.
[13] 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.
[14] 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.
[15] E. Agrell, T. Eriksson, A. Vardy, and K. Zeger, “Closest point search in lattices,” IEEE Trans. Inform. Theory, vol. 48, no. 8, pp. 2201-2214, Aug. 2002.
[16] 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.
[17] 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.
[18] 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.
[19] D. W. Waters and J. R. Barry, “The Chase family of detection algorithms for MIMO channels,” IEEE Trans. Signal Processing, vol. 56, no. 2, pp. 739-747, Feb. 2008.
[20] 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.
[21] 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.
[22] 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.
[23] 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.
[24] 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.
[25] 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.
[26] 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.
[27] 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.
[28] K. Kilhwan, J. Yunho, L. Seongjoo, and K. Jaeseok, “Near-ML soft-MIMO detector with reduced complexity,” in Proc. IEEE Region 10 Conf. (TENCON’12), Nov. 2012 , pp. 1-5.
[29] Y. Jianpeng, M. Jun, and M. Zhigang, “Parallel SFSD MIMO detection with SOFT-HARD combination enumeration,” IEEE Workshop on Signal Processing Systems (SiPS’11), Oct. 2011, pp. 228-233.
[30] C. Xi, L. Jiangpeng, M. Jun, W. Junfeng, and H. Guanghui, “A low complexity soft-input soft-output fixed-complexity sphere decoding algorithm,” 8th Int. Conf. Wireless Commun., Networking and Mobile Computing (WiCOM’12), Sep. 2012, pp. 1-4.
[31] T. Tsubaki and H. Ochiai, “A new candidate adding algorithm for coded MIMO systems with fixed-complexity detection,” IEEE Int. Conf. Commun. (ICC’13), June 2013, pp. 4525-4529.
[32] X. Wu and J. S. Thompson, “A fixed-complexity soft-MIMO detector via parallel candidate adding scheme and its FPGA implementation,” IEEE Commun. Letters, vol. 15, pp. 241-243, Feb. 2011.
[33] 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.
[34] 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.
[35] 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.
[36] 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.
[37] 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.
[38] M. El-Khamy, L. Jungwon, and K. Inyupg, “Soft turbo HARQ combining,” IEEE Int. Conf. Commun. (ICC’13), June 2013, pp. 5542-5547.
[39] S. ten Brink, “Designing iterative decoding schemes with the extrinsic information transfer chart,” AEÜ, Int. J. Electron. Commun., vol. 54, no. 6, pp. 389-398, Nov. 2000.
[40] J. Hagenauer, “The EXIT chart - Introduction to extrinsic information transfer in iterative processing,” in Proc. Eur. Signal Process. Conf., Vienna, Austria, Sep. 2004, pp. 1541–154.
[41] D. Scott, “On optimal and data-based histograms,” Biometrika, vol. 66, no. 3, pp. 605-610, 1979.
[42] S. ten Brink, G. Kramer, and A. Ashikhmin, “Design of low-density parity-check codes for modulation and detection,” IEEE Trans. Commun., vol. 52, pp.670-678, Apr. 2004.
[43] R. G. Maunder, “Rob Maunder's wireless communications research pages Matlab EXIT charts,” Internet: users.ecs.soton.ac.uk/rm/resources/matlabexit, May 20, 2014 [Aug. 19, 2014].