RS码编码及译码.docx

4
：RS码的编码和译码算法的实现
：RS码的编码和译码算法的实现
西安电子科技大学学报（自然科学版）
OURNAL OF XIDIAN UNIVERSITY
RS码的编码和译码算法的实现
摘要：RS码是对突发错误
1 +α
1100
α5
α+α2
0110
α6
α2+α3
0011
α7
1+α+α3
1101
α8
1+α2
1010
α9
α+α3
0101
α10
1+α+α2
1110
α11
α+α2+α3
0111
α12
1+α+α2+α3
1111
α13
1+α2+α3
1011
α14
1+α3
1001
3 RS码的编码
RS码的编码与二进制情况类似。令
aX= a0 +a1X+a2 X2+…+ak-1 Xk-1
为需要编码的信息，其中k = n – 2t。在系统码的形式下，2t个奇偶校验符号恰好是X2taX除
以生成多项式得到的余式bX= b0 +b1X+b2 X2+…+b2t-1 X2t-1的系数。在硬件实现中，可以通过图1的除法电路完成。一旦信息aX已经进入信道和电路，则奇偶校验符号就出现在寄存器中[2]。
4
：RS码的编码和译码算法的实现
：RS码的编码和译码算法的实现
西安电子科技大学学报（自然科学版）
OURNAL OF XIDIAN UNIVERSITY
图1 生成多项式为gX= g0 +g1X+g2 X2+…+g2t X2t的q进制RS码的编码电路
编码实现的过程如下，在RS码的运算过程中，所有加减乘除的运算都是定义在伽罗华域上的模2运算。
采集进来的数据，查前面生成的GF(2m)域与二进制数对照表，转化为GF(2m)域上的元素。
编码的过程，当门开启后，k个信息位串行移位进入电路中，同时送入通信信道。一旦消息全部进入到电路中，则寄存器就构成了余式多项式，即为校验位。
关闭门，断开反馈连接。
将校验位移出到信道中。并且与消息位构成了一个完整的码字。
4 RS码的译码
RS码译码的主要目的就是对接收到的可能出错的码字，通过一定的算法设计出原始发送的码字。译码的实现过程比编码复杂的多。RS码的译码算法主要有PGZ算法、BM算法、Forney算法。本文主要讨论BM迭代译码算法。主要的译码步骤分为以下几步。
通过接收多项式r(X)求n-k个伴随式的值。
计算错误位置。求解错误多项式，错误位置多项式的根就是错误位置。
求出错误值，加到对应位置上，完成整个纠错过程。
Berlekamp提出了求解错误位置多项式的迭代算法。错误位置多项式可表示为σX= σ0 +σ1X+σ2 X2+…+σt Xt与错误位置数的关系由牛顿恒等式确定[[] 谢瑞云，樊小琴，[J].(8)
]。这一步是译码过程中最为复杂的一步，在下面的部分将进行介绍。
RS译码过程是一个很复杂的计算过程。在此处给出RS译码的模块图。
C(X)
si
Xi
v
计算伴随式
计算系数矩阵的秩
解方程组
Chien搜索
代入
(1)
纠正错误
r(X)
si
σi
r(X)
Xi