论文部分内容阅读
在计算机信息的传递过程中,难免会受到各种噪音的干扰,使得信息改变,为了纠正这种差错,我们采用了编码理论,使用纠错码来更正。目前最常用的纠错码是Reed-Solomon编码,本文研究了其设计特点,并根据情况,设计和选择了实现方案,并编写了相应程序;对于常规RS编码的译码过程做了一般的理论分析,介绍实现了传统的Berlekamp-Massey译码算法,它是基于Reed Solomon码的Hamming距离d的译码算法,其纠错能力局限于经典的纠错能力t0=[(n-k)/2]之内;为了突破传统纠错局限,我们进一步引入了Guruswami-Sudan译码算法,其纠错能力为n-1-[√(k-1)n]超过了传统界限,它主要对应于RS编码的根的生成矩阵形式,将译码过程主要分为了对于给定点列{(xi,yi)}ni=1的插值问题,以及求给定的二元多项式Q(x,y)的形如y=f(x)的根的分解问题,本文中给出了相应的方法和实现。