臺灣博碩士論文加值系統

　　里德-索羅門碼（Reed-Solomon codes）為一廣泛使用於數位通訊系統及資料儲存系統之錯誤更正碼。里德-索羅門碼之最大距離可分(maximum distance separable)性質令其擁有極佳之錯誤更正能力。一般里德-索羅門碼之應用，皆使用硬性決定解碼演算法（hard-decision decoding algorithm），如歐幾里德演算法（Euclidean algorithm）、Berlekamp-Massey 演算法等等。著眼於里德-索羅門碼之廣泛應用，提升里德-索羅門碼之錯誤更正能力為近年來持續研究之課題。我們提出了一個基於符碼可信度（symbol reliability）之里德-索羅門碼軟性決定解碼演算法(soft-decision decoding algorithm)。目前已提出之軟性決定解碼演算法，皆根據特定之準則（criterion），由軟性決定所得之資訊，求得一最大可能性字碼（maximum likelihood codeword）可能存在之子集。我們則嘗試先去尋找一些在Hamming geometry中，位於最大可能性字碼周圍的字碼，再藉由我們找到的這些字碼，嘗試去得到最大可能性字碼。
　　我們所提出的演算法，立基於里德-索羅門碼特有之代數性質:字碼與有限場之多項式（polynomial over finite field）間具有一對一對應闗係。我們根據符碼可信度，設定一符號場（symbol filed）之子集，再透過所有在該子集內無根的多項式，參考後置機率（a posterior probability）得到最大可能性周圍的字碼，最後運用這些字碼間的交集嘗試去求得最大可能性字碼。在特定子集中無根的多項式可以由質式(prime polynomial)求得，而質式與收到之字（word）無關，且可被預先儲存。這項特點使得我們的演算法具有以簡單的硬體實現之可能性。我們也提出了一個可能的硬體實驗架構。根據模擬的結果，與硬性決定解碼演算法比較，我們的演算法能夠提供 1.5 dB 的編碼增益。

　In this thesis, we propose a soft-decision decoding algorithms for Reed-Solomon codes based on symbol reliability.
　Our algorithm starts from the relationship between RS codewords and polynomials over a finite field. For an (n, k, d) RS code C over a finite field F, every codeword corresponds to a polynomial with degree less than k.
Our algorithm defines a subset of F composed of locators corresponding to least reliable positions, then works on a subset of C corresponding to polynomials without any root in the specified subset of F.
All polynomials without any root in a specified subset could be found by combination of primes in F[X], and primes are independent of the received word and could be stored in advance.
With this advantage and efficiency of finite field arithmetic, our algorithm could be easily implemented in hardware.
Simulations results confirm the validity of our decoding algorithm and show 1.5 dB coding gain over hard-decision decoding algorithms.

第一章：簡介（第1頁）
第二章：里德-索羅門碼（第2頁）
第三章：軟性決定解碼演算法（第3頁）
第四章：一個基於符碼可信度之里德-索羅門碼軟性決定解碼演算法（第4頁）
第五章：模擬結果（第5頁）
第六章：結論（第6頁）
附　錄：英文論文本（第7頁）

Contents
1 Introduction 1
2 Reed-Solomon Codes 3
3 Soft-Decision Decoding Algorithms 12
4 Soft-Decision Decoding Algorithm Based on Symbol Reliability 19
5 Simulation 34
6 Conclusion 43
Bibliography 44

[1] I. S. Reed and G. Solomon, "Polynomial codes over certain fields," J. Soc. Ind. Appl. Math., vol. 8, pp. 300-304, Jun. 1960.

[2] J. G. David Forney, "Generalized minimum distance decoding," IEEE Trans. Inform.
Theory, vol. IT-12, pp. 125-131, Apr. 1966.

[3] M. P. C. Fossorier and S. Lin, "Soft-decision decoding of linear block codes based on ordered statistics," IEEE Trans. Inform. Theory, vol. 41, pp. 1379-1396, Sept. 1995.

[4] T.-H. Hu and S. Lin, "An efficient hybrid decoding algorithm for Reed-Solomon codes based on bit reliability," IEEE Trans. Inform. Theory, vol. 51, pp. 1073-1081, Jul. 2003.

[5] R. Koetter and A. Vardy, "Algebraic soft-decision decoding of reed-solomon codes," IEEE Trans. Inform. Theory, vol. 49, NO.11, pp. 2809-2825, Nov. 2003.

[6] M. Sudan, "Decoding of Reed-Solomon codes beyond the error-correction bound," Journal of complexity, vol. 13, pp. 180-193, Aug. 1997.

[7] V. Guruswami and M. Sudan, "Improved decoding of Reed-Solomon and algebraic-geometry codes," IEEE Trans. Inform. Theory, vol. 49, NO.6, pp. 1757-1767, Sep.1999.

[8] J. Jiang and K. R. Narayanan, "Iterative soft decoding of Reed-Solomon codes," IEEE Commun. Lett., vol. 8, pp. 244-246, Apr. 2004.

[9] M. El-Khamy and R. J. McEliece, "Iterative algebraic soft-decision list decoding of Reed-Solomon codes," IEEE Jouranl on selected areas in communications, vol. 24, N0.3,
pp. 481-490, Mar. 2006.

[10] E. R. Berlekamp, "Bit-serial reed-solomon encoders," IEEE Trans. Inform. Theory, vol. IT-28, NO.6, pp. 869-874, Nov. 1982.

[11] D. Chase, "A class of algorithms for decoding blcok codes with channel measurement information," IEEE Trans. Inform. Theory, vol. 18, NO.1, pp. 170-182, 1972.

[12] R. M. Roth and G. Ruckenstein, "Efficient decoding of Reed-Solomon codes beyond half the minimum distance," IEEE Trans. Inform. Theory, vol. 46, NO.1, pp. 246-257, 2000.

[13] F. Parvaresh and A. Vardy, "Multiplicity assignments for algebraic soft-decision of Reed-Solomon codes," Proc. ISIT, p. 205, 2003.

[14] M. El-Khamy and R. J. McEliece, "Interpolation multiplicity assignment algorithms for algebraic soft-decision decoding of Reed-Solomon codes," AMS-DIMACS, vol. 68, Vol.on Algebraic Coding Theory and Information Theory, pp. 99-120, 2005.

[15] V. Guruswami and A. Vardy, "Maximum-likelihood decoding of Reed-Solomon codes is np-hard," IEEE Trans. Inform. Theory, vol. 51, NO.7, pp. 2249-2256, Jul. 2005.