二、RS FEC 前向纠错编码学习2.1、协议内容截取2.2、纠错方案简述关于本RS FEC前向纠错方案有几个重点关注点需要先提出。●工作在即每个消息符号都是8bit位宽。●RS(N,K,T)表示接收K个消息符号,对其进行编码输出N个消息接收端能对K个消息中的T个进行纠错。在本协议定义下N120,K128,T4。●编码电路对应的生成多项式如下即从这255个根中挑选前8个即按照下式连乘。十进制分别为1,2,4,8……128。计算连乘(x-1)(x-2)……(x-128)得到各次幂的系数~。●校验多项式也就是8个校验字符是怎么得到的呢——是用消息多项式吗m(x)除以生成多项式g(x)取余数。消息多项式的定义如下多项式的系数~是消息字符。代表编码器接收到的K120个消息字符。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个错误计算出下图中的即。再估计看估计值和实际值是否一致若全都一致则说明确实只有这一个错误否则试验有两个错误。实验T2时使用来估计同理估计看是否一致。T3与T2的操作类似。但是T4没有可供其进行验证的伴随式需要将使用校正后的128个字符数值再计算R()R(),……R()并判断是否为0。若不为0则说明错误数大于4。2.4、纠错实现纠错原理其实说简单也不简单但看起来挺复杂的是第一步计算8个伴随式。这个操作过分复杂基本上不可实现。可以操作的是将R(x)这128个字符再次送入RS FEC电路实施除以生成多项式的长除法如果没有错误的话经过128拍8个寄存器中的数值应为0。如果有错误那8个寄存器中的数值就是余数。长除法后的余数和伴随多项式的关系需要这样思考。长除法后的余数一定是一个最高次为7的多项式。如下面推导可以得到因为生成多项式在“根”处的值为0所以看到这步可能会惊讶似乎看起来余数就是伴随式。但其实不一样因为计算得到了一个数值但是8个x次幂的多项式的线性组合寄存器中的余数就是这些多项式的系数。如何从余数得到伴随式也有不少方法先不在这里记录。