利用K-Best演算法之軟性里德索羅門解碼器

Abstract

本論文提出了利用K-Best演算法之軟性里德索羅門解碼器。這個方法主要可以分成三個部分：前置處理、候選人選擇機制、消去解碼。 在前置處理的部分，我們根據接收到的軟性資訊，給予每一個接收到的符號一個可信度。候選人選擇機制的部分，利用可信度的資訊以及獨立的特性去產生出可能的候選人組合。因為可能的組合有很多，所以利用K-Best演算法的限制來降低運算量。在第三個部分，消去解碼被用來解可能的候選人組合。為了找到合理的候選人數量，需要考慮到兩個相抗衡的項：性能和複雜度。 模擬的結果顯示，在里德索羅門碼(15,11)的狀況，所提出的演算法在字碼錯誤率(CER)為10-4時，其效能比硬性的BerleKamp-Messy(HD-BM)演算法好2.4dB，並且比Kotter-Vardy(KV)好1.3dB。與KV演算法比較時，運算複雜度至少降低了41.7%。而與動態可靠度傳播-代數軟性選擇(ABP-ASD)演算法比較，當字碼錯誤率等於10-4還有0.3dB的效能差距，但是複雜度降低了至少75.5％。對於里德索羅門碼(31,25)，提出的方法在字碼錯誤率等於10-4時，比HD-BM演算法好1.4dB並且比KV演算法好0.55dB。複雜度部分，則比KV降了至少61.6%。但是對於ABP-ASD演算法尚有1.25dB的效能差距，但是複雜度至少降低了97%。

In this thesis, the soft Reed-Solomon (RS) decoder based on K-Best algorithm with constraint is proposed. The proposed algorithm consists of three parts, pre-processing, candidate selecting and erasure only decoding. In pre-processing, the reliability is assigned to the received symbols according to the soft information from the channel. The candidate selecting uses the reliability information and the independent property to generate the possible candidate sets. Since the number of possible candidate sets is large, the K-Best algorithm is utilized to reduce the computation number. In the third part, erasure-only decoding is used to decode possible candidate sets. To provide a reasonable number of candidates, the trade-off between performance and complexity is considered. Simulation results show that for RS (15,11), the proposed algorithm outperforms the hard-decision Berlekamp-Messy (HD-BM) algorithm by 2.4dB and the Kotter-Vardy(KV) algorithm by 1.3dB at codeword error rate (CER) of 10-4. As compared with the KV algorithm the complexity reduction is at least 41.7%. And comparing with the adaptive belief propagation-algebraic soft decision (ABP-ASD) algorithm, there is 0.3dB performance gap at CER of 10-4. However, the complexity reduction is at least 75.5%. For RS (31,25), it outperforms the HD-BM algorithm by 1.4dB and the KV algorithm by 0.55dB at CER of 10-4. The complexity reduction is at least 61.6% as compared to the KV algorithm. There is 1.25dB performance gap between ABP-ASD and proposed method at CER of 10-4. However, the complexity reduction is at least 97%.