多輸入輸出系統之球體解碼與低密度奇偶校驗碼之研究

Abstract

本論文研究探討多輸入輸出系統之球體解碼（sphere decoding）與低密度奇偶校驗碼（low-density parity-check code, 簡稱LDPC code）解碼方式，藉由建立機率模型之理論分析與推導，經過電腦模擬驗證，提出適用於硬體實現之高效能低複雜度演算法。 球體解碼（Sphere Decoding）可描述為一個樹狀圖上找尋最佳路徑之問題，其中K-best algorithm為一常見之簡化演算法，其固定計算量之特色適合硬體實作。但為了維持與傳統sphere decoding相當之效能，需要大量排序運算，造成硬體實作時複雜度大幅增加。因此我們提出了低複雜度排序法與路徑刪除（early pruning）技巧，論文中所提出之路徑刪除技巧可及早在樹狀圖上刪去對應較低機率之路徑。路徑刪除條件與相關參數，可藉由建立與通道統計特性、路徑函數（path metric）以及系統錯誤率等所對應機率模型獲得；其平均計算量亦可依循此機率模型經由理論推導得到。根據理論分析之平均計算量，我們提出early-pruned multi-K-best algorithm，以進一步提升解碼速度。利用電腦模擬一64-QAM 4×4 MIMO系統，在維持與傳統sphere decoding相當之效能時，上述之方法可達到約90%計算複雜度之改進。 信度傳播（Log belief-propagation algorithm, 簡稱Log-BP algorithm）是常見LDPC碼解碼方法，其中需要之非線性運算通常以查表法或min-sum algorithm實現。前者需要大量硬體成本，且大量查表造成電路之時間延遲，故在設計高速解碼器多採用後者。為了減少min-sum algorithm由Log-BP algorithm簡化所造成之效能損失，我們探討並提出動態補償方法，此補償量可描述為解碼器輸入，通道雜訊，與解碼疊代次數之函數。我們進一步利用order statistic與density evolution等技巧分析並推導出此動態補償量函數，並依此提出三類可在硬體上實現之動態補償法。我們以此方法模擬DVB-S2系統，min-sum algorithm加上此動態補償僅造成5%之面積增加，最多可得到1.0dB之SNR改善。 論文最後探討MIMO接收端訊號偵測與通道解碼之相互影響。當系統採用如LDPC碼等需要以信度傳播作為解碼，sphere decoder需要修正為list sphere decoder，並產生一清單(candidate list)以計算通道解碼器需要之可靠度資訊。研究過程中發現，疊代解碼（iterative decoding）的收斂情形在MIMO環境中受到前級輸出之影響甚劇，當candidate過少時將造成嚴重error floor。然而，直接利用sphere decoding algorithm產生較大的candidate list所需要之複雜度過高，因此我們提出一種增加candidate之方式，相形之下需要之運算較少。最後我們模擬IEEE802.11n LDPC碼在64-QAM 4×4 MIMO通道之效能，採用我們提出之清單擴增方法，搭配路徑刪除法，在降低error floor的同時，最多可再減少94%之計算複雜度。

This dissertation presents algorithm designs for sphere decoders and low-density parity check (LDPC) code decoders in multi-input multi-output (MIMO) systems from implementation point of view. Based on statistical techniques, complexity reduction schemes are proposed. Sphere decoders of hard-decision outputs and LDPC decoding algorithms in AWGN channel are discussed first. Then the sphere decoders with soft-decision outputs for channel-coded MIMO systems are investigated. Sphere decoding algorithm is one realization of maximum likelihood signal detection for MIMO systems, and the computation can vary with channel due to the fading phenomena. Among several modified algorithms, K-best algorithm is suitable for hardware implementation for the constant computation and predictable hardware complexity. However, K-best algorithm has to be realized with the assumption of worst channel condition in order to maintain the system performance. For complexity reduction, an early pruning scheme combined with K-best algorithm is presented. According to the system model and channel statistics the expected complexity can be analyzed as well. Based on the complexity analysis, an early-pruned multi-K-best algorithm is proposed by which the lowest decoding speed can be further improved. The simulation results in 64-QAM 4 × 4 MIMO channel show that 90% complexity can be reduced with imperceptible degradation in both symbol error rate and bit error rate above 10−5. For decoding LDPC codes, min-sum algorithm is one common simplification of Log-BP algorithm, but there is a performance gap due to the approximation inaccuracy. Normalization schemes are investigated to compensate the approximation error. Moreover, the normalization factor can be described by a function of the decoder inputs, noise variance, and the decoding iteration number. The data-dependent correction terms can be analyzed and derived by order statistic and density evolution. Simulated in DVB-S2 system, the dynamic normalization schemes effectively mend the SNR loss from Log-BP algorithm to min-sum algorithm with few normalization overheads, and 1.0dB SNR improvement, which is about 95% of the SNR loss from Log-BP to min-sum algorithm, can be achieved. For channel coded MIMO systems, a sphere decoder is modified to a list sphere decoder that generates a candidate list for computing the soft inputs. Under iterative message passing decoding, the candidate list and the soft value generation impact the decoding convergence. Sufficiently large candidate list is required to avoid error floor. Thus, a path augmentation technique is proposed by which a larger and distinct list can be employed in computing the probabilistic information of each received bit. Compared with directly generating a larger list, path augmentation performs comparatively less operations. In our simulation based on a 64-QAM 4×4 MIMO system with LDPC codes defined in IEEE802.11n, the proposed augmented-list sphere decoder based on 64-best algorithm achieves the lowest error floor and saves about 50% computations, if compared to the standard list sphere decoder which is based on 128-best algorithm. Moreover, by the proposed early pruning scheme and multi-K-best algorithm, 94% reduction in sorting complexity can be achieved.