臺灣博碩士論文加值系統

本論文提出了利用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%.

1 Introduction 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Thesis organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 Soft decoding of RS codes 4
2.1 System model of RS code . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Basic properties of Reed Solomon codes . . . . . . . . . . . . . . . . . . . . 5
2.3 Generalized minimum distance algorithm . . . . . . . . . . . . . . . . . . . 6
2.4 Chase decoding algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.5 Algebraic soft decision decoding algorithm . . . . . . . . . . . . . . . . . . 8
2.6 Iterative Reed-Solomon decoding algorithm . . . . . . . . . . . . . . . . . . 8
3 Proposed soft RS decoding with K-Best algorithm 12
3.1 Pre-processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.1.1 Candidate generation . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.1.2 Reliability ordering . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.1.3 Re-order generator matrix . . . . . . . . . . . . . . . . . . . . . . . 16
3.1.4 Re-encoding process . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.2 Candidate selecting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2.1 K-Best algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2.2 Parallel K-Best algorithm . . . . . . . . . . . . . . . . . . . . . . . 19
3.2.3 Parallel K-Best algorithm with constraint . . . . . . . . . . . . . . 22
3.3 Erasure-only decoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4 Simulation results and complexity comparison 28
4.1 Simulation results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.2 Complexity comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
5 Conclusion and Future Work 39
5.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
5.2 Future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
6 Appendix: several techniques used for the proposed soft RS decoding 41
6.1 Simplied cost function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
6.2 Re-encode decoding based on reliability ordering . . . . . . . . . . . . . . . 42
6.3 Sphere decoding and K-Best algorithm . . . . . . . . . . . . . . . . . . . . 43
6.4 Erasure-Only Decoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

[1] E. R. Berlekamp, G. Seroussi, and P. Tong, Reed-Solomon Codes and Their Appli-
cation. Piscataway, NJ: IEEE Press, 1968.
[2] V. Guruswami and M. Sudan, \Maximum-likelihood decoding of Reed-Solomon codes
is NP-hard," IEEE Trans. Inf. Theory, vol. 51, pp. 2249{2256, July 2005.
[3] R. Kotter and A. Vardy, \Algebraic soft-decision decoding of Reed-Solomon codes,"
IEEE Trans. Inf. Theory, vol. 49, no. 11, pp. 2809{2825, Nov. 2003.
[4] V. Guruswami and M. Sudan, \Improved decoding of Reed-Solomon codes and alge-
braic geometry codes," IEEE Trans. Inf. Theory, vol. 45, pp. 1757{1767, Sep. 1999.
[5] J. Jiang and K. R. Narayanan, \Iterative soft-input soft-output decoding of Reed-
Solomon codes by adapting the parity-check matrix," IEEE Trans. Inf.Theory,
vol. 52, no. 8, pp. 3746{3756, Aug. 2006.
[6] M. E. Khamy and R. McEliece, \Iterative algebraic soft decision list decoding of
Reed-Solomon codes," IEEE Journal on selected areas in communications, vol. 24,
pp. 481{489, Mar. 2006.
[7] M. Fossorier and S. Lin, \Soft decision decoding of linear block codes based on ordered
statistics," IEEE Trans. Inf. Theory, vol. 41, pp. 1379{1396, Sep. 1995.
[8] G. Forney, \Generalized minimum distance decoding," IEEE Trans. Inf. Theory, vol.
IT-12, no. 2, pp. 273{276, 2002.
[9] D. Chase, \A class of algorithms for decoding block codes with channel measurement
information," IEEE Trans. Inf. Theory, vol. IT-18, no. 1, pp. 170{182, Jan. 1972.
[10] S. L. H. Tang, \On combining chase-2 and GMD decoding algorithms for nonbinary
block codes," IEEE Commin. Lett., vol. 5, no. 5, pp. 209{211, May 2001.
[11] L. E. Aguado and P. G. Farrel, \On hybrid stack decoding algorithms for block
codes," IEEE Trans. Inf. Theory, vol. 44, no. 1, pp. 398{409, Jan. 1998.
[12] J. Belzile and D. Haccoun, \Bidirectional breadth-rst algorithms for the decoding
of convolutional codes," IEEE Trans. Inf. Theory, vol. 41, no. 2, pp. 370{380, Feb.
1993.
[13] E. R. Berlekamp, Algrbraic coding theory. New York: McGraw-Hill, 1968.
[14] R. Bose and D. K. Ray-Chaudhuri, \On a class of error correcting binary group
codes," Inform. Control, Mar. 1960.
[15] S. Lin and D. Costello, Error Control Coding-Fundamentals and Applications. 2nd
ed. Pearson Prentice Hall, 2004.
[16] F. Shayegh and M. Soleymani, \Soft decision decoding of Reed-Solomon codes using
sphere decoding," IEEE International Conference on Communication(ICC) 2008,
May 2008.
[17] T. Cormen, C. Leiserson, R. Rivest, and C.Stein, Introduction to algorithms. 2nd
ed. McGraw-Hill Book Company, 2003.
[18] B. Hassibi and H. Vikalo, \On the sphere-decoding algorithm I. Expected complex-
ity," IEEE Trans. Sigal Processing, vol. 53, no. 8, pp. 2806{2818, Aug. 2005.
[19] H. Chang, Y. Liao, and H. Chang, \Low-complexity prediction techniques of K-
Best sphere decoding for mimo systems," IEEE Workshop on Signal Processing Sys-
tems(SiPS) 2007, Oct. 2007.