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

物理层（三）和物理层（四）记录针对RS FEC前向纠错编码的学习。

一、LFSR等概念

先介绍下几个关键概念。

以下介绍是最简略的为工程服务的理解，不具备学术准确性。

1.1、有限域

一个被特殊定义的数学域，有自己的值域范围0~255,以及特殊的数学计算规则，加法运算相当于异或，乘法是在二进制域进行，可以理解为逻辑与。有线域的幂次数n是可变的，n表示二进制比特的位宽。

比如0xa+0xb =( 1010 异或 1011) = 0001

0xa*0xb = 0x45 计算方法如下竖式：

1.2、多项式

在这个领域的多项式，类似下面的表达，看起来跟正常的多次多项式一致，但是它可以表示在有限域中的所有元素。如果是，则说明该域中的每个元素都是8bit位宽。比如以下两个元素，从多项式视角是这样表达的。x的幂次表示的是bit的位置。

1.3、本原多项式

本原多项式是LFSR（Linear Feedback Shift Register）的"黄金标准"生成多项式。用它构造的LFSR能产生最长周期序列（遍历所有非零状态），比如下面这个3级LFSR（3个寄存器）。使用本原多项式能干什么，最大的意义就是知道计算结果的位数超出级数时，该怎么处理溢出。

先来看看本原多项式的根的概念。它其实也跟整数多项式一样，是让该式为0的数值。但计算规则不同，它是在符合在有限域界乘法和加法规则的前提下，让该式为0的数值。

因此，对于上图中的本原多项式，根是指能满足和异或的结果为0的数值。

在这个本原多项式的定义下，尝试计算的n次方。可以看出用能表示除0之外的所有的数值（3bit位宽的二进制）。这当然是一个非常特殊的性质。本原多项式用在下面计算时。因为已经超出3bit范围（幂次表示位置，它表示二进制1000），可以直接替换为，即010异或001=011。

还有一种计算方法，即如下图，采用长除法，用除以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+ x3+1就是耳熟能详的本原多项式。

这就引出了一个问题：知道了本原多项式后，它对应的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）中给出的并非是本原多项式，而是所谓的反馈多项式。反馈多项式和本原多项式之间有个互反的关系。