XOR LFSR与全零状态

Question

我在线性移位反馈寄存器的描述中读到了这个

请注意，必须排除所有零状态。如果LFSR假定了这种状态，它就会被“卡住”，也就是说，它再也不能离开它了。

我能理解为什么一个全零状态意味着如果LFSR进入一个全零状态，它就会被困在状态中。然而，如何防止它进入全零状态呢？除非将LFSR初始化为全零状态，否则它永远不会进入全零状态吗？如果不能，有证据证明吗？

Answer 1

如何防止LFSR进入全零状态？

一种方法是不将LFSR初始化到全零状态，而使用一个具有常数项的反馈多项式(多项式中的1 )。

[形象信用]

通过归纳，证明它适用于Fibonacci型中的LFSR，如上面图片中的多项式x^{16}+x^5+x^3+x^2+1所示:如果n-bit LFSR的当前状态为非零，并且存在一个常数项(多项式中的1，等效为最右边位的XOR点击)，则通过考虑以下两种情况，下一个状态为非零：

• 如果任何一个n-1左位是非零的，那么这个位被携带到下一个状态，因此它是非零的。
• 否则，n-1左位为零，最右位为1。此位进入XOR，而所有进入XOR的其他位都为零，因此下一个左位为1，因此下一个状态为非零。

对于Galois型中的LFSR，我们可以调用与Fibonacci形式的等价，或者进行直接证明，如下所示。如果LFSR的反馈多项式为P(x)，且状态为S(x)，则定义下一个状态为\big(x\cdot S(x)\big)\bmod P(x)。由于S(x)的度最多比P的度小1，所以下一个状态只能在下列任一状态保持不变时为全零。

• x\cdot S(x)=0，暗示S(x)=0
• x\cdot S(x)=P(x)，如果P(x)有一个常量项的话，就不可能了。

注：“反馈多项式有一个常数项”的条件在实践中非常普遍，有时它是LFSRs定义的一部分。当它成立时，可以证明具有相同多项式的Fibonacci和Galois形式的LFSRs (可能在反射内，取决于Fibonacci的约定)是等价的，即一个给定初始状态产生的序列与另一个初始状态产生的序列相同。没有其他常见形式或种类的二进制LFSR。

一些硬件结构希望从故障中恢复(无效设置，“扰乱”，如电源故障或宇宙线)，并具有特殊的电路，以便在进入时保持全零状态。这可以是所有状态位上的NAND门，迫使一个人进入LFSR。或者一个计数器与LFSR时钟，当LFSR输出是一个计数器时重置，该计数器的高阶位迫使一个计数器进入LFSR。