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
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?
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?
Turnip,
That design is Galois LFSRs, they're direct implementation of polynomial (not integer) division.
That design is Galois LFSRs, they're direct implementation of polynomial (not integer) division.
so how do i count taps
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).