LFSR code is giving wrong result
<p>I have the code for LFSR and getting wrong results, the first 8 bits should be 01110010 but i'm getting 0101111001.</p>

<p>I'm talking about Galois LSFR: en.wikipedia.org/wiki/Linear-feedback_shift_register </p>

<p>Can anyone see what the problem is with this code?</p>

<pre><code>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
</code></pre>

<p>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. </p>

<p>An LFSR of this type can be visualised as a shift register with taps:</p>

<pre><code>pos   0 1 2 3 4 5 6 7
reg   0 0 1 1 1 0 0 1
    ^-  +       + +
</code></pre>

<p>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:</p>

<pre><code>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
</code></pre>

<p>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. </p>

<p>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? </p>

<p>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).</p>

<pre><code>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
</code></pre>

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

python lfsr