2
$\begingroup$

Does anyone know a good proof that a LFSR (with XOR feedback and seeded with non-zero starting state) will never enter zero state?

It is obvious that a zero state will always get stuck in a zero state, but what is the proof that nonzero states cannot cycle into the zero state eventually?

$\endgroup$
  • 1
    $\begingroup$ Hint: the LFSR state transition is invertible... $\endgroup$ – poncho Jul 27 '16 at 23:19
2
$\begingroup$

Any linear map (as used in the LFSR next bit computation) gives zero output when loaded by the all zero state, by definition of linearity. So one can never leave the all zero state, which maps onto itself. As @poncho points out the LFSR state mapping is reversible so one can never enter that isolated all zero state from any of the remaining states.

$\endgroup$

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.