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
2
-
$\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. ♦Commented Nov 18, 2015 at 2:22
-
$\begingroup$ See also cs.stackexchange.com/q/43707/755 for a related topic. $\endgroup$– D.W. ♦Commented Nov 18, 2015 at 2:24
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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)}$.
answered Nov 18, 2015 at 8:27