企业官网建设流程全解析

二、RS FEC 前向纠错编码学习

2.1、协议内容截取

2.2、纠错方案简述

关于本RS FEC前向纠错方案有几个重点关注点需要先提出。

●工作在，即每个消息符号都是8bit位宽。

●RS(N,K,T)表示接收K个消息符号,对其进行编码输出N个消息，接收端能对K个消息中的T个进行纠错。在本协议定义下，N=120,K=128,T=4。

●编码电路对应的生成多项式如下，即从这255个根中挑选前8个即按照下式连乘。十进制分别为：1,2,4,8，……，128。

计算连乘(x-1)(x-2)……(x-128)得到各次幂的系数~。

●校验多项式，也就是8个校验字符是怎么得到的呢？——是用消息多项式吗m(x)除以生成多项式g(x)取余数。消息多项式的定义如下，多项式的系数~是消息字符。代表编码器接收到的K（120）个消息字符。x的幂次表示字符的位置。按照文档的定义，字符先到，后到。在第8次幂对应的位置上，剩下的第7到0是校验字符。

为何要这样设计校验多项式呢？看下式，发送端最终发送的128个字符用如下多项式来表达。G(x)就是上面提到的生成多项式g(x)，它在这8个点上是0值，即G()~G()=0。P(x)是余数，即8个校验字符。两个P(x)进行异或等于0。即发送的128个字符组成的多项式C(x)在这8个点上也应该为0。当接收端接收了128个字符后（接收字符多项式命名为R(x)），计算R()~R()的数值都应等于0。如果不为0，说明128个字符中有错误，需要通过纠错算法找出错误字符的位置以及错误的数值（正确和错误的差值）。

截图中的图3-4是编码器电路——伽罗瓦LFSR。消息字符率先进入此电路，与寄存器的输出做异或后再与做乘法，将结果反馈至各级寄存器。图中涉及到乘法时，结果若超出8bit溢出，则需除本原多项式取余数。这就是本原多项式存在的意义——规定如何处理溢出回绕。当运行128拍后，~这8个寄存器中存储的就是m(x) 模除 g(x)的余数，即校验字符。这个RS FEC编码电路本质上就是实现有限域中的长除法。

这个设计很巧妙，我简单计算了下，发现确实符合长除法的结果，其实长除法就是试商-乘法-异或。这个编码电路也是一样的，只是参与异或的数值的顺序跟长除法不同。结果是一致的。说明一下，乘以反馈值直接赋值给，没有与前一级寄存器的输出做异或。

（注：下图第一行qX g0错算成了5，应是10，刚好长除法那里也算错了，结果反而一致。）

2.3、纠错原理介绍

接收端收到128个字符，所有的字符包括校验字符都有损坏的可能，根据RS FEC的设计，有8个校验字符，可以校正最多4个错误。

思路如下：

如果128个字符都是正确的，根据发送字符的这个设计，接收端在8个根处的数值为0。接收多项式用R(x)表示。当R()=0, R()=0,……R()=0，说明无错误，直接输出前120个消息字符。

当发生了错误，也就是128个字符的某些位置的字符出现了错误，用以下方式校错。

以下符号称为伴随式。它实际就是将本原元的8个根代入接收多项式求值的结果。这个结果的意义是什么呢，是正确的结果和错误结果的差值。

假设正确的多项式是：

接收到的错误的多项式是：

正确的多项式在“根”处为0：

错误多项式带入根计算后得到伴随式，可以看出正确的消息项都被消失了，只剩下错误的那一项（假设只有一个错误时）以及错误系数和正确系数的异或值：

通过伴随式的系数和接受到的同一位置的项对应的系数做异或就可以校正错误了。

通过以上例子可知，计算伴随式得到的是错误的那些项的和（异或和）。有n个错误，便会出现n个项，项的幂次表示错误的位置，项的系数是正确和错误的字符数值的异或。

通过伴随式的系数和接受到的同一位置的项对应的系数做异或就可以校正错误了。

通过以上例子可知，计算伴随式得到的是错误的那些项的和（异或和）。有n个错误，便会出现n个项，项的幂次表示错误的位置，项的系数是正确和错误的字符数值的异或。

当有1个错误时：

数学上建模倒是很容易，但是实际上真要做校正求解却没那么容易。

此时只在一个位置有错误，设这个位置是。则计算时由于所有幂次的计算项都为1，结果只剩下常数项。（第二次阅读时，疑惑如果按照上面的示例，常数项不就是1吗，不是这样的，因为真正接收到的R(x)的常数项是余数项，它一般都不会是1，而是一个0~255的数值，这样下式的符号e仍是正确常数和错误常数的异或值）即：

计算时，抵消正确的项后只能剩下错误的第项。错误的数值仍然是。

以上两式，只有和两个未知数（和是计算伴随式得到的，是二进制 10）,以下和是示例数字。按照下面的方法就可以求出位置。求系数的方法就不赘述了。

当有2个错误时：

可以列出如下4个方程。未知数有4个。但是位置在指数上，所以下面的4元3次方程，用4个方程式无法求解。目前采用的方法如下，即先解出，再解求其两个根。当然是不能用二元一次方程来求解的，需要将共128个数值依次带入该方程，若为0便是方程的根。我认为数学上应有不少证明，证明根存在且唯2。

当有4个错误时，方法同上，也是利用根之间的线性推导关系。

在实际中，事先并不知道有几个错误，所以会采用一步一步猜的方法，先假设1个错误，计算出下图中的，即。再估计，看估计值和实际值是否一致，若全都一致，则说明确实只有这一个错误，否则试验有两个错误。

实验T=2时，使用来估计，同理估计，看是否一致。

T=3与T=2的操作类似。

但是T=4没有可供其进行验证的伴随式，需要将使用校正后的128个字符数值再计算R()，R(),……R()并判断是否为0。若不为0，则说明错误数大于4。

2.4、纠错实现

纠错原理其实说简单也不简单，但看起来挺复杂的是第一步，计算8个伴随式。这个操作过分复杂基本上不可实现。

可以操作的是，将R(x)这128个字符再次送入RS FEC电路，实施除以生成多项式的长除法，如果没有错误的话，经过128拍，8个寄存器中的数值应为0。如果有错误，那8个寄存器中的数值就是余数。

长除法后的余数和伴随多项式的关系，需要这样思考。长除法后的余数，一定是一个最高次为7的多项式。如下面推导可以得到，因为生成多项式在“根”处的值为0，所以：

看到这步可能会惊讶，似乎看起来余数就是伴随式。但其实不一样，因为计算得到了一个数值，但是8个x次幂的多项式的线性组合，寄存器中的余数就是这些多项式的系数。

如何从余数得到伴随式也有不少方法，先不在这里记录。