臺灣博碩士論文加值系統

在無線通訊系統中，多輸入多輸出(Multiple-Input Multiple-Output, MIMO)技術不需要增加額外的頻寬及傳輸功率便能提高傳輸速率及改善傳輸品質。然而，在多輸入多輸出系統中要設計出具高性能且低複雜度之接收機是一項艱難的挑戰。使用最大可能偵測法能得到最佳的效能，然而其所需的運算複雜度會隨著傳送天線個數的增加呈指數的成長。球體解碼演算法能以較低的複雜度達到與最大可能偵測法相同之效能。然而，傳統的球體解碼演算法會有資料吞吐量不穩定之問題。K-best球體解碼演算法在每一層的節點搜尋當中只保留K個最佳的候選點當作下一次搜尋的依據，因此具有穩定的資料吞吐量。然而，K-best球體解碼演算法需要取相當大的K值才能達到近似最大可能偵測法之效能。除此之外，在每一層的節點搜尋中將候選點作排序取出K個最佳的候選點會耗費大量的記憶體存取。在本論文中，吾人提出ㄧ具高效率搜尋架構之複數K-best球體解碼器。此解碼器能夠大幅降低排序時所花費的運算量。針對所提出之複數候選點搜尋方法，吾人亦設計出相對應之電路架構圖。經由分析與模擬的驗證，此解碼器僅需選取較小的K值即可達到近似最大可能偵測法之效能。

In wireless communication systems, multiple-input and multiple-output (MIMO) technology offers significant increases in data rate and link range without additional bandwidth or transmit power. However, the design of high performance and low complexity receivers for MIMO systems is a challenging task. The maximum-likelihood (ML) detection is the optimal detection scheme but its complexity grows exponentially with the number of transmit antennas. The sphere decoding algorithm (SDA) achieves the ML performance with reduced complexity. Nevertheless, the throughput of the conventional SDA is not stable. The K-best SDA which keeps only K-best candidates at each layer for the search of next layer is guaranteed to have a stable throughput. However, to achieve a near-ML performance, the value of K should be sufficiently large. Besides, applying a sorting algorithm to find K-best candidates at each layer requires a large amount of memory access. In this thesis, we propose a complex K-best sphere decoder with an efficient search architecture. The proposed K-best sphere decoder significantly reduces the sorting complexity. We also provide the hardware architecture of the proposed complex candidate search method. It is demonstrated through analysis and simulations that the proposed K-best sphere decoder achieves a near-ML performance without requiring a large value of K.

Chinese Abstract I
English Abstract II
Acknowledgement III
Contents IV
List of Figures VI
List of Tables VIII
Acronym Glossary IX
Notations XI
Chapter 1 Introduction 1
Chapter 2 MIMO Systems 4
2.1 System Model 4
2.2 Channel Capacity 6
2.3 MIMO Diversity 8
2.3.1 Receive Diversity 8
2.3.2 Transmit Diversity 9
2.4 Spatial Multiplexing 10
2.5 MIMO Detection 13
2.5.1 Linear Detection 13
2.5.2 Non-Linear Detection 14
2.6 Sphere Decoding Algorithm (SDA) 16
2.6.1 Fincke and Pohst SDA 19
2.6.2 Schnorr and Euchner SDA 20
2.6.3 K-Best SDA 21
2.6 Summary 22
Chapter 3 Proposed Complex K-Best Sphere Decoding Algorithm 24
3.1 Complex K-Best SDA 24
3.2 Efficient Sorting Strategy 27
3.3 Efficient Complex Domain Search Method 32
3.4 Preprocessing 38
3.5 ML-Like Search Strategy 39
3.6 Computer Simulations 40
3.7 Summary 44
Chapter 4 Hardware Architecture and Sorting Complexity Analysis of Proposed Algorithm 45
4.1 Hardware Architecture 45
4.2 Discussion on Proposed ML-Like Search Strategy 49
4.3 Sorting Complexity Analysis 55
4.4 Simulation Results 58
4.5 Summary 65
Chapter 5 Conclusions and Future Works 66
Bibliography 69

[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 using multiple antennas,” Wireless Personal Commun., vol. 6, no.3, pp. 311-335, Mar. 1998.
[3] S. M. Alamouti, “A simple transmit diversity scheme for wireless communication,” IEEE J. Select. Areas Commun., vol. 16, no. 8, 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, Autumn 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, pp. 108-115, Jun. 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] G. D. Golden, G. J. Foschini, R. A. Valenzuela and P. W. Wolniansky, ”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, no. 170, pp. 463-471, Apr. 1985.
[10] B. Hassibi and H. Vikalo, “On the sphere-decoding algorithm I. expected complexity,” IEEE Trans. Signal Process., 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 Process., 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, Aug. 1994.
[13] K. W. Wong, C. Y. Tsui, R. S. Cheng and W. H. Mow, “A VLSI architecture of a K-best lattice decoding algorithm for MIMO channels,” in Proc. IEEE ISCAS’02, vol. 3, pp. 273-276, May 2002.
[14] Q. W. Li and Z. F. Wang, “Improved K-best sphere decoding algorithms for MIMO systems,” in Proc. IEEE ISCAS’06, pp. 1159-1162, May 2006.
[15] S. Roger, A. Gonzalez, V. Almenar and A. M. Vidal, “Combined K-best sphere decoder based on the channel matrix condition number,” ISCCSP’08, pp. 1058-1061, May 2008.
[16] 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, pp. 936-939, May 2008.
[17] T. M. Cover and J. A. Thomas, Elements of Information Theory, John Wiley & Sons, Inc., 1991.
[18] P. W. Wolniansky, G. J. Foschini, G. D. Golden and R. A. Valenzuela, “V-BLAST: An architecture for realizing very high data rates over the rich-scattering wireless channel,” in Proc. URSI ISSSE-98, pp. 295-300, 1998.
[19] M. Grotschel, L. Lovasz and A. Schriver, Geometric Algorithms and Combinatorial Optimization, 2nd ed. New York: Springer-Verlag, 1993.
[20] D. Knuth, The Art of Computer Programming, Volumn 3: Sorting and Search, 3rd ed., Addison-Wesley, 1997.
[21] 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), pp. 36-40, Jun. 2003, Rome, Italy.
[22] N. Kobayashi, M. Ohnishi, M. Kova, N. Tsukamoto and Y. Kokuryou, “Simplified viterbi decoding for high speed data modem,” in Proc. IEEE GLOBECOM’87, vol. 1, pp. 472-478, Nov. 1987, Japan.
[23] K. Lee and J. Chun, “ML symbol detection based on the shortest path algorithm for MIMO systems,” IEEE Trans. Signal Process., vol. 55, no. 11, pp. 5477-5484, Nov. 2007.
[24] A. K. Lenstra, H. W. Lenstra and L. Lovasz, “Factoring polynomials with rational coefficients,” Math. Ann., vol. 261, no. 4, pp. 513-534, 1982.
[25] 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.
[26] N. Balakrishnan and A. C. Cohen, Order Statistics and Inference Estimation Methods, New York: Academic, 1991.
[27] M. E. Muller, “A note on a method for generating points uniformly on n-dimensional spheres,” Comm. Assoc. Comp. Mach., vol. 2, no. 4, pp. 19-20, Apr. 1959.
[28] 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.
[29] D. Pham, K. R. Pattipati, P. K. Willett and J. Luo, “An improved complex sphere decoder for V-BLAST systems,” IEEE Signal Process. Letters, vol. 11, no. 9, pp.748-751, Sep. 2004.