臺灣博碩士論文加值系統

多輸入多輸出系統中，高效率且低功率消耗之接收機的設計為關鍵議題之ㄧ。在本論文中，吾人首先以K-Best解碼器為基礎，提出一個適用於大型積體電路架構的高性能球型解碼器。利用複數平面星座圖的規律特性來簡化路徑長度計算及排序，達到省卻大量資料排序動作及路徑值的運算需求，進而實現一個高效率且具有固定吞吐量的解碼器；更進一步針對傳統K--Best解碼性能的缺失，藉由所提出的一種新型搜尋策略可提供接近於最大似然搜尋之解碼性能。接著，吾人針對廣義之多天線之欠定系統，提出具有低解碼複雜度的解碼器。該解碼器包含了兩個步驟：1.藉由所提出的高效率的平面候選點搜尋器將所有所需的候選點一一找出。2.針對這些候選點集合進行平面交集的動作並配合動態半徑調整機制來快速地找出該問題的解。接著，一個可與所提出解碼器結合之通道矩陣行向量的排序策略亦被提出。進而提供低運算需求及近似最大似然搜尋的解碼性能。吾人亦針對排序策略所對應的運算降低率提出一套系統化的數學分析分法。 最後，吾人針對上傳鏈結系統之多點協同傳輸系統中的碼簿搜尋問題，提出具有極低運算複雜度之演算法。首先，吾人根據矩陣運算理論，提出一個塊狀 QR 分解程序，能順利將原搜尋問題轉化成尋找最長路徑之命題。接著，運用所提出的修正K-Best解碼器便能以極低的運算量完成碼簿搜尋且仍保有極佳的系統性能。經由電腦模擬驗證本論文所提出的演算法及架構皆能提供優越的解碼性能及較低的運算需求，極適用於下世代之寬頻無線通訊系統。

In this dissertation, a low complexity near-ML K-Best sphere decoder is proposed as the first part. The development of the proposed K-Best sphere decoding algorithm (SDA) involves two stages. First, a new candidate sequence generator (CSG) is proposed. The CSG directly operates in the complex plane and efficiently generates sorted candidate sequences with precise path weights. Using the CSG and an associated parallel comparator, the proposed K-Best SDA can avoid the computational complexities in the large amount of path weight evaluations and sorting. Then a new search strategy based on a derived cumulative distribution function (cdf) and an associated efficient procedure is proposed. With the above features, the proposed SDA can provide near ML performance with the lower complexity than conventional K-Best SDAs. Afterwards, a novel decoder with low decoding complexity is proposed for underdetermined MIMO systems. The proposed decoder consists of two stages. First, an improved slab decoding algorithm is adopted to efficiently obtain valid candidate points within a given slab. Next, a multi-slab based decoding algorithm finds the optimal solution by conducting intersections on the obtained candidate set with dynamic radius adaptation. Furthermore, an optimal preprocessing technique is proposed from the geometrical perspective and the comprehensive analysis on the complexity reduction is also provided. The proposed decoder incorporating preprocessing scheme offers a low (non-exponential) computational complexity and near-ML decoding performance for underdetermined MIMO systems, particularly with large number of antennas and/or high-order constellations. Finally, a tree based codebook search algorithm for uplink (UL) coordinated multipoint (CoMP) systems is proposed. The codebook search issue can be reformulated as a tree search form and the solution can be obtained efficiently using a modified K-Best enumeration strategy. The proposed approach provides the advantage of low computational complexity and nearly the same performance of the exhaustive search algorithm, especially when the CoMP size is significant. Simulation results show that these proposed algorithms can significantly reduce the computational complexity and maintain system performance, which provide a promising solution for future wireless communication systems.

Chinese Abstract i
English Abstract ii
Table of Contents v
List of Figures viii
List of Tables xi
Acronym Glossary xii
Notations xv
Chapter 1 Introduction 1
1.1 Basics of Multi-Antenna Systems 1
1.2 Basics of MIMO Decoder 2
1.3 Related Literature Review 4
1.4 Main Contributions 9
1.5 Organization of Dissertation 10
Chapter 2 Efficient Search Algorithm for Over- determined MIMO systems 12
2.1 Overview 12
2.2 Signal Model 13
2.3 Proposed Sorting Algorithm and Hardware Architecture 18
2.3.1 Candidate Sequence Generator in Complex Plane 18
2.3.2 Architecture of Highly-Parallel Comparison Circuit (HPCC) 25
2.3.3 Complexity Advantages 28
2.4 Proposed Search Strategy for Near-ML Performance 29
2.4.1 Preprocessing with Column Permutation 29
2.4.2 Proposed Search Strategy 30
2.4.3 Joint 2-Layer ML Search Algorithm 34
2.5 Computer Simulation and Discussions 38
2.6 Summary 48
Chapter 3 Geometry Based SDA for Under- determined MIMO systems 50
3.1 Overview 50
3.2 Signal Model for Underdetermined SDA 51
3.3 Proposed Decoding Algorithms for Underdetermined Systems 54
3.3.1 An Efficient Slab Search (ESS) Algorithm 55
3.3.2 A Multi-slab Sphere Decoding (MSSD) Algorithm 57
3.4 Proposed Preprocessing Technique for Complexity Reduction 60
3.4.1 A Preprocessing with Column Permutation 60
3.4.2 Complexity Analysis 64
3.5 Computer Simulation and Discussions 69
3.6 Summary 76
Chapter 4 Efficient Search Algorithm for Codebook Search in Uplink CoMP Systems 77
4.1 Overview 77
4.2 Signal Model 78
4.3 Propsoed Codebook Serach Algorithm 81
4.4 Simulation Results 85
4.5 Summary 88
Chapter 5 Conclusions and Future Works 91
5.1 Summary of Dissertation 91
5.2 Future Works 92
APPENDIX 94
Bibliography 101

[1] E. Telatar, “Capacity of multi-antenna Gaussian channels,” AT&;T Bell Labs Internal Tech. Memo., June 1995.
[2] G. J. Foschini and M. J. Gans, “On limits of wireless communications in a fading environment when using multiple antennas,” Wireless Personal Commun., vol. 6, no.3, pp. 311-355, Mar. 1998.
[3] S. M. Alamouti, “A simple transmitter diversity scheme for wireless communication,” IEEE J. Select. Areas Commun., vol. 16, pp. 1451-1458, Oct. 1998.
[4] G. J. Foschini, “Layered space-time architecture for wireless communication in a fading environment when using multi-element antennas,” AT&;T Bell Labs Tech. J., pp. 41-59, Aug. 1996.
[5] A. J. Goldsmith and S. G. Chua, “Variable-rate variable-power MQAM for fading channels,” IEEE Trans. Commun., vol. 45, no. 10, pp. 1218-1230, Oct. 1997.
[6] S. Catreux, V. Erceg, D. Gesbert, and R. W. Heath, “Adaptive modulation and MIMO coding for broadband wireless data networks,” IEEE Commun. Mag., vol. 40, no. 6, Junly 2002.
[7] G. J. Foschini, G. D. Golden, R. A. Valenzuela, and P. W. Wolniansky, “Simplified processing for high spectral efficiency wireless communication employing multi-element arrays,” IEEE J. Select. Areas Commun., vol. 17, no. 11, pp. 1841-1852, Nov. 1999.
[8] P. W. Wolniansky, G. J. Foschini, G. D. Golden, and R. A. Valenzuela, ”Detection algorithm and initial laboratory results using V-BLAST space-time communication architecture,” Electronic Letters, vol. 35, no. 1, pp. 14-16, Jan. 1999.
[9] 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.
[10] 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.
[11] H. Vikalo and B. Hassibi, “On the sphere-decoding algorithm II. generalizations, second-order statistics, and applications to communications,” IEEE Trans. Signal Processing, vol. 53, no. 8, pp. 2819-2834, Aug. 2005.
[12] C. P. Schnorr and M. Euchner, “Lattice basis reduction: improved practical algorithms and solving subset sum problems,” Math. Programming, vol. 66, pp. 181-191, 1994.
[13] W. Zhao and G. B. Giannakis, “Reduced complexity closest point decoding algorithms for random lattices,” IEEE Trans. Wireless Commun., vol. 5, no. 1, pp. 101-111, Jan. 2006.
[14] Z. Guo and P. Nilsson, “Algorithm and implementation of the K-best sphere decoding for MIMO detection,” IEEE J. Select. Areas Commun., vol. 24, no. 3, pp. 491-503, Mar. 2006.
[15] A. Burg, M. Borgmann, M. Wenk, M. Zellweger, W. Fichtner, and H. Bo¨lcskei, “VLSI implementation of MIMO detection using the sphere decoding algorithm,” IEEE J. Solid-State Circuits, Vol. 40, No.7, pp. 1566–1577, July 2005.
[16] X. Huang, C. Liang, and J. Ma, “System architecture and implementation of MIMO sphere decoders on FPGA,” IEEE Tans. VLSI Systems, vol. 16, no. 2, pp. 188-197, Feb. 2008.
[17] K. Wong, C. Tsui, R. S. Cheng, and W. Mow, “A VLSI architecture of a K-best lattice decoding algorithm for mimo channels,” in Proc. IEEE ISCAS’02, vol. 3, May 2002, pp. 273-276.
[18] Y. H. Wu, Y. T. Liu, Y. C. Liao, and H. C. Chang, “Early-pruned K-best sphere decoding algorithm based on radius constraints,” in Proceedings of IEEE International Conference on Communications, ICC 2008, May 2008, pp. 4496-4500.
[19] Q. Li and Z. Wang, “Reduced compexity K-best sphere decoder design for MIMO systems,” Circuits, Systems, and Signal Processing, Birkhäuser Boston, vol. 27, no.4, pp. 491-505, Aug. 2008.
[20] M. Shabany and P. G. Gulak, “A 0.13um CMOS, 655Mbps, 4x4 64-QAM K-best MIMO detector,” International Solid-State Circuits Conference, Feb. 2009, pp. 256-257.
[21] B. Shim and I. Kang, “Sphere decoding with a probabilistic tree pruning,” IEEE Tans. Signal Processing, vol. 56, no. 10, pp. 4867-4878, Oct. 2008.
[22] Q. Li and Z. Wang, “Improved K-best sphere decoding algorithms for MIMO systems,” in Proc. IEEE ISCAS’06, May 2006, pp. 4-7.
[23] J. W. Choi, B. Shim, A. C. Singer, and N. I. Cho, “A low-complexity near-ML decoding technique via reduced dimension list stack algorithm,” in Proc. IEEE SAM 2008, July 2008, pp. 41-44.
[24] S. Roger, A. Gonzalez, V. Almenar, and A. M. Vidal, “Combined K-best sphere decoder based on the channel matrix condition number,” in Proc. ISCCSP’08, May 2008, pp. 1058-1061.
[25] S. Roger, A. Gonzalez, V. Almenar, and A. M. Vidal, “MIMO channel matrix condition number estimation and threshold selection for combined K-best sphere decoders,” IEICE Trans. Commun., no. 4, pp. 1380-1383, Apr. 2009.
[26] L. Azzam and E. Ayanoglu, .”Reduced complexity sphere decoding for square QAM via a new lattice representation,” in Proc. IEEE GLOBECOM, Nov. 2007, pp. 4242-4246.
[27] K. Amiri, C. Dick, R. Rao, and J. R. Cavallaro, “Novel sort-free detector with modified real-Vvalued decomposition (M-RVD) ordering in MIMO systems,” in Proc. IEEE GLOBECOM, Nov. 2008, pp. 4217-4221.
[28] M. Myllylä, M. Juntti, and J. R. Cavallaro, “Implementation aspects of list sphere detector algorithms,” in Proc. IEEE GLOBECOM, 2007, pp. 2915-3920.
[29] M. Myllylä, M. Juntti, and J. R. Cavallaro, “Implementation aspects of list sphere detector algorithms for MIMO-OFDM systems,” Signal Processing, vol. 90, issue 10, pp. 2863-2876, 2010.
[30] H. L. Lin, R. C. Chang, and H. L. Chen, “A high speed SDM-MIMO decoder using efficient candidate searching for wireless communication,” IEEE Trans. Circuits and Systems- II, vol. 55, no. 3, pp. 289-293, Mar. 2008.
[31] S. Mondal, K. N. Salama, and W. H. Ali, “A novel approach for K-best MIMO detection and its VLSI implementation,” in Proc. IEEE ISCAS’08, May 2008, pp. 936-939.
[32] E. Dekel and I. Ozsvath, “Parallel external sorting,” J. Parallel and Distributed Computing, vol. 6, pp. 623-635, 1989.
[33] Z. Wen, “Multi-way merging in parallel,” IEEE Trans. Parallel and Distributed Systems, vol. 7, no. 1, pp. 11-17, Jan. 1996.
[34] S. Mandal, A. Eltawil, and K.N. Salama, “Architectural optimiztions for low-power K-best MIMO decoders,” IEEE Trans. Vehicular Technology, vol. 58, no. 7, pp. 3145-3153, Sept. 2009.
[35] S. Mondal, A. Eltawil, C. A. Shen, and K. N. Salama, “Design and Implementation of a sort-free K-best sphere decoder,” IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol. 18, no. 10, pp. 1497-1501, Oct. 2010.
[36] K. Lee and J. Chun, “ML symbol detection based on the shortest path algorithm for MIMO systems,” IEEE Trans. Signal Processing, vol. 55, no. 11, pp. 5477-5484, Nov. 2007.
[37] A. K. Lenstra, H. W. Lenstra, and L. Lovasz, “Factoring polynomials with rational coefficients,” Math. Ann., vol. 261, no. 4, pp. 513-534, 1982.
[38] H. C. Chang, Y. C. Liao, and H. C. Chang, “Low-complexity prediction techniques of K-best sphere decoding for MIMO systems” Signal Processing Systems, 2007 IEEE Workshop, Oct. 2007, pp. 45-49.
[39] A. Wiesel, X. Mestre, A. Pages, and J. R. Fonollosa, “Efficient implementation of sphere demodulation,” IEEE Workshop on Signal Processing Advances in Wireless Communications (SPAWC), June, 2003, pp. 36-40.
[40] N. Balakrishnan and A. C. Cohen, Order Statistics and Inference Estimation Methods, New York: Academic, 1991.
[41] M. E. Muller, “A note on a method for generating points uniformly on n-dimensional spheres,” Comm. Assoc. Comp. Mach., vol. 2, pp. 19-20, Apr. 1959.
[42] M. O. Damen, K. Abed-Meraim, and J.-C. Belfiore, “A generalised sphere decoder for asymmetrical space–time communication architecture,” Elect. Lett., vol. 36, no. 2, pp. 166–167, Jan. 2000.
[43] T. Cui and C. Tellambura, “An efficient generalized sphere decoder for rank-deficient MIMO systems,” IEEE Commun. Lett., vol. 9, no. 5, pp. 423-425, May 2005.
[44] P. Wang and T. L. Ngoc, “A low-complexity generalized sphere decoding approach for underdetermined MIMO systems,” in Proc. IEEE ICC, 2006, pp. 4266-4271.
[45] P. Wang and T. L. Ngoc, “A low-complexity generalized sphere decoding approach for underdetermined linear communication systems: performance and complexity evaluation,” IEEE Trans. Commun., vol. 57, no. 11, pp. 3376-3388, Nov., 2009.
[46] G. Romano, F. Palmieri, P. S. Rossi, and D. Mattera, “A tree-search algorithm for ML decoding in underdetermined MIMO systems,” in Proc. ISWCS 2009, pp. 662-665.
[47] G. Romano, F. Palmieri, P. S. Rossi, and F. Palmieri, “Tree-search ML detection for underdetermined MIMO systems with M-PSK constellations,” in Proc. ISWCS 2010, pp. 102-106.
[48] Z. Yang, C. Liu, and J. He, “A new approach for fast generalized sphere decoing in MIMO systems,” IEEE Signal Processing Lett., vol. 12, no. 1, pp. 41-44, Jan. 2005.
[49] X. W. Chang and X. Yang, “An effieient tree search decoder with column recording for underdetermined MIMO systems,” in Proc. IEEE GLOBECOM 2007, pp. 4375-4379.
[50] K. K. Wong and A. Paulraj, “Efficient near maximum-likelihood detection for underdetermined MIMO antenna systems using a geometrical approach,” EURASIP Journal on Wireless Commun. and Networking, Oct. 2007.
[51] K. K. Wong, A. Paulraj and R. D. Murch, “Efficient high-performance decoding for overloaded MIMO antenna systems,” IEEE Trans. Wireless Commun., vol. 6, no. 5, pp. 1833-1843, May 2007.
[52] L. Bai, C. Chen, and J. Choi, “Prevoting cancellation-based detection for underdetermined MIMO systems,” EURASIP Journal on Wireless Commun. and Networking, vol. 2010, April 2010, article no. 96.
[53] K. Liu, and S. S. Xing, “Combined multi-stage MMSE and ML multiuser detection for underdetermined MIMO systems,” in Proc. CCWMC 2011 IET, 2011, pp. 10-14.
[54] T. Datta, N. Srinidhi, A. Chockalingam, and B. S. Rajan, “Low-complexity near-optimal signal detection in underdetermined large-MIMO systems,” in Proc. NCC 2012, 2012, pp. 1-5.
[55] C. J. Huang, C. Y. Wu, and T. S. Lee, “Geometry based efficient decoding algorithms for underdetermined MIMO systems,” in Proceedings of the IEEE SPAWC 2011, June 2011, pp. 371-375.
[56] K. K. Wong and A. Paulraj, “Near maximum-likelihood detection with reduced-complexity for multiple-input single-output antenna systems,” in Proc. Asilomar Conf. on Signals, Systems, and Computers, Nov. 2004.
[57] F. Khan, LTE for 4G Mobile Broadband: Air Interface Technologies and Performance, Cambridge University Press, 2009.
[58] 3GPP TS 36.211, “Physical channels and modulation (Release 11),” July 2013.
[59] M. Sawahashi, et al., "Coordinated multipoint transmission/reception techniques for LTE-Advanced," IEEE Wireless Commun. Mag., vol. 17, no. 3, pp. 26-34, Apr. 2010.
[60] R. Irmer, et al., “Coordinated multipoint: concepts, performance, and field trial results,” IEEE Commun. Mag., vol. 49, no. 2, pp. 102–111, Feb. 2011.
[61] 3GPP TR 36.819, “Coordinated multi-point operation for LTE physical layer aspects (Release 11),” Dec. 2011.
[62] M. Hong, R. Sun, H. Baligh, and Z.-Q. Luo, “Joint base station clustering and beamformer design for partial coordinated transmission in heterogeneous networks,” IEEE J. Sel. Areas Commun., vol. 31, no. 2, pp. 226-240, Feb. 2013.
[63] Y.-F. Liu, Y.-H. Dai, and Z.-Q. Luo, “Max-min fairness linear transceiver design for a multi-user MIMO interference channel,” IEEE Trans. Signal Process., vol. 61, no. 9, pp. 2413-2423, May 2013.
[64] D. Gesbert, S. Hanly, H. Huang, S. S. Shitz, O. Simeone, and W. Yu, “Multi-cell MIMO cooperative networks: a new look at interference,” IEEE J. Sel. Areas Commun., vol. 28, no. 9, pp. 1380-1408, Dec. 2010.
[65] M. R. McKay, I. B. Collings, and A. M. Tulino, “Achievable sum rate of MIMO MMSE receivers: A general analytic framework,” IEEE Trans. Inf. Theory, vol. 56, no. 1, pp. 396-410, Jan. 2010.
[66] R. Uehara and Y. Uno. “Efficient algorithms for the longest path problem,” in 15th Annual International Symposium on Algorithms and Computation (ISAAC 2004), 2004, pp. 871-883.