Upper bound Linear Feedback Shift Register

Question

It is clear that when we have any output stream $x_0,x_1,...$ produced by linear-feedback shift register, then this output has to be periodic.

Now I was wondering if we can find an upper bound for the period of the output sequence from a linear-feedback shift register with $R$ registers over $\mathbb F_q$?

Answer 1

Between them, K.G. and Dilip Sarwate have pretty much answered your question. That is, you can derive an upper bound using the method described by KG:

When the LFSR reaches a state it has been in before, what happens to the output sequence? How many possible states are there? Now you have an upper bound

However, working out how tight this bound is can be much more difficult (as per Dilip's comment):

In general, the period of a polynomial $g(x)$ is the least integer $e$ such that $g(x)$ divides $x^e−1$. If $g(x)$ is the feedback polynomial of an LFSR, then $e$ is the upper bound you seek.

In particular, this is the cycle generated if you initialize the LFSR with all the entries $0$ except for the last one set to $1$.

For a good LFSR, the period will be close to the maximum possible. Consider the tightness of the bounds described by K.G.: if the feedback polynomial is 'badly' chosen (for example $x^k-1$), the period may be much lower.

Since each time you 'step' the LFSR you are multiplying by $x$ within the appropriate field extension, to calculate the period it doesn't matter where on the cycle you start. It does matter that your initial condition is somewhere on this cycle, as for example initializing with the $0$ state leads to a cycle of only $1$ element. Now, if the period is maximal, then every non-zero element must be part of the 'main' cycle, and so any initialization vector will lead to an LFSR of maximal period. However, if the period is lower than this, we must be careful to ensure that the starting vector is indeed on the main cycle.