LFSR代码给出了错误的结果

Question

我有LFSR的代码并得到错误的结果，前8位应该是01110010，但我得到的是0101111001。

我说的是Galois : en.wikipedia.org/wiki/Linear-feedback_shift_register

有人能看到这段代码的问题所在吗？

def lfsr(seed, taps):
  for i in range(10):
      nxt = sum([ seed[x] for x in taps]) % 2
      yield nxt
      seed = ([nxt] + seed)[:max(taps)+1]



for x in lfsr([0,0,1,1,1,0,0,1],[6,5,1]) :
  print x

Answer 1

我对这个问题的回答是：“有人能看到这段代码的问题所在吗？”该代码是可操作的，实现了LFSR (它的类型经常用于在硬件中执行伪随机信号，以及流行的CRC函数的基础)。我只能猜测你为什么认为它不是。

这种类型的LFSR可以可视化为带有抽头的移位寄存器：

pos   0 1 2 3 4 5 6 7
reg   0 0 1 1 1 0 0 1
    ^-  +       + +

每次迭代时，从抽头计算一个值，并将其插入到一端，移动另一个值。在这种情况下，新位变成LSB。让我们运行这个LFSR几个周期：

taps    +       + +
pos   0 1 2 3 4 5 6 7
reg   0 0 1 1 1 0 0 1
c1    0 0 0 1 1 1 0 0
c2    1 0 0 0 1 1 1 0
c3    0 1 0 0 0 1 1 1
c4    1 0 1 0 0 0 1 1
c5    1 1 0 1 0 0 0 1
c6    1 1 1 0 1 0 0 0
c7    1 1 1 1 0 1 0 0
c8    0 1 1 1 1 0 1 0

请注意，我们从c1向下读取了列0中产生的输出位。顺便说一句，位置7不需要存在，因为没有回溯到很久以前的抽头；代码中的片段删除了这样的列。

我已经成功地复制了你所说的值，你可以通过倒转八个周期的输入和输出来获得。你能解释一下你是怎么得出你说的值的吗？

我可以想象得出类似值的一种方法是将另一种方式移到另一种方式，并在一个周期后观察移位寄存器的状态。这需要保持其宽度过去的活动龙头(在CRC使用中并不罕见)。

taps    +       + +  -v
pos   0 1 2 3 4 5 6 7
reg   0 0 1 1 1 0 0 1
c1    0 1 1 1 0 0 1 0
c2    1 1 1 0 0 1 0 0
c3    1 1 0 0 1 0 0 0
c4    1 0 0 1 0 0 0 1

但即便如此，输出仍然是0001010111 (这一次是在第7栏中读到的)。