高效率之球型解碼演算法及其應用

Abstract

多輸入多輸出系統中，高效率且低功率消耗之接收機的設計為關鍵議題之ㄧ。在本論文中，吾人首先以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.