Hello

i found an article which seems very interesting, however i have some unanswered questions;

" A notable thing about LFSRs is the fact that it can be used to find modulo 2 polynomial division remainders. The LFSR in figure 5-2 represents division by G(x) = x5+x3+x2+1. In table 5-1, the input P=11001110 is sequentially fed into the circuit, with high order terms fed in first. By the end of clock cycle 8, the remainder R(x)=01101 remains in stored in the register's flip-flops."


figure 5-2: a diagram of a LFSR implementing division by polynomial x5+x3+x2+1


Table 5-1: LFSR states for LFSR described in figure 5-2 during division of P=11001110

   
       
       
       
       
       
       

       
   
   
       
       
       
       
       
       
       

   
   
       
       
       
       
       
       
       
   
   

       
       
       
       
       
       
       
   
   
       

       
       
       
       
       
       
   
   
       
       

       
       
       
       
       
   
   
       
       
       

       
       
       
       
   

   
       
       
       
       
       
       
       
   
   

       
       
       
       
       
       
       
   
   
       

       
       
       
       
       
       
   
Clock
Input

x0
x1
x2
x3
x4
0
N/A
0

0
0
0
0
1
1
1
0

0
0
0
2
1
1
1
0

0
0
3
0
0
1
1
0

0
4
0
0
0
1
1
0

5
1
1
0
0
1
1
6
1
0
1

1
1
1
7
1
0
0
0

0
1
8
0
1
0
1
1

0


the full article is in here
http://testbusters.wikispaces.com/Chapter05


However, i am new with this type lfsr  and i always imagined them being drawn like this

figure 5-3: a diagram of a LFSR with tap-sequence [4,1]



and i can't figure out how to count the taps (from where) in figure 5-2.



Secondly,
i would like to know what mathematical explanation would be, ie how lfsr is similar to long binary division (it looks different but same result). Because its used in crc to find remainders, ie it divides.

But how exactly is this possible illudes my mind for the moment.

any kind souls to explain?
Posted on 2010-10-03 04:19:25 by Turnip
Turnip,

That design is Galois LFSRs, they're direct implementation of polynomial (not integer) division.
Posted on 2010-10-04 10:25:25 by baldr
so how do i count taps
Posted on 2010-10-04 13:01:06 by Turnip

so how do i count taps

On 5-2? It's simply the number of feedback XOR gates (three), this is one less than terms in polynomial x5+x3+x2+1 (because term of highest order is implicit).
Posted on 2010-10-05 00:41:33 by baldr