臺灣博碩士論文加值系統

在這篇論文裡，我們推薦了一個具有高輸出率、固定複雜度的軟性輸出球體解碼器，並支援QPSK、16-QAM、64-QAM調變的4x4多輸入多輸出通訊系統。

為了達到軟性輸出，本論文提出了特定的搜尋樹演算法。隨著一些模擬的數據結果，可以修改原始硬性輸出的固定式球體解碼器(Fixed-complexity Sphere Decoder, FSD)的搜尋樹而成為具有軟性輸出的搜尋樹。和理想的球體解碼器相比，所提出的軟性輸出固定複雜度球體解碼器(Soft-output FSD, SFSD)有少許訊框錯誤率表現上的衰退(0.5dB)，但是得到的好處是得到固定的運算複雜度還有更適合用平行或是管線(pipeline)的硬體架構來實現。

除此之外，一個高傳輸率的硬體架構被提出來實現SFSD的演算法。球體解碼器的列舉部分透過一些設計來達到簡化。平行的硬體架構被採用來達成高傳輸率。許多的管線電路也被適當的插入硬體架構之中以達到高的運作時脈。這些設計都被採用來達成高傳輸率同時降低複雜度的目的。

最後，電路使用台積電的0.18um的製程和本實驗室特有的元件資料庫(Cell Library)進行合成。在經過合成後，所提出的硬體架構面積大約有100k的等效邏輯閘面積。等效的邏輯閘是最基本的NAND邏輯閘。最快傳輸率在16-QAM調變的時候可以達到120Mbps。而FPGA的擬真也同樣的完成以達到驗證所設計的電路是否真的能使用。於是一個高解碼表現、高傳輸率的軟性輸出MIMO偵測器完整的從本論文中提出。

In this thesis, a high throughput fixed complexity soft-output sphere decoder supporting QPSK, 16-QAM, and 64-QAM modulation in the 4x4 MIMO system is proposed.

For achieving soft-output, the proposed tree search algorithm is presented. Some simulation results help to modify the tree search algorithm of the original fixed-complexity sphere decoder (FSD) for soft-output detection. Compared with the optimal soft-output sphere decoder, the proposed soft-output FSD (SFSD) has a little frame error rate (FER) degradation (0.5dB), but the benefit is that SFSD has fixed complexity and can suit to a parallel or full pipeline hardware design.

Moreover, a high throughput hardware architecture is proposed to implement the SFSD algorithm. A simplified enumeration method is proposed to reduce the hardware complexity. The parallel architecture is proposed to achieve high throughput. For the high clock frequency, many pipelines are inserted into the proposed architecture.

In addition, the proposed SFSD is implemented by the 0.18um CMOS cell-library of HP laboratory. The area of proposed hardware implementation is about 100k equivalent gates corresponding to the two-input drive-one NAND gate. The maximum throughput can reach to 120Mbps with 16-QAM modulation. Finally, the FPGA emulation is made to verify the proposed design is able to work. Then a high performance high throughput soft-output MIMO detector has completely accomplished in the thesis.

1 Introduction 1
1.1 Overview of Wireless Communication Systems . . . . . . . . . . . . . . . . 1
1.2 Motivation of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.3 Organization of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 Multiple-Input Multiple-Output (MIMO) Systems 3
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 Multiple-Input Multiple-Output . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2.1 MIMO System Model . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2.2 Channel Capacity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.3 Categories of MIMO Techniques . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3.1 Diversity Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3.2 Spatial Multiplexing . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.3.3 Precoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.4 Hard-Output and Soft-Output . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.5 Turbo-MIMO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.5.1 MIMO APP Detection . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.5.2 Simplification APP Detection . . . . . . . . . . . . . . . . . . . . . 13
3 Detection for Spatial Multiplexing MIMO Communications 15
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.2 Linear Detector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.2.1 Zero Forcing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.2.2 Minimum Mean Square Error . . . . . . . . . . . . . . . . . . . . . 16
3.3 Nonlinear Detector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.3.1 Maximum Likelihood . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.3.2 Ordered Successive Interference Cancelation . . . . . . . . . . . . . 17
3.4 Sphere Decoder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.4.1 Sphere Constraint . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.4.2 Tree Pruning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.4.3 Preprocess with Sort . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.4.4 Enumeration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.4.5 Categories of Tree Search . . . . . . . . . . . . . . . . . . . . . . . 23
3.4.6 Soft-Output Sphere Decoder . . . . . . . . . . . . . . . . . . . . . . 26
4 Soft-Output Fixed Complexity Sphere Decoder 29
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.2 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.2.1 System Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.2.2 System Parameter . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.2.3 Simulation Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.2.4 SNR Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.3 Soft-Output Fixed-Complexity Sphere Decoder . . . . . . . . . . . . . . . . 32
4.3.1 Tree Search for Soft-Output . . . . . . . . . . . . . . . . . . . . . . 32
4.3.2 Modified FSD Algorithm for Soft-Output . . . . . . . . . . . . . . . 35
4.3.3 Comparison of SFSD Distribution . . . . . . . . . . . . . . . . . . . 36
4.3.4 Simplified Enumeration for proposed SFSD algorithm . . . . . . . . 38
4.3.5 Complexity Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 40
5 Hardware Implementation and Measurement 45
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
5.2 Design Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
5.3 Architecture Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
5.3.1 Proposed Architecture . . . . . . . . . . . . . . . . . . . . . . . . . 46
5.3.2 Partial Euclidean Distance (PED) Part . . . . . . . . . . . . . . . . . 48
5.3.3 List Administration Unit (LAU) Part . . . . . . . . . . . . . . . . . . 48
5.3.4 LLR computation Part . . . . . . . . . . . . . . . . . . . . . . . . . 48
5.4 Word-Length Determination . . . . . . . . . . . . . . . . . . . . . . . . . . 49
5.4.1 Word-Length Determination Method . . . . . . . . . . . . . . . . . 49
5.4.2 Simulation Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5.5 Hardware Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.5.1 First Partial Euclidean Distance Unit . . . . . . . . . . . . . . . . . . 52
5.5.2 Partial Euclidean Distance Unit . . . . . . . . . . . . . . . . . . . . 53
5.5.3 List-Administration Unit . . . . . . . . . . . . . . . . . . . . . . . . 53
5.5.4 Input Buffer and Output Buffer . . . . . . . . . . . . . . . . . . . . 54
5.6 FPGA Emulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.7 Complexity Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.8 Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.9 MIMO-OFDM Application . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
6 FutureWorks and Conclusions 61
6.1 Future Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
6.2 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
7 FutureWork and Conclusions 63
7.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
7.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

[1] J. Hagenauer and P. Hoeher, “A Viterbi algorithm with soft-decision outputs and its
applications,” in Proc. IEEE GLOBECOM, Dallas, TX, Nov. 1989, pp. 47.11-47.17.
[2] B. M. Hochwald and S. ten Brink, “Achieving near-capacity on a multiple-antenna
channel,” IEEE Truncations on Communication, vol. 51, no. 3, pp. 389-399, Mar. 2003.
[3] C. E. Shannon, “A mathematical theory of communication,” Bell Labs Technical Journal,
vol. 27, pp. 379-423, 1948.
[4] I. E. Telatar, “Capacity of multi-antenna Gaussian channels,” European Transactions on
Telecommunications, vol. 10, pp. 585-595, Nov. 1999.
[5] S. M. Alamouti, “A simple transmit diversity technique for wireless communications,”
IEEE Journal on Selected Area in Communications, vol. 16, no. 8, pp. 1451-1458, Oct.
1998.
[6] S. Guncavdi and A. Duel-Hallen, “Performance analysis of space-time transmitter diversity
techniques for WCDMA using long range prediction,” IEEE Transactions on
Wireless Communications, vol. 4, no. 1, pp. 40-45, Jan. 2005.
[7] C. Berrou, A. Glavieux, and P. Thitimajshima, “Near Shannon limit error-correcting
coding and decoding: turbo-codes,” in Proc. International Conference on Communications,
May 1993, pp. 1064-1070.
[8] G. J. Foschini, “Layered space-time architecture for wireless communication in a fading
environment when using multiple antennas,” Bell Labs Technical Journal, vol. 1, no. 2,
pp. 41-59, 1996.
[9] M. Pohst, “On the computation of lattice vectors of minimal length, successive minima
and reduced bases with applications,” ACM SIGSAM Bulletin, vol. 15, no. 1, pp. 37-44,
Feb. 1981.
[10] U. Fincke and M. Pohst, “Improved methods for calculating vector of short length in
lattice, including a complexity analysis,” Mathematics of Computation, vol. 44, no. 170,
pp. 463-471, Apr. 1985.
[11] E. Viterbo and J. Boutros, “A universal lattice decoder for fading channels,” IEEE
Transactions on Information Theory, vol. 45, no. 5, pp. 1639-1642, Jul. 1999.
[12] M. O. Damen, H. El Gamal, and G. Caire, “On maximum likelihood detection and the
search for the closest lattice point,” IEEE Transactions on Information Theory, vol. 49,
no. 10, pp. 2389-2402, Oct. 2003.
[13] C. P. Schnorr and M. Euchner, “Lattice basis reduction: improved practical algorithms
and solving subset sum problems,” Mathematical Programming, vol. 66, no. 2, pp. 181-
191, Sep. 1994.
[14] Z. Guo and P. Nilsson, “Algorithm and implementation of the K-best sphere decoding
for MIMO detection,” IEEE Journal on Selected Area in Communications, vol. 24, no.
3, pp. 491-503, Mar. 2006.
[15] D. W�鈉bben, R. B�酣hnke, J. Rinas, V. K�鈉hn, and K. Kammeyer, “Efficient algorithm for
decoding layered space-time codes,” Electronics Letters, Vol. 37, no. 22, pp. 1348-1350,
Oct. 2001.
[16] L. G. Barbero and J. S. Thompson, “A fixed-complexity MIMO detector based on the
complex sphere decoder,” in Proc. IEEE Workshop SPAWC, Cannes, France, Jul. 2006,
vol. 1, pp. 1-5.
[17] C. Studer, A. Burg, and H. Bぴolcskei, “Soft-output sphere decoding: algorithms and
VLSI implemntation,” IEEE Journal on Selected Areas in Communications, vol. 26,
no.2, pp. 290-300, Feb. 2008.
[18] L. R. Bahl, J. Cocke, F. Jelinek, and J. Raviv, “Optimal decoding of linear codes for
minimizing symbol error rate,” IEEE Transactions on Information Theory, vol. IT-20(2),
pp. 284-287, Mar. 1974.
[19] G. E. P. Box and M. E. Muller, “A Note on the generation of random normal deviates,”
The Annals of Mathematical Statistics, vol. 29, pp. 610-611, 1958.
[20] A. Burg, M. Borgmann, M. Wenk, M. Zellweger, W. Fichtner, and H. Bぴolcskei, “VLSI
implementation of MIMO detection using the sphere decoding algorithm,” IEEE Journal
of Solid-State Circuits, vol. 40, no. 7, pp. 1566-1577, Jul. 2005.
[21] S. Chen, T. Zhang, and Y. Xin, “Relaxed K-best MIMO signal detector design and VLSI
implementation,” IEEE Trans. VLSI Systems, vol. 15, no. 3, pp. 328-337, Mar. 2007.
[22] S. Chen and T. Zhang, “Low power soft-output signal detector design for wireless
MIMO communication systems,” International Symp. Low Power Electronics and Design,
pp. 232-237, 2007.
[23] L. G. Barbero and J. S. Thompson, “Extending a fixed-complexity sphere decoder to obtain
likelihood information for turbo-MIMO systems,” IEEE Transactions on Vehicular
Technology, vol. 57, no. 5, pp. 2804-2814, Sep. 2008.