Gibbs Sampling based Near MAP Receiver Design for Multi-User Spread Spectrum Systems

在這篇論文中，我們首先架構一個統一的系統模型，分別適用於下傳同步直序分碼多工（direct-sequence code division multiple access, DS-CDMA），上傳非同步直序分碼多工，以及多載波分碼多工（multi-carrier code division multiple access, MC-CDMA）系統。接著我們會介紹幾種接近最大後機率以及最大概似的演算法，包含Gibbs抽樣方法，反覆條件最大化 (iterated conditional modes, ICM)以及期望值最大化 (expectation maximization, EM)。我們會採用這些演算法在上傳非同步DS-CDMA的接收機設計。此外，除了用戶資料的偵測，我們也會探討在盲蔽式接收機設計中，每個使用者的通道以及雜訊變異數之估測的問題。模擬的結果顯示，建構於Gibbs抽樣方法的接收機設計，其效能可以勝過ICM以及其他次佳的接收機。 基於樹狀結構搜尋之最短路徑的最佳接收機設計中，我們也提出了一個不規則樹狀結構搜尋(irregular tree search, ITS)可以進一步降低整體的複雜度。ITS可以視為一個隨機的過程去適應性地控制每一層所需保留的節點，因此在高訊號雜訊比的情況，和M-演算法相比，ITS 的複雜度能夠大幅地降低。模擬的結果顯示，在高訊號雜訊比時，無論是在效能和複雜度上，ITS都能有較好的表現。In this thesis, we first establish a unified system model for downlink synchronous direct-sequence code division multiple access (DS-CDMA), uplink asynchronous DS-CDMA, and multi-carrier CDMA (MC-CDMA) systems. Several near-maximum-a-posteriori (MAP) and near-maximum-likelihood (ML) algorithms, including Gibbs sampling, iterated conditional modes (ICM), and expectation-maximization (EM) are next introduced. These algorithms are adopted in the receiver design of uplink asynchronous direct-sequence CDMA (DS-CDMA) system. In addition to user data estimation, channel estimation for each user and noise variance estimation for blind receiver design are also investigated. Simulation results show that the performance of the Gibbs sampling based receiver outperforms ICM and other suboptimal receivers. Based on the tree search structure in the minimum distance optimal receiver, we also propose an irregular tree search (ITS) method to greatly reduce the overall complexity. ITS can be viewed as a stochastic procedure of adaptively controlling the survivors at each levels and thus, the complexity can be greatly reduced compared to the M-algorithm at high SNR. Simulation results show that at high SNR, ITS outperforms the M-algorithm both in error performance and complexity.Contents 1 Introduction 1 2 System Model of CDMA systems 5 2.1 MIMO System Model . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Signal Model of DS-CDMA . . . . . . . . . . . . . . . . . . . 7 2.2.1 Downlink Synchronous DS-CDMA . . . . . . . . . . . 9 2.2.2 Uplink Asynchronous DS-CDMA . . . . . . . . . . . . 12 2.3 MC-CDMA Signal Model . . . . . . . . . . . . . . . . . . . . . 14 2.3.1 OFDM System . . . . . . . . . . . . . . . . . . . . . . 15 2.3.2 Downlink Synchronous and Uplink Quasi-Synchronous MC-CDMA . . . . . . . . . . . . . . . . . . . . . . . . 17 3 Multiuser Detection 21 3.1 Detection in CDMA Systems . . . . . . . . . . . . . . . . . . . 21 3.2 Conventional Single User Matched Filter Detector . . . . . . . 23 3.3 Optimal Multiuser Detection . . . . . . . . . . . . . . . . . . . 24 3.3.1 Optimal Receiver Design . . . . . . . . . . . . . . . . . 24 3.3.2 Complexity of the tree search algorithm . . . . . . . . 27 3.4 Sub-Optimal Multiuser Detection . . . . . . . . . . . . . . . . 28 3.4.1 Linear Multiuser Detectors . . . . . . . . . . . . . . . . 29 3.4.2 Nonlinear Multiuser Detectors . . . . . . . . . . . . . . 30 4 Near Optimal Estimation Algorithms 41 4.1 Stochastic Estimation Algorithm . . . . . . . . . . . . . . . . 42 4.1.1 Markov chain . . . . . . . . . . . . . . . . . . . . . . . 42 4.1.2 Gibbs Sampling . . . . . . . . . . . . . . . . . . . . . . 43 4.2 Deterministic Optimization Algorithm . . . . . . . . . . . . . 47 4.2.1 The Expectation Maximization Algorithm . . . . . . . 47 4.2.2 Iterated Conditional Modes (ICM) . . . . . . . . . . . 49 5 The Near MAP Receiver Design 53 5.1 Near MAP Receiver Design with Perfect Channel Estimation . 53 5.2 Blind Near MAP Receiver Design . . . . . . . . . . . . . . . . 55 5.2.1 Derivations of Conditional Posteriori Distributions . . . 56 5.2.2 Generation of Inverse Gamma Random Variable . . . . 60 5.2.3 Interpretation of ICM receiver . . . . . . . . . . . . . . 60 5.2.4 Gibbs Sampling based blind receiver . . . . . . . . . . 61 6 Simulation Results 65 6.1 Performance of Near MAP Receiver . . . . . . . . . . . . . . . 65 6.1.1 Simulation Parameters . . . . . . . . . . . . . . . . . . 65 6.1.2 Receiver with perfect channel estimation . . . . . . . . 66 6.1.3 Blind Receiver . . . . . . . . . . . . . . . . . . . . . . . 69 6.2 Irregular Tree Search . . . . . . . . . . . . . . . . . . . . . . . 73 6.2.1 Simulation Parameters . . . . . . . . . . . . . . . . . . 74 6.2.2 Performance Evaluations . . . . . . . . . . . . . . . . . 74 7 Conclusions and Future Works 79 7.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 7.2 Future Works . . . . . . . . . . . . . . . . . . . . . . . . . . . 8