【电子技术】什么是LFSR？

大家好，欢迎来到IT知识分享网。

目录

0 前言

1 数学基础

1.1 逻辑异或

1.2 模2乘法 和 模2除法

 2 线性反馈移位寄存器LFSR

3  抽头和特征多项式

 4  阶线性反馈移位寄存器实例

0 前言

线性反馈移位寄存器： (Linear Feedback Shift Register，LFSR)和循环冗余码（Cyclic Redundancy Check，CRC）是微控制器中常用的底层原理。LFSR用于生成伪随机数，后者用于生成检错码。他们的数学原理都是一样的。

1 数学基础

1.1 逻辑异或

1 相同得0，不同得1

2 二进制加法，只留模2的余数，抛弃进位（模2加法）

1.2 模2乘法 和 模2除法

两个二进制数的模2乘法是指在乘法竖式运算中需要做加法的地方都使用异或运算。

模2乘法1010 * 101=，下图红框中，1⊕0⊕1=0，没有进位：

两个二进制数的模2除法是指在除法竖式运算中需要做减法的地方都使用异或运算。

模2除法10000 / 101=101余1，下图红框中，0⊕1=1，没有借位：

 2 线性反馈移位寄存器LFSR

以斐波那契(外部LFSR)为例，有n个二进制寄存器R0-Rn-1，每个寄存器值为0或1。

3  抽头和特征多项式

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。

使最大输出序列长度为2N-1的不可约多项式称为LFSR的本原多项式，本原多项式产生的寄存器序列为M序列。

 4  阶线性反馈移位寄存器实例

通过设定seed和抽头，LFSR最多可产生2N-1个序列，这些序列之间看似是随机产生的，之所以称之为伪随机，是因为这些数是通过具体的关系式产生，最终会实现循环。