Suppose we use an LFSR, which gives output $x_1x_2x_3\dots$ from some particular initial state. From another state, different from the previous one, using the same LFSR though, it gives sequence $y_1y_2y_3\dots$

Intuitively, some $i$ inequality must be true for $x_i\neq y_i$, but "intuitively" isn't exactly convincing, neither is "empirically."

Is it true that for some $i$ bits, the result will be different, i.e., $x_i\neq y_i$, and if so - why?

  • 1
    $\begingroup$ Hint: in a Fibonnaci LFSR, the bits of the initial state are also the first bits of the output; this makes it easy to prove the result for such LFSR. Then you can use the equivalence of Fibonnaci and Galois LFSRs to prove the result for the other kind. $\endgroup$
    – fgrieu
    Sep 19, 2015 at 16:19
  • $\begingroup$ But of course! Thanks.. it was too close to think about $\endgroup$ Sep 19, 2015 at 16:36


Your Answer

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

Browse other questions tagged or ask your own question.