1
$\begingroup$

It's clear that an LFSR has finite states and eventually will end up with repeating cycle. However, is it possible for an LFSR to have more than one repeating cycle? For example, with initial state $A$, its goes to cycle $C_a$, and for initial state $B$, it ends up with cycle $C_b$.

$\endgroup$
  • 1
    $\begingroup$ All already have, cycle with all 0...0 and others. If the defining polynomial is not primitive, then there will be different cycles. Have a link too. $\endgroup$ – kelalaka Jan 11 at 19:37
  • 1
    $\begingroup$ And see this Non primitive lfsr sequence $\endgroup$ – kelalaka Jan 11 at 19:50
  • $\begingroup$ It is if you don't mind a counter and some other hardware. The state $C_a = B$ in that condition $\endgroup$ – b degnan Jan 11 at 20:07
  • $\begingroup$ en.wikipedia.org/wiki/… note that non-maximal implies there are other cycles $\endgroup$ – bmm6o Jan 22 at 5:27
2
$\begingroup$

As the question is if the LFSR can have more than one repeating cycle, the answer is it can as long as you change the math. To do so, you'll need to tweak the hardware. I present two polynomials

$$P_0=x^3 + x^1 +1\\P_1=x^3 + x^2 +1$$

that are implemented in a switchable circuit that is dependent on the counter with overflow. The polynomials are 3rd degree, so you would overflow on 7, which is the select signal. In both cases, the initial condition is $1,0,0$.


The logic states are as follows:

\begin{array} {|l|l|} \hline count & select & s_2 & s_1 & s_0 \\ \hline 0 & 0 & 1 & 0 & 0 \\ \hline 1 & 0 & 0 & 0 & 1 \\ \hline 2 & 0 & 0 & 1 & 1 \\ \hline 3 & 0 & 1 & 1 & 1 \\ \hline 4 & 0 & 1 & 1 & 0 \\ \hline 5 & 0 & 1 & 0 & 1 \\ \hline 6 & 0 & 0 & 1 & 0 \\ \hline \hline 0 & 1 & 1 & 0 & 0 \\ \hline 1 & 1 & 0 & 0 & 1 \\ \hline 2 & 1 & 0 & 1 & 0 \\ \hline 3 & 1 & 1 & 0 & 1 \\ \hline 4 & 1 & 0 & 1 & 1 \\ \hline 5 & 1 & 1 & 1 & 1 \\ \hline 6 & 1 & 0 & 1 & 1 \\ \hline \end{array}

note: I picked these two polynomials and the initial condition because they wrap back to $1,0,0$, for the same initial condition. If you use the initial condition of $111$ you will get 4 iterations before you return to the same cycle. However, you should check my math on that.

$\endgroup$
  • 2
    $\begingroup$ This is not an LFSR. Note that the L in LFSR stands for linear, and the feedback is not linear. $\endgroup$ – Dilip Sarwate Jan 12 at 17:12
  • $\begingroup$ What 2 different cycles are you suggesting this "LFSR" has? $\endgroup$ – bmm6o Jan 13 at 17:46
1
$\begingroup$

There is a very nice recent paper available here by Chang, Ezermann, Ling and Wang, which has addressed this problem for arbitrary alphabet $\mathbb{F}_q$ and arbitrary characteristic polynomials, including those with divisors that are powers of irreducible polynomials.

Let $\Omega(f)$ be the set of sequences satisfying $f$ as their characteristic polynomial.

This paper determines the cycle structure of $\Omega(f)$ fully for an arbitrary $f$ and gives a method to identify a state from each distinct cycle in $\Omega(f)$, a longstanding open problem.

$\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.