LFSR(Linear Feedback Shift Register)结构分析

1 前言

这篇文章看起来公式很多，不要担心，写公式只是为了更清晰的表达，并没有什么复杂的数学。只有有耐心， 基本没什么困难。

2 理论回顾

在大学电路学习中我们学到过一个定理：互易定理，是指将二端口网络的输入和特定输出互换位置后，输出不因这种换位而有所改变。 这个定理扩展之后，可以应用到数字电路中，说明如下：

对于一个线性系统：

1. 将数字电路用信号流图描述出来，满足如下限制(加粗的重点名词是作者自己取的，若和权威不匹配，请自行处理)
   1. 信号汇集点： 仅有一个流出路径，一个或多个流入路径，流出值等于所有流入值的和。
   2. 信号发散点： 仅有一个流入路径，一个或多个流出路径，各个流出值都相等，等于流入值。
   3. 每个节点要么是信号汇集点，要么是信号发散点，不允许同时有多个流入和多个流出。
   4. 对于不满足上述条件的信号流图，通过适当变换也可以满足上述条件。
2. 如果将原信号流图同时经过如下修改，则输入输出的传递函数不会改变
3. 输入输出交换，
4. 信号流方向取反，取反之后， 信号汇集点就变成了信号发散点， 信号发散点变成了信号汇集点。

3 LFSR 结构实例分析说明

结合如下图形进行说明：($Z^{-1}$代表一级延时，用D触发器来实现)

图1是Galois结构实现的LFSR，其中：

• 红色节点A是 信号发散点, a=b=c (a,b的值复制c的值）
• 红色节点B是 信号汇集点, e=d+b (e取值为b和d的相加)

图2是将图1进行如下动作之后得到的结构：

1. 输入输出交换

2. 信号流方向取反

进行上述变换之后，原来的汇集点B变成了发散点，原来的发散点A变成了汇集点。

将图2进行水平镜像，得到图3，就是Fibonacci结构。Fibonacci 结构的特点是最低位的输入是由某些高位进行相加(异或) 之后得到。其余的 bit 形成移位寄存器。

如果将输入X固定为0，对寄存器选择非0的初始值，以及合适的反馈系数， 这两种结构就可以用来产生伪随机数。其中Galois结构，由于关键路径只有一个加法（异或），因此常常用在数字电路设计中。 在这里，是为了证明这两种方法的等效性，加深电路设计的理解。

4 Galois结构的原理说明

下面简单分析Galois结构:

以图1为例，输入永远为0，每一个延时单元保存1bit的值，加法是异或运算。 电路实现上，延时单元就是一个D触发器，每个时钟，运算一次。

初始条件下，3个延迟单元的值为$ (r_0，r_1，r_2)$, 可以将图1的3个延时单元用多项式来表示如下：

$P(0)=r_0+r_1X+r_2X^2$

经过一个时钟，不考虑反馈，移位的动作相当于乘以X，不考虑 X3 次项，得到:

$P(1)=XP(0)$

现在来考虑移位之后的$ X^3$ 次项，

• 当$r_2=0$时, $X^3$ 项为0， 反馈系数全部为0，所以 P(1)=XP(0) 成立。
• 当$r_2=1$时, $X^3$ 项为1，反馈系数为1， 需要在移位之后加上反馈的效应。反馈的动作相当于一个加法, 分析得到：

$P(1)=XP(0)-X^3+X+1$

由于是加法是模2加法，所以加法和减法等价。于是得到

$P(1)=XP(0)-(X^3+X+1)$

• 综合这两种情况， P(1) 相当于 $XP(0)$ 对$ (X^3+X+1)$ 进行除法求余数。扩展到 P(n) 的情形， n代表时钟计数编号.

$P(n)=XP(n-1) mod (X^3+X+1)$

$P(n)=X^iP(n-i) mod (X^3+X+1)$

• 由上述公式，假如初始值$ P(0)=1(r_0=1，r_1=0，r_2=0)$则:

任意一个多项式对$ X^3+X+1$ 求余数，余数可能为 $R=s_0+s_1X+s_2X^2$. $s_i(i=0,1,2)$ 取值为0或者1， 因此 R 共有$2^3=8$种可能性。 直接观察，$X^n\ mod\ (X^3+X+1)$, 其结果不可能为0。因此 P(i) 的取值最多只有7种。 根据抽象代数的域论知识，因为$(X^3+X+1)$ 是本原多项式，所以 P(i) 结果会遍历这7种可能性。

• 所以，图1/2/3的结构，当初始值为非0的时候，会产生周期为7的序列。通过 $X^8 \ mod\ (X^3+X+1)=1$ 亦可证明。 这部分结论可以推广到更高阶的LFSR电路中， 可以作为随机数产生器，也可以作为固定长度的计数器。