2
$\begingroup$

An LFSR with polynomial 1+x4+x5 = (1+x+x2)(1+x+x3) can generate several sequences, depending on the initial value.
If I did not made any mistake enumerating them, the sequences length are 3, 7 and 21.
For 1+x+x4+x6 = (1+x)(1+x+x2)(1+x+x3), I get 1, 3, 3, 7, 7, 21, 21
For 1+x+x6+x8+x9 = (1+x+x2)(1+x+x3)(1+x+x4), I get 3, 7, 15, 15, 15, 15, 21, 105, 105, 105, 105

My goal is to have an algorithm to compute those length without going through the enumeration of all sequences. I am a bit puzzled by the fact that in the last example 45=3*15 is not in the list. A link to a paper or a book dealing with that would be a great help: a lot of books cover LFSRs but most of the time they cover only maximum length cases...

$\endgroup$
4
$\begingroup$

A single iteration of an LFSR with feedback polynomial $p(x)$ amounts to multiplication (of the "LFSR-content polynomial" by $x$ modulo $p(x)$. So with initial value $q(x)$ the least period of the resulting sequence is the smallest positive integer $m$ with the property that $$ x^mq(x)\equiv q(x)\pmod{p(x)}. $$ The basic fact (you undoubtedly know this - just stating it for reference) is that if

  • $p(x)$ is irreducible (also $p(x)\neq x$ as nobody uses a feedback polynomial with constant term zero), and
  • $q(x)$ is not divisible by $p(x)$,

then the length of the period is the order of $x$ modulo $p(x)$. In other words, the same period that we get we $q(x)=1$ = the multiplicative order of the element $x+\langle p(x)\rangle$ in the finite field $\Bbb{F}_2[x]/\langle p(x)\rangle$. Of course, if $q(x)$ is divisible by $p(x)$, i.e. $\equiv0\pmod{p(x)}$, then the resulting sequence has period $1$, as the sequence is just all zeros.

As you noticed it is a bit more complicated, when $p(x)$ is not irreducible. Your examples fall under the umbrella case of a square free $p(x)$, when the feedback polynomial has no repeated factors. Here Chinese remainder theorem comes to our rescue. Assume that we have the factorization $$ p(x)=p_1(x)p_2(x)\cdots p_t(x) $$ with the polynomials $p_i(x)\in\Bbb{F}_2[x]$ all irreducible and distinct. Then CRT states that $$ \Bbb{F}_2[x]/\langle p(x)\rangle\cong \Bbb{F}_2[x]/\langle p_1(x)\rangle\oplus \Bbb{F}_2[x]/\langle p_2(x)\rangle\oplus\cdots\oplus\Bbb{F}_2[x]/\langle p_t(x)\rangle. $$ Furthermore, the isomorphism simply sends the coset of $q(x)$ modulo $p(x)$ to a vector containing the cosets of $q(x)$ modulo all the factors $p_i(x), i=1,2,\ldots,t.$

Because multiplication by $x$ is thus preserved all around, what this means is that the LFSR with feedback polynomial $p(x)$ can be viewed as a combination of $t$ LFSRs - with respective feedback polynomials $p_i(x)$ running on synch. This allows us to calculate the periods of the resulting sequences. Assume that the irreducible factor $p_i(x)$ produces a sequence of length $L_i, i=1,2,\ldots,t$, when given a non-zero input. Then the CRT isomorphism means that the individual components of the LFSR gotten from $p(x)$ have periods $L_i$ or $1$ according to whether $q(x)$ is divisible by $p_i(x)$ or not. This means that the states of the "combination of $t$ LFSRs" repeat with period $$ L=\operatorname{lcm}\{L_i\mid i=1,2,\ldots,t,\ p_i(x)\nmid q(x)\}. $$

For example $p_1(x)=1+x+x^2$ gives length $L_1=3$, $p_2(x)=1+x+x^3$ has $L_2=7$ and $p_3(x)=1+x+x^4$ has length $L_3=15$. When you combine them to your second example $$ p(x)=p_1(x)p_2(x)p_3(x) $$ you get sequences with periods for example $21$ when the initial polynomial $q(x)$ is divisible by $p_3(x)$, but is not divisible by either $p_1(x)$ or $p_2(x)$, because in that case $$ L=\operatorname{lcm}\{3,7\}=21. $$ You cannot get $3\cdot15$, because the least common multiple of $3$ and $15$ is $15$. For the same reason you won't see period $3\cdot7\cdot15$ either.

Edit: Adding a census of periods of sequences generated by the feedback polynomial $$ p(x)=1+x+x^6+x^8+x^9=(1+x+x^2)(1+x+x^3)(1+x+x^4). $$ We can view these as coming from the above "virtual" parts corresponding to the three irreducible factors. For the part corresponding to $1+x+x^2$ there are $3$ non-zero choices of inputs. For the part corresponding to $1+x+x^3$ there are $7$, and for the part corresponding to $1+x+x^4$ there are fifteen. For each of these there is a single choice giving the zero input. By CRT the choices are independent from each other. Call the periods of the different parts $L_1$, $L_2$ and $L_3$. We have 8 combinations $$ \begin{array}{c|c|c|c|c} L_1&L_2&L_3&L=\operatorname{lcm}\{L_1,L_2,L_3\}&\text{number of sequences of this type}\\ \hline 1&1&1&1&1\cdot1\cdot1=1\\ 1&1&15&15&1\cdot1\cdot15=15\\ 1&7&1&7&1\cdot7\cdot1=7\\ 1&7&15&105&1\cdot7\cdot15=105\\ 3&1&1&3&3\cdot1\cdot1=3\\ 3&1&15&15&3\cdot1\cdot15=45\\ 3&7&1&21&3\cdot7\cdot1=21\\ 3&7&15&105&3\cdot7\cdot15=315 \end{array} $$

So looking at the two last columns we see that there is a single sequence with period $L=1$, $3$ sequences with period $L=3$, $7$ sequences with period $L=7$, $15+45=60$ sequences of period $L=15$, $21$ sequences of period $L=21$, and last but not least $105+315=420$ sequences of period $L=105$. Here the total number of sequences generated by this LFSR is $$ 1+3+7+60+21+420=512=2^9 $$ as we would expect. Note that the sequence of period $1$ here is the all zeros sequence, which is sometimes excluded from the tally. Your pick.


It gets more complicated, when we allow repeated factors. You may (or may not) get doubled (or quadrupled, or...) period from the multiple factors. Chinese remainder still helps, but we need to analyze the case of a feedback polynomial that is a power of an irreducible polynomial separately. I won't get into that at this time.

Hope this helps.

$\endgroup$
  • $\begingroup$ Thanks very much, I would never have found that out by myself... I am still struggling a bit with the example: we have 3 "primitive" length L1, L2, L3, so there are only 8 combinations possible, that cannot add up to the 11 sequences length that I enumerated in the original post. I am missing 2 sequences with length 15 and 2 others with length 105. I thing the enumerated sequence lengths are correct because the sum of their length is 511, the maximum length for degree 9 polynomial. I tried the permutations, but then I get too many sequences. What did I miss ? $\endgroup$ – acapola Jul 21 '14 at 22:01
  • $\begingroup$ I added a census. Does that help? $\endgroup$ – Jyrki Lahtonen Jul 22 '14 at 16:31
  • $\begingroup$ Thanks that helps a lot. I was counting cycles rather than sequence: 420 sequences of length 105 are 4 different cycles...<br> $\endgroup$ – acapola Jul 22 '14 at 19:07
  • $\begingroup$ Note for the curious about the irreducible polynomial cases: to find the length of the generated sequences you need to find the number k such that x^k mod p(x)=1, k being the product of a combination of the prime factors of (2^n)-1, n being the degree of p(x). $\endgroup$ – acapola Jul 22 '14 at 19:18

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.