灵衢协议学习——物理层（三）

物理层三和物理层四记录针对RS FEC前向纠错编码的学习。一、LFSR等概念先介绍下几个关键概念。以下介绍是最简略的为工程服务的理解不具备学术准确性。1.1、有限域一个被特殊定义的数学域有自己的值域范围0~255,以及特殊的数学计算规则加法运算相当于异或乘法是在二进制域进行可以理解为逻辑与。有线域的幂次数n是可变的n表示二进制比特的位宽。比如0xa0xb ( 1010 异或 1011) 00010xa*0xb 0x45 计算方法如下竖式1.2、多项式在这个领域的多项式类似下面的表达看起来跟正常的多次多项式一致但是它可以表示在有限域中的所有元素。如果是则说明该域中的每个元素都是8bit位宽。比如以下两个元素从多项式视角是这样表达的。x的幂次表示的是bit的位置。1.3、本原多项式本原多项式是LFSRLinear Feedback Shift Register的黄金标准生成多项式。用它构造的LFSR能产生最长周期序列遍历所有非零状态比如下面这个3级LFSR3个寄存器。使用本原多项式能干什么最大的意义就是知道计算结果的位数超出级数时该怎么处理溢出。先来看看本原多项式的根的概念。它其实也跟整数多项式一样是让该式为0的数值。但计算规则不同它是在符合在有限域界乘法和加法规则的前提下让该式为0的数值。因此对于上图中的本原多项式根是指能满足和异或的结果为0的数值。在这个本原多项式的定义下尝试计算的n次方。可以看出用能表示除0之外的所有的数值3bit位宽的二进制。这当然是一个非常特殊的性质。本原多项式用在下面计算时。因为已经超出3bit范围幂次表示位置它表示二进制1000可以直接替换为即010异或001011。还有一种计算方法即如下图采用长除法用除以p(x)取模。1011是本原多项式表示的数值1000是表示的数值。从图中还可以看出。做减法也是异或操作。1.4、 LFSR最早接触线性反馈移位寄存器是在prb23等伪随机码的产生中。如果3级寄存器组成的LFSR按照本原多项式来实现电路则可以产生最长的循环序列。由于二进制000无论怎么异或都只能产生0bit没有办法实现三个寄存器的状态转移所以3级寄存器能产生的最长序列为7。先看下下面这张图它代表了最初我对LFSR电路的认知。即一串的移位寄存器从某些寄存器的输出引出抽头做异或输出接到第一个寄存器的输入这样所有寄存器的状态随着时钟的节拍而不断循环变化。其中以下截图中提到的斐波拉契反馈多项式它直接反映了电路的连接方式。从第3和4个寄存器的输出抽头接入第1个寄存器。正当我觉得掌握了LFSR电路用多项式表示的规律时出现了很多其他形态的表示有的电路从0开始命名。有的说多项式x4只表示最高级是4级并不参与反馈抽头真正参与的是第0级1和第3级x3。我也一度认为图中的x4 x31就是耳熟能详的本原多项式。这就引出了一个问题知道了本原多项式后它对应的LFSR电路是什么样的还是以上文的3级为例。这7个状态就是对应的7个的LFSR的7个状态。也就是LFSR电路进行状态转移时是按照、、、、、、这样的顺序进行转移的。比如T0时刻3个寄存器的状态是表示为多项式为下一时刻T1对应的3个寄存器状态表示为多项式为这样可以立刻看出状态转移的关系即从T0到T1是按照如下方式转换的于是LFSR电路也确定了将第0个和第2个寄存器的输出抽出做异或的结果送入第1个寄存器。当然按照惯例将反馈的输入端命名为0个寄存器就成了普通的LFSR电路的样子。按照上面的方法推导截图图6.2中4级LFSR的电路结构。可以看出电路结构与之不同但是依然可以实现15个状态转移。所以截图图6.2中给出的并非是本原多项式而是所谓的反馈多项式。反馈多项式和本原多项式之间有个互反的关系。