2
$\begingroup$

everywhere I've searched it says that the minimal period of an LFSR given by a characteristic polynomial $c(x)$ is the least number $r \in \mathbb{N}$ that: $$c(x)|(x^r-1)$$ but how do I prove it's correctness? I've tried o prove it like that: given $c(x)$ the characteristic polynomial and $h(x)$ theinitial state polynomial, I'll denote the minimal period with $\pi$ then: $$ {h(x) \over c(x)}=G(x)= \sum^\infty_{k=0}a_kx^k=\sum^{\pi -1}_{k=0}a_kx^k(1+x^\pi+x^{2\pi}...)={\sum^{\pi -1}_{k=0}a_kx^k \over 1-x^\pi} $$ and I'm not sure where to go from here

$\endgroup$
  • $\begingroup$ What have you tried? Note that the answer is already covered by my answer to cs.stackexchange.com/q/49482/755, so this is effectively already answered by that question (I derive the answer to this question in my answer over there), but you said you didn't understand that answer. So, please tell us in the question what you have tried and what you do understand, to make clear your expectations about what level of an answer you're looking for, so people can know what kind of answer will be useful to you. Do you know group theory? finite fields? modular arithmetic? $\endgroup$ – D.W. Nov 18 '15 at 2:22
  • $\begingroup$ See also cs.stackexchange.com/q/43707/755 for a related topic. $\endgroup$ – D.W. Nov 18 '15 at 2:24
1
$\begingroup$

Hint: The LFSR changes its state by multiplying it by $x$ modulo $c(x)$. So if the initial state is $x_0$, the state after $t$ steps is $x_t \equiv x_0 x^t \pmod{c(x)}$. In particular, $x_t = x_0$ if $x_0 (x^t-1) \equiv 0 \pmod{c(x)}$.

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