0

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

我说的是伽罗瓦 LSFR：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
4

1 回答 1

2

My answer to the question posted, "Can anyone see what the problem is with this code?", is no. The code is operational, implementing an LFSR (of the type frequently used to do pseudorandom signals in hardware, and the basis for popular CRC functions). I'm left to guess at why you think it isn't.

An LFSR of this type can be visualised as a shift register with taps:

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

Each iteration, one value is calculated from the taps and inserted on one end, shifting the other values. In this case, the new bit becomes LSB. So let's run this LFSR a few cycles:

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

Note that we read the output bits yielded in column 0, from c1 down. Incidentally, position 7 doesn't need to exist, because there are no taps that far back; the slice in the code removes such columns.

I've managed to reproduce the value you say you're getting by reversing the inputs and output of eight cycles. Can you explain how you arrive at the value you say it should be?

One way I can imagine arriving at a similar value is by shifting the other way and observing the shift register's state after one cycle. This requires maintaining its width past active taps (not unusual in CRC use).

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

But even so the output is 0001010111 (this time read in column 7).

于 2016-10-10T19:35:55.143 回答