里德所羅門系統碼的Guruswami-Sudan解碼:複雜度比較

Abstract

這篇論文是關於使用Guruswami-Sudan 演算法解里德所羅門碼，其中包含Kötter 和 Roth-Ruckenstein 的改善，主要分為插值和分解兩部份。在Guruswami-Sudan 演算法中可以比Berlekamp-Massey 演算法更正更多的錯誤。藉由挑選插值的重根數，GS 解碼端最後會回傳包含所有漢明距離小於tm 的所有訊號的列表，其中解碼半徑tm 是插值重根數的一個函式。最後，我們使用其他方法去執行插值的部分並比較複雜度。

This thesis is about the Guruswami-Sudan decoding algorithm of Reed-Solomon code, including the Kötter and Roth-Ruckenstein improvements, and containing two main parts, Interpolation and Factorization. In Guruswam-Sudan algorithm, it can correct more errors than other decoding by Berlekamp-Massey algorithm. By choosing the interpolation multiplicity m , the GS decoder finally returns the list which includes all codewords with Hamming distance tm, where the decoding radius tm is a function of interpolation multiplicity. Finally, we use another method to process the interpolation part and compare the complexity.