Design of a New Complex Sphere Decoder for Soft-Output MIMO Detection

下世代無線區域網路將提供越來越多樣化的服務，包括線上收看各種視訊影片、高畫質電視、網路互動式遊戲等，因此對於傳輸速度還有品質的要求越來越高。為了滿足有限頻寬下對高傳輸速率與高傳輸品質的要求，多輸入多輸出系統成為繼正交分頻多工技術後另一個極具市場潛力的關鍵技術。 多輸入多輸出系統可直接藉由增加傳輸與接收天線數來達成高傳輸速率的需求，卻也帶來信號解碼上的困難。相關文獻提出採用最大相似準則來進行多輸入多輸出解碼的球面演算法，理論上可達到最佳的解碼效能，並減輕原本和天線數量呈指數次方比的解碼複雜度。然而，球面解碼器相較於其他多輸入多輸出解碼方法而言，仍需付出較高的解碼代價，以換取位元錯誤率的降低。 有鑑於此，本論文結合改良式表列舉與最佳優先樹搜尋演算法，提出新的球面演算法，並輔以數學歸納法證明其搜尋效率的最佳性。在以迭代多輸入多輸出偵測解碼系統加以軟體模擬後，進一步證明新的球面解碼器可有效解決高階星座圖調變的列舉問題，而具有低複雜度高效能之特性，且優於現有的球面解碼器。此外，在有限運算複雜度限制下，本論文將新演算法結合連續消除演算法及提前終止演算法，以避免高天線數系統的效能衰減。最後，本論文提出硬體設計，說明將改良式最佳優先演算法應用在具軟性輸出解調之球面解碼器上的可實現性。The services, such as on-line videos, high definition TV (HDTV), interactive games, provided by the next generation wireless communication systems produce the demand for much higher throughput and better Quality of Service (QoS) under the situation of limited bandwidth. Nowadays, OFDM is widely adopted to improve bandwidth utilization in many communication systems and has become the main modulation technique of many standards. In the future, MIMO will be the next widely accepted technique because of its provision for diversity and spectrum efficiency. MIMO system can easily satisfy the demand for high throughput by increasing the number of transmit and receive antennas. For the QoS concern, the detection complexity grows exponential with the antenna number in theory. Corresponding literatures propose sphere decoder to mitigate this problem and conserve the near ML performance. However, the arithmetic complexity is still much more than other detection schemes. In order to overcome this trade-off problem, the thesis combines modified tabular enumeration and best-first tree search algorithm and therefore proposes the new sphere decoding algorithm: modified best-first (MBF) algorithm. After mathematic induction and software simulation by the iterative MIMO detection & decoding system, we demonstrate that MBF can not only reduce the enumeration complexity, especially for high-order QAM, but also conserve high performance from the characteristic of the best-first algorithm. Besides, in order to avoid the performance attenuation of high dimension MIMO system, we integrate successive interference cancellation algorithm, early termination algorithm and MBF into proposed MBF-SIC algorithm. Finally, we give the hardware design to show that the proposed soft-output MIMO complex-plane sphere decoder composed of MBF-SIC is reasonable for hardware implementation.圖目錄 v 表目錄 xi 1. 第一章 緒論 1 1.1. 背景 1 1.2. 動機 3 1.3. 研究簡介 5 1.4. 論文組織介紹 6 2. 第二章 多輸入多輸出系統 (MIMO System) 7 2.1. 本章介紹 7 2.2. 多輸入多輸出(MIMO)系統 7 2.2.1. 系統簡介 8 2.2.2. 信號模型 9 2.2.3. 通道容量(Channel Capacity) 10 2.2.4. 時空編碼(Space-Time Coding) 12 2.3. 多輸入多輸出信號解碼(MIMO Detection) 14 2.3.1. 線性解碼 14 2.3.1.1. 強制歸零(Zero-Forcing, ZF) 14 2.3.1.2. 最小均方錯誤(Minimum Mean Square Error, MMSE) 15 2.3.2. 非線性解碼 15 2.3.2.1. 縱向貝爾實驗室多層時空編碼(Vertical Bell Laboratories Layered Space-Time Code, V-BLAST) 15 2.3.2.2. 最大相似準則(Maximum Likelihood Criterion) 16 2.3.3. 線性適應多輸入多輸出訊號偵測(Linear Adaptive MIMO Decoding) 17 2.3.3.1. 最小均方(Least Mean Square) 18 2.3.3.2. 遞迴最小平方(Recursive Least-Squares) 18 2.3.4. 解碼輸出種類 19 2.3.4.1. 硬性解調輸出(Hard-output) 19 2.3.4.2. 軟性解調輸出(Soft-output) 19 2.4. 迭代多輸入多輸出信號解碼(Iterative MIMO Detection and Decoding) 20 2.4.1. 架構簡介 20 2.4.2. 最大化事後機率準則位元解碼(MAP Bit Detection) 21 2.4.3. 最大對數取值近似之最大化事後機率準則(MAX-Log-MAP) 23 2.5. 發展現況(State of the Art) 24 3. 第三章 複數平面球面解碼(Complex Sphere Decoding) 27 3.1. 本章介紹 27 3.2. 球面演算法(Sphere Algorithm) 27 3.3. 球面限制(Sphere Constraint) 29 3.4. 前置處理(Preprocessing) 32 3.4.1. 通道矩陣三角化(QR decomposition) 32 3.4.2. 通道矩陣欄能量排序 36 3.5. 樹狀搜尋(Tree Search) 37 3.5.1. 深度優先演算法(Depth-First Algorithm) 38 3.5.2. 廣度優先演算法(Breadth-First Algorithm) 40 3.5.3. 最佳優先演算法(Best-First/ Metric-First Algorithm) 41 3.5.4. 樹搜尋演算法的綜合分析 42 3.6. 列舉(Enumeration) 44 3.7. 硬性解調輸出之球面解碼(Hard-Output Sphere Decoding) 46 3.8. 軟性解調輸出之球面解碼(Soft-Output Sphere Decoding) 47 3.8.1. K-最佳演算法(K-best Algorithm) [24] 48 3.8.2. 列舉球面解碼器(List Sphere Decoder, LSD) [10] 49 3.8.3. 面臨的挑戰 50 4. 第四章 具軟性輸出之簡化複雜度球面解碼 51 4.1. 本章介紹 51 4.2. 表列舉(Tabular Enumeration) 51 4.2.1. 具最小部份代價有效點之尋找 52 4.2.2. 排序 54 4.2.3. 表號碼(List number, LN) 54 4.2.4. 表內容 56 4.2.4.1. 個別表(Individual List) 57 4.2.4.2. 統一表(Unified List) 57 4.2.4.3. 記憶體儲存量比較 60 4.2.5. 效能比較 60 4.2.5.1. 平均平方錯誤比較 60 4.2.5.2. 位元錯誤率比較 65 4.3. 改良式最佳優先演算法(Modified Best-First Algorithm, MBF) 66 4.3.1. 演算法架構 66 4.3.2. 數學歸納法證明 69 4.3.3. 模擬結果 76 4.3.3.1. 系統架構 76 4.3.3.2. 位元錯誤率比較 84 4.3.4. 高天線數時之效能衰減 89 4.4. 修正改良式最佳優先演算法(MBF Algorithm with SIC) 89 4.4.1. 連續消除演算法(Successive Interference Cancellation Algorithm) 90 4.4.2. 提前終止演算法(Early Termination Algorithm) 91 4.4.3. 模擬結果 92 4.4.3.1. 位元錯誤率比較 92 4.4.3.2. 運算複雜度比較 108 4.4.3.3. 資料儲存量比較 116 4.4.3.4. 綜合比較 117 5. 第五章 硬體架構 119 5.1. 本章介紹 119 5.2. 硬體架構設計 119 5.2.1. 可重置性(Reconfigurable Characteristic) 120 5.2.2. 計算單元(Calculation Unit) 121 5.2.2.1. 表列舉(Tabular Enumeration) 123 5.2.2.2. 移位加法器(Shift & Add) 125 5.2.2.3. 乘法器 (Multiplication) 127 5.2.3. 目標節點選取(Pool Control) 129 5.2.4. 軟性解調輸出產生器(Soft-Output Generator) 132 5.2.5. 平行處理(Parallel Processing) 134 6. 第六章 結論與展望 135 7. 參考資料 13