# Number of states in a LFSR

Do all $2^{\ell}$ (where $\ell$ is the bit length of the shift register) states always occur in a LFSR or can I choose my taps badly so some states are skipped and the period is shortened?

If so is there a way to prove the number of states that can occur in a LFSR?

-
Found some info that you might find interesting: cryogenius.com/software/lfsr –  mikeazo Dec 13 '12 at 14:05

As fgrieu points out, the number of states reached is at most $2^\ell-1$ and that is achieved only if the feedback polynomial is a primitive polynomial (and the initial state is not all zero). If the feedback polynomial is irreducible but not primitive, then with nonzero initial loading, the LFSR state will cycle through $N$ states, where $N$ is a divisor of $2^\ell-1$ but not a divisor of $2^m-1$ for any $m$ that is itself a proper divisor of $\ell$. For example, if the feedback polynomial is an irreducible but nonprimitive polynomial of degree $6$, then, depending on which polynomial is being considered, the LFSR will cycle through $21$ states, or through $9$ states. The $63$ nonzero states form $3$ cycles of $21$ states each, or $7$ cycles of $9$ states each. Depending on the initial loading, the LFSR will cycle through one of these cycles (and the other cycles will never occur).

For an arbitrary feedback polynomial, which could be reducible, that is, factorable into a product of (not necessarily distinct) irreducible polynomials (meaning something like $[f(x)]^2g(x)$ might be the factorization), the answer is much messier and complicated to describe. Search for the term period of a polynomial and read Lidl and Neiderriter's Finite Fields or Chapter 6 of Berlekamp's Algebraic Coding Theory for some of the details.

-

Read chapter 6 of the HAC.

It will tell you that no, the $2^ℓ$ states are never reached, at most $2^ℓ-1$ are. And that occurs for taps chosen per a primitive polynomial, and initial state not all zero.

For lists of primitive polynomials, I use jj's useful and ugly page of mathematical data.

-