在現代無線通訊系統中，多輸入多輸出(Multi-input multi-output, MIMO)技術被廣泛地用以增加傳輸速率與改善傳輸品質，在現今文獻當中，已有數個多輸入多輸出偵測演算法發展出來。在這些演算法當中，固定複雜度球形解碼(Fixed-complexity sphere decoding, FSD)演算法具有低複雜度與適用高平行化架構的特性，使其有利於硬體設計而被廣泛地採用。為了提供更加準確的軟式資訊給軟式輸入軟式輸出解碼器，具擴展搜尋之高可靠軟式資訊固定複雜度球型解碼(Highly reliable soft information FSD with extended search)演算法已被提出應用在固定複雜度球形解碼演算法上，此方法具有高平行度、高規律性以及低複雜度。
在本論文中，我們針對具擴展搜尋之高可靠軟式資訊固定複雜度球型解碼演算法的硬體設計，結合使用心臟陣列架構(Systolic array architecture)設計與正交實數分解(Orthogonal real-valued decomposition)，使得硬體當中具高平行度與高規律性之處理元件能夠更有效率的被使用，所提出的架構具有較少量處理單元並且可維持高吞吐率。在64-QAM調變的4×4多輸入多輸出系統架構下，若與現有之演算法相比，在位元錯誤率(BER)上具有0.2~0.3 dB以上的效能增進，並且在架構設計上達到低複雜度以及高吞吐率。

In modern wireless communication systems, multiple-input multi-output (MIMO) technique is widely used to enhance the throughput and signal quality. To recover the transmitted signals from the received signals efficiently, several MIMO detection algorithms have been developed. Among them, the fixed-complexity sphere decoding (FSD) algorithm is a popular one due to its low computational complexity and highly parallel architecture. To provide more accurate soft information to soft-input soft-output decoder, a highly reliable soft information FSD with extended search is adopted to the original FSD algorithm with high regularity, parallelism and low complexity.
In this thesis, we presented hardware implementation of a soft-input soft-output FSD algorithm. By adopting the systolic array architecture and orthogonal real-valued decomposition, processing elements with high parallelism and regularity are available for reuse efficiently. Hence, the proposed architecture can achieve high throughput with a less amount of processing elements. Considering a 4x4 system with 64-QAM, the BER performance is improved about 0.2~0.3dB as compared with that of recent literatures.

[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] 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.
[34] P. Y. Chiu, “A Soft-output Enhancement Technique for Fixed-complexity Sphere Decoding Algorithm,” M. S. Thesis, Department of Electrical Engineering, National Cheng Kung Uni., Tainan, Taiwan, July 2015.
[35] J. L¨ofgren and P. Nilsson, “On MIMO K-best sphere detector architecture complexity reductions,” in Proc. International Conference on Signal Processing and Communication Systems (ICSPCS), Dec. 2008, pp. 1-9
[36] J. S. Lin, “High-performance Joint Iterative Detection and Decoding Design in Coded-MIMO Systems,” D. P. Dissertation, Department of Electrical Engineering, National Cheng Kung Uni., Tainan, Taiwan, July 2015.
[37] A. Maltsev, V. Pestretsov, R. Maslennikov, and A. Khoryaev, “Triangular systolic array with reduced latency for QR-decomposition of complex matrices,” in Proc. IEEE Int. Symp. Circuits Syst., 2006, pp. 385-388.
[38] Y. Sun and J. R. Cavallaro, “Trellis-search based soft-input soft-output MIMO detector: Algorithm and VLSI architecture,” IEEE Trans. Signal Process., vol. 60, no. 5, pp. 2617–2627, May 2012
[39] E. Witte et al., “A scalable VLSI architecture for soft-input soft-output single tree-search sphere decoding,” IEEE Trans. Circuits Syst.—II:Exp. Briefs, vol. 57, no. 9, pp. 706–710, Sep. 2010.
[40] Xi Chen, Guanghui He, Jun Ma, "VLSI Implementation of a High-Throughput Iterative Fixed-Complexity Sphere Decoder", Circuits and Systems II: Express Briefs IEEE Transactions on, vol. 60, pp. 272-276, 2013, ISSN 1549-7747.
[41] Liang Liu, Johan Löfgren, Peter Nilsson, Viktor Öwall, "VLSI Implementation of a Soft-Output Signal Detector for Multimode Adaptive Multiple-Input Multiple-Output Systems", Very Large Scale Integration (VLSI) Systems IEEE Transactions on, vol. 21, pp. 2262-2273, 2013, ISSN 1063-8210.