信息与编码理论 第2版 课件 6.3 RS码

§6.3RS码Reed-Solomon码（简称为RS码）是一种特殊的非二进制的BCH码，最早由Reed和Solomon于1960年提出。RS码是可以纠正个错误的进制BCH码，码长为个符号（即表示个二进制位）。在接下来的讨论中，码长用来表示，消息符号的个数用来表示，最小码距用来表示。6.3.1RS码的生成多项式为了设计一个RS码，首先选择一个本原元素，然后分别求出在上的最小多项式，其中，显然这些多项式可以表示为，所以生成多项式为

(6-23)式中，，即是上的一个多项式。便是进制RS码的生成多项式，该码的码长为且对于，因是上的非零元素，故它们都是的根，于是是的一个因式。显然，的码重不会小于该码的最小码距，而，因此由式(6-23)可知的系数都不会是零，于是该码的最小码重等于，即

(6-24)综上可知，RS码是一个进制的BCH码，且最小码距为，其中为正整数，。RS码码字的重量分布式是可以准确计算出来的。例如对于上码长为的RS码，如果最小码距为，则该码码字的重量分布可以用下式来求得：

(6-25)式中。【例6-10】设计一个码长且可以纠正3个错误的RS码，请给出生成多项式。【解】由可得，因此。选取上的一个本原元素，则生成多项式为

在上式的计算过程中用到了表6-6。该码是一个上可以纠3个错误的RS码，码字长度为15，码字中每个元素都是一个进制的符号，于是每个码字等效于60位的二进制比特。最为流行的RS码是上的码其最小码距，从而该码能够纠正16个符号的错误，因此在突发信道中（即错误连续成串发生），该码可以纠正最大长度为比特的突发错误！RS码对于突发错误的纠错能力较强。在突发错误信道中具有特别大的吸引力。6.3.2RS码的系统编码RS码是一种循环码，其系统形式的编码方法与前面的二进制循环码的方法类似，仍可以按照下列步骤来实现：将消息多项式乘上；将除以生成多项式，求得余式；将余式加至，即得码字多项式。【例6-11】设计一个可以纠正2个错误的RS码，请给出消息向量的系统形式编码方案。6.3.2RS码的系统编码【解】由可得。选取上的一个本原元素，则生成多项式为消息多项式为，于是

接下来将除以生成多项式，可得其中商式为，余式为校验多项式。最后可得码字多项式为6.3.3RS码的译码假设某码字在传输过程中发生了个错误，则对应的错误多项式可以表示为

(6-26)式中表示第个错误的错误位置（ErrorLocation），表示第个错误的错误值（ErrorValue），其中。如果码字对应的码字多项式为，则对应的接收多项式为

(6-27)对应的伴随式分别为

(6-28)定义为错误定位数（ErrorLocatorNumber），，则上式可以表示为

(6-29)上式是一个个方程组成的非线性方程组，共有个未知数，其中个位置数，个错误值。显然只要能够求得这个未知数，就可以实现译码，所以任何可以求解上述方程组的方法都是一种RS码的译码算法。Peterson–Gorenstein–Zierler译码算法错误定位数的确定将式(6-30)等号两边乘上，，可得

(6-31)在上式中取，可得

(6-32)显然上式对于均成立，所以可知

(6-33)整理可得

(6-34)再利用式(6-29)中的关系，可知上式中的每一个求和项均是一个伴随式，于是可得

(6-35)显然，只有当时才表示所有已知的伴随式，因此可得如下方程组：

(6-36)式(6-36)是联系系数和伴随式之间的线性方程组，可以将前个等式写成如下的矩阵形式：

(6-37)这样，只要上式中的方阵是非奇异的，便可以解出的所有系数。实际上在译码之前，是不知道发生错误的具体个数的。为了确定该值，可以定义一个如下页所示的伴随式矩阵：(6-38)为了确定的值，译码器依次计算的行列式，直到获得第一个非零值的行列式时停止计算，此时便得到了错误符号个数的值。接下来，将式(6-37)等号左右两边都左乘上的逆矩阵，便可得到的所有系数，进而便能求出的根。可以证明：当恰好等于实际发生的错误符号个数时，矩阵是非奇异的；当时，矩阵均是奇异的。错误值的确定在确定了中的错误位置数之后，为了确定错误值，可以将任意个伴随式的值代入来进行确定。利用错误多项式来纠错在得到错误多项式之后，只需要将其加至接收多项式便可得到码字多项式，即

(6-39)【例6-12】对于上例中可以纠正2个错误（）的RS码，如果发送码字多项式为，并假设传输过程中的错误图样为。请给出接收多项式，并对其进行译码。【解】错误多项式为，于是接收多项式为

与上式对应的伴随式分别为下面来确定错误符号个数。首先计算

接着计算

因此，可知误码个数为1。接着来确定错误位置。由式(6-37)可得

于是，错误定位多项式为上式的根为，错误定位数为，从而可知误码的错误位置为，错误多项式可以表示为下面来求错误值。为了计算错误值，可以将任意一个伴随式的值代入上式，例如

于是，最终可得错误多项式为所以，译码器得到的码字多项式为

又因为该码是系统码，所以该多项式左侧3个系数构成对应的消息向量，即

【例6-13】继续考虑上例，如果传输过程中的错误图样为。请给出接收多项式，并对其进行译码。【解】错误多项式为，于是接收多项式为

与上式对应的伴随式分别为下面来确定错误符号的个数。计算

可知错误符号个数为2。接着来确定错误定位多项式的表达式。易得于是，错误定位多项式为

为了求得上式的根和，可以将中的所有非零元素一一代入进行检验：所以和，从而错误