目录
线性反馈移位寄存器： (Linear Feedback Shift Register，LFSR)和循环冗余码（Cyclic Redundancy Check，CRC）是微控制器中常用的底层原理。LFSR用于生成伪随机数，后者用于生成检错码。他们的数学原理都是一样的。
异或运算使用符号⊕或者nor表示，真值表如下
F = A ⊕ B
A B F
0 0 0
0 1 1
1 0 1
1 1 0
异或运算可以有3种理解方式：
1 相同得0，不同得1
2 二进制加法，只留模2的余数，抛弃进位（模2加法）
3 二进制减法，大数减小数，不借位（模2减法）
两个二进制数的模2乘法是指在乘法竖式运算中需要做加法的地方都使用异或运算。
模2乘法1010 * 101=100010，下图红框中，1⊕0⊕1=0，没有进位：
两个二进制数的模2除法是指在除法竖式运算中需要做减法的地方都使用异或运算。
模2除法10000 / 101=101余1，下图红框中，0⊕1=1，没有借位：
以斐波那契(外部LFSR)为例，有n个二进制寄存器R0-Rn-1，每个寄存器值为0或1。
f(Rn-1, … R1, R0) = (Rn-1*gn)⊕(Rn-2*gn-1)⊕…⊕(R0*g1)*g0 可以用多项式表示为：
G(x)=gnxn+gn-1xn-1+…+g1x+g0
G(x)称为LFSR的特征多项式。
影响线性反馈寄存器下一个状态的 gi = 0 或1叫做抽头，抽头的设定会决定线性反馈寄存器存储的结果 (Rn-1, … R1, R0) 的变化规律。
通常N位的线性反馈寄存器最多有 2'N 个不同的状态。但是如果出现初值为N个0的情况，线性反馈寄存器陷入死循环，要排除掉。所以N位线性反馈寄存器能产生最长的不重复序列为 2'N-1。
抽头的位置会影响LSFR的最大输出状态的个数
例如：3位的抽头为(g3, g2, g1, g0) = (1, 1, 0, 1)会产生7个状态（多项式对应为：G(x)=x3+x2+1)
若抽头为(g3, g2, g1, g0) = (1, 0, 1, 1)，会产生2个状态（多项式对应为：x3+x+1)。
使最大输出序列长度为2N-1的不可约多项式称为LFSR的本原多项式，本原多项式产生的寄存器序列为M序列。
当N位下，本原多项式不是唯一的。下表为不同的位下的本原多项式：
上图为3阶线性反馈移位寄存器：
抽头为(g3, g2, g1, g0) = (1, 1, 0, 1)
多项式对应为：G(x)=x3+x2+1
线性反馈函数R0 = f(R2, R1, R0) = R1⊕R2
初始值为SEED = (R2, R1, R0) = (1, 0, 1)
3阶线性反馈移位寄存器周期为7：
通过设定seed和抽头，LFSR最多可产生2N-1个序列，这些序列之间看似是随机产生的，之所以称之为伪随机，是因为这些数是通过具体的关系式产生，最终会实现循环。
