1
$\begingroup$

Suppose recursion for output of Galois LFSR is $u_1=u_3=u_4=0$

What kind of taps are here, and initial state? How to uncover this information?

$\endgroup$
2
$\begingroup$

In general, you're missing both the polynomial (taps) and some symbols, so there is no unique solution.

The LFSR is determined by its generating polynomial and thus its degree/length/taps. If the LFSR is 5 bits or more in length you're out of luck, you need 5 equations so 5 bits of information for any hope of solving this.

If it is 4 bits long, and primitive, you're in general out of luck again in the absence of any extra information, since all loadings, and in particular both states $$(s_1,s_2,s_3,s_4)=(0,s_2,0,0)$$ with $s_2$ arbitrary are possible.

However, if $s_2=0$ this will give a trivial LFSR of all zero output, so if you're not in this setting you can assign $s_2=1$ and proceed, if the LFSR is 4 bits long. Then you might try all possible primitive LFSRs (there are 2 of length 4) and have 2 candidates.

If it is 3 bits or less, again, if the all zero state can be ruled out, you can proceed by trying all primitive LFSRs and in fact now you have 4 bits of info (4 symbols after ruling out all zero state) for a $L=3$ so you should be able to determine the LFSR uniquely if it is primitive (there are 2 here).

$\endgroup$
1
  • $\begingroup$ Suppose any $s_2$ works. Ive been thinking, if initial configuration is, lets say $1,0,0,0,0,0$, and tap is to 5h bit (0 which is after 1 in initial state) It should produce 4 consequtive zeroes, and given any $s_2$ works, should correspond to initial requirement $u_1=u_3=u_4$ Do I miss anything? $\endgroup$ Sep 4 '15 at 5:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.