1
$\begingroup$

I read this in a description of Linear Shift Feedback Registers

Note that the allzero state must be excluded. If an LFSR assumes this state, it will get “stuck” in it, i.e., it will never be able to leave it again".

I can understand why an all zero state means that if the LFSR comes to an all zero state, it gets stuck in the state. However, how does one prevent it from getting to an all zero state? Can an LFSR never get into an all zero state unless it's initialized to an all-zero state? If it cannot, is there any proof for this?

$\endgroup$
3
$\begingroup$

how does one prevent a LFSR from getting to an all zero state?

One method is to not initialize the LFSR to the all-zero state, and use a feedback polynomial with a constant term (the $1$ in the polynomial).

Fibonnaci LFSR [image credit]

Proof that it works for a LFSR in Fibonnaci form, as illustrated with polynomial $x^{16}+x^5+x^3+x^2+1$ in the above picture, by induction: if the current state of an $n$-bit LFSR is non-zero, and there is a constant term (the $1$ in the polynomial, equivalently a XOR tap on the rightmost bit), then the next state is non zero, by considering the two cases:

  • If any of the $n-1$ left bits is non-zero, then this bit is carried to the next state, which thus is non-zero.
  • Otherwise, the $n-1$ left bits are zero and the rightmost bit is one. This bit enters the XOR, and all other bits entering the XOR are zero, hence the next left bit is a one, hence the next state is non-zero.

For LFSRs in Galois form, we can invoke the equivalence with the Fibonnaci form, or make a direct proof, as follows. If the LFSR's feedback polynomial is $P(x)$ and it's state $S(x)$, the next state is defined to be $\big(x\cdot S(x)\big)\bmod P(x)$. Since the degree of $S(x)$ is at most one less than the degree of $P$, the next state can be all-zero only if one of the following holds

  • $x\cdot S(x)=0$, implying that $S(x)=0$
  • $x\cdot S(x)=P(x)$, which can't be if $P(x)$ has a constant term.

Note: The condition "feedback polynomial has a constant term" is so common in practice that it is sometime part of the definition of LFSRs. When it holds, it can be shown that Fibonnaci and Galois forms of LFSRs with the same polynomial (perhaps within reflection, depending on convention for Fibonnaci) are equivalent, in the sense that the sequence produced by one for a given initial state is the same as the sequence produced by the other for a (different) initial state. There is no other common form or kind of binary LFSRs.


Some hardware constructions want to recover from a fault (invalid setting, "upset" such as a power glitch or a cosmic ray) and have special circuitry to leave the all-zero state if it gets entered. That can be a NAND gate on all the state bits forcing a one to enter the LFSR. Or a counter clocked with the LFSR, reset when the LFSR output is a one, with the counter's high-order bit forcing a one to enter the LFSR.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you - this seems to be proof for specific LFSRs. Does that mean that this property doesn't hold good for all LFSRs? $\endgroup$ – user93353 Sep 3 at 9:31
  • $\begingroup$ What do you mean by specific LFSR. An LFSR is LFSR, either it can attain a maximal period, called $m$-sequences, or not. If attains the maximal period, the above is fine. If not, then you are not using an LFSR correctly, like you are not taking the last stage into feedback calculation. Than those stages can all be one, however, the LFSR can be diverge to all zero state. In this case you need to be careful about the feedback polynomial.. $\endgroup$ – kelalaka Sep 3 at 9:40
  • $\begingroup$ @kelalaka - by specific LFSR, I mean that his answer is relevant to a Fibonacci LFSR & Galois. How do you extend it to show that the property will be true for any LFSR $\endgroup$ – user93353 Sep 3 at 9:46
  • $\begingroup$ @user93353 can you define another LFSR? and Fgriue said: "For Galois LFSRs, we can invoke the equivalence with Fibonnaci LFSR: $\endgroup$ – kelalaka Sep 3 at 9:47
  • $\begingroup$ @kelalaka - I am sure you are right. But I don't get it. Anyway, leave it. I will wait for some else to answer in terms I can understand $\endgroup$ – user93353 Sep 3 at 9:49

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.