Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/8439
標題: K-Best偵測器的排序電路設計與實現
Efficient Sorting for K-Best detector
作者: 林士鈞
Lin, Shih-Chun
關鍵字: 合併排序;sorting;球型解碼演算法;多輸入多輸出;K-Best;MIMO
出版社: 電機工程學系所
引用: [1] K. Pahlavan and A. H. Levesque, Wireless Information Networks, 2nd ed. Wiley, 2005. [2] J. G. Proakis, Digital Communications, 4th ed., McGraw-Hill, 2001. [3] B. Vucetic and J. Yuan, Space-Time Coding, Wiley, 2003. [4] M. Jankirman , Space-Time codes and MIMO systems, Artech House, 2004. [5] R. Shariat-Yazdi and T. Kwasniewski, “Reconfigurable K-best MIMO detector architecture and FPGA implementation” IEEE Conference on Intelligent Signal Processing and Communication Systems, 2007. [6] D. Gesbert, M. Shafi, Shiu Da-shan, P. J. Smith, and A. Naguib, “From theory to practice: an overview of MIMO space-time coded wireless systems,” IEEE Journal on Selected Areas in Communications, vol.21, no.3, April 2003. [7] M. O. Damen, H. El Gamal, and G. Caire, “On maximum likelihood detection and the search for the closest lattice point,” IEEE Trans. Information Theory, vol. 49, No. 10, pp. 2389-2402, Oct. 2003. [8] Q. Li and Z. Wang, “An improved K-best sphere decoding architecture for MIMO systems,” Fortieth Asilomar Conference on Signals, Systems and Computers, pp.2190-2194, Oct.-Nov., 2006. [9] 張宜濡, “應用於多輸入多輸出偵測系統之改良型K-Best球型解碼演算法硬體設計與實現,”國立中興碩士論文,中華民國九十七年七月。 [10] T. H Cormen, C. E. Leiserson , R. L. Rivest, and C. Stein, Introduction to Algorithms, The MIT Press September 2009. [11] D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, Addison-Wesley, 1998. [12] R. C. T. Lee, S. S. Tseng, R. C. Chang, and Y. T. Tsai, Introduction to the Design and Analysis of Algorithms, McGraw Hill 2005. [13] B. Wilkinson and M. Allen, Parallel Programming: Techniques and Application Using Networked Workstations and Parallel Computers, Prentice-Hall Inc., 2005. [14] A. Grama, A. Gupta, G. Karypis, and V. Kumar, Introduction to Parallel Computing, Addison Wesley, January 2003. [15] Y. N. Chang and C. J. Fu. “Design of VLSI sorting accelerator architecture,” IEEE Midwest Symposium on.Circuits and Systems, 2008. [16] R. Shariat-Yazdi and T. Kwasniewski, ”Configurable K-best MIMO detector architecture,” IEEE Conference on Communications, Control and Signal Processing, 2008. [17] H. Sahni and A. Freed, Fundamentals of Data Structures in C, Computer Science Press, 1993.
摘要: 
近年來,無線通訊用在視訊串流、線上影音下載…等新應用上已經越來越多,因此,使用者就需要更高速的無線網路和更好的通訊品質。除了使用正交分頻多工和64QAM調變技術滿足了提高傳輸速率的需求外,近年來更積極發展多輸入多輸出(Multiple-Input Multiple-Output)技術,以滿足市場對高傳輸速率無線通訊的需求。

MIMO偵測器的功用是在接收端將收到的訊號,回復為原始的傳送端之symbol。最大相似度偵測法是公認最佳化的演算法,有著最好的偵測效能,但運算複雜度將會隨著調變群集和傳送天線數目大小而呈指數型增加。K-Best球型解碼演算法因而被提出來,得到近似最大相似度偵測法的結果,解決最大相似度偵測法運算複雜度過高的問題。K-Best球型解碼演算法在計算完部份歐幾里德距離 (Partial Euclidean Distance)後,需要取最小K個值做為候選點,再往下層去找候選點。因此需先將部份歐幾里德距離的結果做排序,再選取出最小K個值。選取愈多的K參數值,就越趨近最大相似度的偵測效能,但等待排序的資料量會變得很大。

因此一般常用的泡沫搜尋法(Bubble Sort),並不適用在K-Best偵測器。本論文設計了一種改良型的最小值搜尋法,以合併排序(Merge Sort)為主要基礎,利用排序演算法幫助我們完成最小值的搜尋,不但比電路設計常用的泡沫搜尋法快速,且硬體面積也較小。

In recent years, with the increasing use of wireless communications in new applications such as video streaming, multimedia online downloads, it requires more high-speed wireless networks and better communication quality.

Orthogonal Frequency Division Multiplexing (OFDM) and 64QAM modulation techniques are utilized to improve the transmission rate to meet the requirement. But for new applications, users will require higher data rate for wireless application. Multiple-Input Multiple-Output (MIMO) technique began to be widely investigated.

MIMO detector receives the signal and recovers it to the original transmitted symbol. Maximum likelihood detector (MLD) is the optimal detector and has the best performance. The challenge of MLD is the high computational complexity. K-Best decoding algorithm has been proposed to reduce the computational complexity. K-Best decoder algorithm computes Partial Euclidean Distance (PED) and only keeps the best K nodes that have the smallest accumulated PEDs. After completing breadth-first tree search, we will have K leaves with the smallest PEDs. Therefore, K-Best algorithm is to find the K smallest PEDs. While K is larger, the performance is better, but the complexity is higher. That's why we require an efficient sorting algorithm.

An improved sorting algorithm for K-Best MIMO detector is designed in this thesis. The sorter is based on the Merge Sort and is much faster and smaller than the commonly used Bubble Sort.
URI: http://hdl.handle.net/11455/8439
其他識別: U0005-0602201000343200
Appears in Collections:電機工程學系所

Show full item record
 

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.