XOR LFSR and all zero state

Question

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?

Answer 1

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).

[image credit]

Proof that it works for a LFSR in Fibonacci 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 Fibonacci 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 Fibonacci and Galois forms of LFSRs with the same polynomial (perhaps within reflection, depending on convention for Fibonacci) 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.