臺灣博碩士論文加值系統

隨著資料傳輸速度及對傳輸品質的要求遽增，多輸入多輸出天線(MIMO)無線通訊系統已廣泛被使用。傳統QR分解演算法下之多輸入多輸出天線非最佳解碼器已不能提供可容忍之錯誤率(bit error rate)，因此晶格簡化演算法(lattice reduction)被提出應用。其演算法可使多輸入多輸出天線非最佳解碼器得到比原本效能好很多之錯誤率，且可逼近最佳解碼器(ML detector)的錯誤率。然而隨著天線數的增加，硬體的面積與運算複雜度也大幅的增加。本論文改良原始晶格簡化演算法(LLL algorithm)以及結合QR分解演算法，利用其演算法之關聯性，綜合考量二個演算法，可省略一些多餘的運算降低運算時間及硬體複雜度。又因其演算法有大部分相同運算，可使用運算元件共享來降低硬體面積。本論文所提出之處理器可對8x8多輸入多輸出系統執行完整的預先處理(pre-processing)。
最後我們利用TSMC 90奈米製程實現本論文所設計之處理器。所提出的處理器可支援多種操作模式。經由完整的驗證流程後，在8x8天線，單純處理QR分解的固定吞吐量(throughput)為2.77 M matrix/s，單純處理晶格簡化的固定吞吐量為1.24 M matrix/s，結合QR分解與晶格簡化之處理器的固定吞吐量為0.856 M matrix/s。如果考量在第三代合作夥伴計畫長期演進技術(3GPP-LTE Advanced)的規格下，最佳情況得到的吞吐量為234.72 M bit/s。雖然目前未能達到此規格之最大吞吐量要求，但如果往後在硬體面積能允許下，本設計將可達到此規格之吞吐量需求並且實現在實際應用上。

Due to the growing link quality demand of multiple-input multiple-output (MIMO) wireless communication system, traditional QR decomposition-based
sub-optimal MIMO detectors gradually cannot support enough bit error rate (BER) performance. In addition, lattice reduction algorithm is proposed to make sub-optimal MIMO detectors achieve the full diversity gain. However, due to the growing number of antennas, the hardware cost and the processing time become a big challenge for hardware design.
In this thesis, joint QR decomposition and lattice reduction algorithm is proposed to get better BER performance than only processing QR decomposition. Because both QR decomposition algorithm and lattice reduction algorithm should use Givens rotation processor, this proposed algorithm can combine both two algorithms to do the computation sharing and reduce the hardware cost. In addition, the proposed algorithm removes some unnecessary operations to reduce the computational complexity by joint consideration of this two algorithms. Moreover, the proposed algorithm uses the parallel processing scheme to shorten the processing time.
The proposed processor was implemented by TSMC 90nm 1P9M CMOS technology. The proposed processor can supply several different operating modes. According to the post-layout simulation result, the maximum throughput of 8x8 QR decomposition is 2.77 M matrix/s, the maximum throughput of 8x8 lattice reduction is 1.24 M matrix/s and the maximum throughput of joint QR decomposition and lattice reduction for 8x8 MIMO system is 0.856 M matrix/s. In addition, this process can achieve 234.72 M bps (bit per second) in 3rd Generation Partnership Project Long Term Evolution Advanced (3GPP LTE-Advanced) standard at the best case. Although this throughput cannot achieve the maximum throughput demand in 3GPP LTE-Advanced standard, the proposed design can do real-time implementation and achieve the throughput requirement without the limitation of hardware area.

1 Introduction
1.1 MIMO System
1.2 Research Motivation
1.3 Organization of This Thesis

2 Pre-processing for MIMO Systems
2.1 System Model
2.2 MIMO Detection
2.2.1 Linear Detection
2.2.2 Non-linear Detection
2.3 QR Decomposition Algorithm
2.3.1 Gram-Schmidt Method
2.3.2 Householder Transform Method
2.3.3 Givens Rotation Method
2.4 Lattice Reduction Algorithm
3 Proposed Joint QR Decomposition and Lattice Reduction Algorithm
3.1 Constant Throughput LLL Algorithm (CT-LLL)
3.2 Proposed Enhanced Constant Throughput LLL Algorithm (E-CTLLL)
3.2.1 Parameter Determination
3.2.2 Power Saving Scheme
3.2.3 Complexity Analysis
3.3 QR Decomposition and Full Size Reduction
3.4 Joint QR Decomposition and Lattice Reduction Algorithm
4 Architecture Design
4.1 2D and 4D CORDIC Algorithm
4.1.1 2D CORDIC Algorithm
4.1.2 4D CORDIC Algorithm
4.2 2D and 4D CORDIC Hardware Architecture
4.3 Givens Rotation Processor
4.4 Architecture Choose
4.5 System Architecture
4.6 Timing Schedule
4.7 Fixed-point Simulation
5 Implementation Result
5.1 Design Flow
5.2 Pre-synthesis Design and Verification
5.3 Synthesis Result
5.4 Post-layout Result
5.5 Measurement Consideration
5.6 Comparison
5.7 Application in 3GPP LTE-Advanced standard
6 Conclusion

[1] P.-L. Chiu and Y.-H. Huang, “A scalable MIMO detection architecture with non-sorted multiple-candidate selection,” in Circuits and Systems, 2009. ISCAS 2009.
IEEE International Symposium on, may 2009, pp. 689 –692.
[2] X. Cao, “Local maximum likelihood detection method for MIMO systems,”in Communications, Circuits and Systems, 2005. Proceedings. 2005 International Conference on, vol. 1, may 2005, pp. 203 – 206 Vol. 1.
[3] M. Shabany and P. Gulak, “Scalable VLSI architecture for K-best lattice decoders,”in Circuits and Systems, 2008. ISCAS 2008. IEEE International Symposium on,
may 2008, pp. 940 –943.
[4] Y. Wang and K. Roy, “A new reduced-complexity sphere decoder with true lattice-boundary-awareness for multi- antenna systems,” in Circuits and Systems, 2005.
ISCAS 2005. IEEE International Symposium on, may 2005, pp. 4963 – 4966 Vol.5.
[5] M. Taherzadeh, A. Mobasher, and A. Khandani, “LLL lattice-basis reduction achieves the maximum diversity in MIMO systems,” in Information Theory, 2005.
ISIT 2005. Proceedings. International Symposium on, sept. 2005, pp. 1300 –1304.
[6] A. K. Lenstra, H. W. Lenstra, and L. Lovasz, “Factoring polynomials with rational coefficients,” Math. Annalen, vol. 261, pp. 515–534, 1982.
[7] I. V. L. CLARKSON, “Approximation of Linear Forms by Lattice Points with Application to Signal Processing,” Australian National University PhD Thesis, January 1997.
[8] L. Barbero, D. Milliner, T. Ratnarajah, J. Barry, and C. Cowan, “Rapid Prototyping of Clarkson’s Lattice Reduction for MIMO Detection,” in Communications,
2009. ICC ’09. IEEE International Conference on, june 2009, pp. 1 –5.
[9] L. Bruderer, C. Studer, M. Wenk, D. Seethaler, and A. Burg, “VLSI implementation of a low-complexity LLL lattice reduction algorithm for MIMO detection,” in
Circuits and Systems (ISCAS), Proceedings of 2010 IEEE International Symposium on, 30 2010-june 2 2010, pp. 3745 –3748.
[10] C.-F. Liao and Y.-H. Huang, “Power-Saving 4x4 Lattice-Reduction Processor for MIMO Detection With Redundancy Checking,” Circuits and Systems II: Express
Briefs, IEEE Transactions on, vol. 58, no. 2, pp. 95 –99, feb. 2011.
[11] A. Youssef, M. Shabany, and P. Gulak, “VLSI implementation of a hardware-optimized lattice reduction algorithm for WiMAX/LTE MIMO detection,” in Cir-
cuits and Systems (ISCAS), Proceedings of 2010 IEEE International Symposium on, 30 2010-june 2 2010, pp. 3541 –3544.
[12] J. Soler-Garrido, H. Vetter, M. Sandell, D. Milford, and A. Lillie, “Implementation of a reduced-lattice MIMO detector for OFDM Systems,” in Design, Automation
Test in Europe Conference Exhibition, 2009. DATE ’09., april 2009, pp. 1626 –1631.
[13] C. K. Singh, S. H. Prasad, and P. T. Balsara, “A Fixed-Point Implementation for QR Decomposition,” in Design, Applications, Integration and Software, 2006 IEEE
Dallas/CAS Workshop on, oct. 2006, pp. 75 –78.
[14] Y. Wang, J. Wang, and Z. Xie, “Parallel MIMO detection algorithm based on householder transformation,” in Intelligent Signal Processing and Communication Systems, 2007. ISPACS 2007. International Symposium on, 28 2007-dec. 1 2007,pp. 180 –183.
[15] E. Antelo, J. Villalba, and E. Zapata, “A Low-Latency Pipelined 2D and 3D CORDIC Processors,” Computers, IEEE Transactions on, vol. 57, no. 3, pp. 404
–417, march 2008.
[16] J.-M. Delosme and S.-F. Hsiao, “CORDIC Algorithms in Four Dimensions,” vol.261, pp. 349–360, July 1990.
[17] S.-F. Hsiao and J.-M. Delosme, “The CORDIC Householder algorithm,” in Computer Arithmetic, 1991. Proceedings., 10th IEEE Symposium on, jun 1991, pp. 256
–263.
[18] A. Burg, “VLSI Circuits for MIMO Communication Systems,” 2006.
[19] J.-Y. Wang, R.-H. Lai, C.-M. Clien, P.-A. Ting, and Y.-H. Huang, “A 2x2-8x8 sorted QR decomposition processor for MIMO detection,” in Solid State Circuits
Conference (A-SSCC), 2010 IEEE Asian, nov. 2010, pp. 1 –4.
[20] P. Luethi, C. Studer, S. Duetsch, E. Zgraggen, H. Kaeslin, N. Felber, and W. Fichtner, “Gram-Schmidt-based QR decomposition for MIMO detection: VLSI implementation and comparison,” in Circuits and Systems, 2008. APCCAS 2008. IEEE Asia Pacific Conference on, 30 2008-dec. 3 2008, pp. 830 –833.
[21] “3GPP TS 36.211-3rd Generation Partnership Project,Technical Specification Group Radio Access Network,Evolved Universal Terrestrial Radio Access (E-
UTRA),Physical channels and modulation,"Rev.10.0.0,December 2010.
[22] P. Meher, J. Valls, T.-B. Juang, K. Sridharan, and K. Maharatna, “50 Years of CORDIC: Algorithms, Architectures, and Applications,” Circuits and Systems I:
Regular Papers, IEEE Transactions on, vol. 56, no. 9, pp. 1893 –1907, sept. 2009.
[23] P. Luethi, A. Burg, S. Haene, D. Perels, N. Felber, and W. Fichtner, “VLSI Implementation of a High-Speed Iterative Sorted MMSE QR Decomposition,” in Circuits
and Systems, 2007. ISCAS 2007. IEEE International Symposium on, may 2007, pp.1421 –1424.
[24] Z. Guo and P. Nilsson, “A VLSI implementation of MIMO detection for future wireless communications,” in Personal, Indoor and Mobile Radio Communications,
2003. PIMRC 2003. 14th IEEE Proceedings on, vol. 3, sept. 2003, pp. 2852 – 2856 vol.3.
[25] C. Ling and N. Howgrave-Graham, “Effective LLL Reduction for Lattice Decoding,”in Information Theory, 2007. ISIT 2007. IEEE International Symposium on, june
2007, pp. 196 –200.
[26] G. Villard, “Parallel lattice basis reduction,” in International Conference on Symbolic and Algebraic Computation, 1992, pp. 269 –277.