2
$\begingroup$

An LFSR with a reducible polynomial can generate several sequences, depending on the initial value. My goal is to have an algorithm to compute those length without going through the enumeration of all sequences.

So far I am able to compute the length of sequences for the following polynomial cases:
- primitive: 1+x+3
- irreducible: 1+x+x2+x3+x4
- reducible and square free: 1+x4+x5 = (1+x+x2)(1+x+x3) (this is explained here: Sequences length for LFSR when polynomial is reducible)
- power of primitive: 1+x2+x6 = (1+x+x3)^2
- power of irreducible: 1+x2+x4+x6+x8 = (1+x+x2+x3+x4)^2

But the remaining 3 cases seem harder:

  1. product of powers of primitive:
    • 1 + x + x2 + x5 = (1+x)^2*(1+x+x3)
    • 1 + x + x2 + x3 + x6 + x7 = (1+x)(1+x+x3)^2
  2. product of powers of irreducible
  3. product of powers of primitive and irreducible

An example: 1+x+x2+x3+x5+x7+x8+x9+x13 = (1+x+x2)(1+x2+x3)(1+x+x4)^2.
The terms taken separately are giving:

1+x+x2:      3 sequences of period 3 (L1)
1+x2+x3:     7 sequences of period 7 (L2)
(1+x+x4)^2: 15 sequences of period 15 (L3) and 240 sequences of period 30 (L4). 

Combining them using LCM for the number of sequence and for the length gives the following:

3    sequences of period 3
7    sequences of period 7
15   sequences of period 15   -> I expect 60 of them.
21   sequences of period 21
240  sequences of period 30   -> I expect 960 of them.
105  sequences of period 105  -> I expect 420 of them.
1680 sequences of period 210  -> I expect 6720 of them.


So combining period length with LCM gives the correct set of period lengths, but for the number of sequences, I am missing something.
For sequences of period 15, we have 2 combinations

- LCM(1,1,15,1) = 15 and for the number of sequences similarly we get 15
- LCM(3,1,15,1) = 15 and for the number of sequences similarly we get 15

the sum would be 30, or the LCM(15,15) is 15, either way I don't get to the expected 60.

$\endgroup$
3
$\begingroup$

As always we start by calling the Chinese remainder theorem for help. So if your feedback polynomial $f(x)$ has the factorization $$ f(x)=\prod_{i=1}^tp_i(x)^{a_i}, $$ where $p_i(x)\in\Bbb{F}_2[x]$ are distinct irreducible polynomials, then CRT gives us the isomorphism $$ \Bbb{F}_2[x]/\langle f(x)\rangle\cong \bigoplus_{i=1}^t\Bbb{F}_2[x]/\langle p_i(x)^{a_i}\rangle. $$ If you initialize the LFSR with the polynomial $q(x)$, then the period $L$ of the resulting sequence is the smallest positive integer such that $x^Lq(x)\equiv q(x)\pmod {f(x)}$. By the above isomorphism $x^Lq(x)\equiv q(x)\pmod{f(x)}$ if and only if $x^Lq(x)\equiv q(x)\pmod{p_i(x)^{a_i}}$ for all $i=1,2,\ldots,t$. As in your previous question, if $L_i, i=1,2,\ldots,t,$ is the smallest positive integer such that $x^{L_i}q(x)\equiv q(x)\pmod{p_i(x)^{a_i}}$, then we can conclude that $$ L=\operatorname{lcm}\{L_1,L_2,\ldots,L_t\}, $$ i.e. the period is the least common multiple of the periods you would get from the same input using the powers $p_i(x)^{a_i}$ as feedback polynomials.

Now the game becomes a bit more interesting. Let us fix $i, 1\le i\le t,$ and denote the period of $q(x)=1$ modulo $p_i(x)$ by $L_{i,1}$. In other words $L_{i,1}=m$ is the smallest positive integer $m$ such that $p_i(x)\mid x^m+1$ in the ring $\Bbb{F}_2[x]$.

By squaring this we get that $p_i(x)^2\mid (x^m+1)^2=x^{2m}+1$. Repeating the dose we get that $p_i(x)^4\mid x^{4m}+1$, and, more generally, $p_i(x)^{2^j}\mid x^{2^{j}m}+1$. This leads up to the following

Lemma. If $L_{i,k}$ is the smallest integer $m$ with the property that $p_i(x)^k\mid x^m+1$, and $j$ is the smallest integer such that $2^j\ge k$, then we have $$ L_{i,k}=2^jL_{i,1}. $$

Proof. This follows from the observation that if $r$ is an odd integer, then the binomial $g(x)=x^r+1$ has no multiple factors, because $\gcd(g(x),g'(x))=1$. On the other hand we have, for all odd integers $r$ and all $j>0$ $$ x^{2^jr}+1=(x^r+1)^{2^j}, $$ so all the factors of $x^{2^jr}+1$ have multiplicity $2^j$.

Corollary. If we initialize an LFSR with feedback polynomial $p_i(x)^{a_i}$ with input $q(x)$, and $p_i(x)^\ell$ is the highest power of $p_i(x)$ that divides $q(x)$ (i.e. $p_i^\ell\mid q(x)$, but $p_i^{\ell+1}\nmid q(x)$), then the smallest integer $m$ with the property that $x^mq(x)\equiv q(x)\pmod{p_i(x)^{a_i}}$ is equal to $L_{i,a_i-\ell}$. In other words, if $2^j$ is the smallest power $\ge a_i-\ell$, then we get $L_i=2^jL_{i,1}$.

Proof. This follows from the preceding Lemma, because $(x^m+1)q(x)$ is divisible by $p_i(x)^{a_i}$ if and only if $x^m+1$ is divisible by $p_i(x)^{a_i-\ell}$.

This allows us to make a census of the sequence lengths generated by a feedback polynomial that is a power of an irreducible one much like in my answer to the simpler version of this question.

As an example let us consider, for a change, a non-primitive irreducible polynomial $p(x)=1+x+x^2+x^3+x^4$, which is a factor of $x^5-1$ and thus gives rise to sequences with period $L_1=5$. Let us further specify the feedback polynomial $f(x)=p(x)^5$ that is of degree $20$. Here $2^3=8$ is the smallest power of two $>5$. Altogether we have $2^{20}$ possible ways $q(x)$ of initializing this LFSR. Because $\deg p(x)=4$, of the possible choices of $q(x)$ there are exactly $2^{20-4}=2^{16}$ that are divisible by $p(x)$. Of those $2^{16-4}=2^{12}$ are divisible by $p(x)^2$, $2^8$ are divisible by $p(x)^3$, $2^4$ are divisible by $p(x)^4$ and a single one, namely $q(x)=0$ is divisible by $p(x)^5$. The corresponding periods of the generated sequences are $8\cdot5$, $4\cdot5$, $4\cdot5$, $2\cdot5$, $1\cdot5$ and $1$ respectively. Thus we get

  • $2^{20}-2^{16}=983040$ sequences of period $40$,
  • $2^{16}-2^8=65280$ sequences of period $20$,
  • $2^8-2^4=240$ sequences of period $10$,
  • $2^4-2^0=15$ sequences of period $5$, and
  • a single sequence (all zeros) of period $1$.

To a given feedback polynomial you can then combine the frequencies of such data for each power of an irreducible factor that appears in the feedback polynomial the same way as was done in the linked answer.


Appending this with the desired example of $$ f(x)=(1+x+x^2)(1+x+x^3)(1+x+x^4)^2 $$ of degree $13$. With $p_1(x)$ there are $n_1=3$ sequences of length $L_1=3$ and $n_1=1$ sequence with $L_1=1$. With $p_2(x)=1+x+x^3$ there are $n_2=7$ sequences of length $L_2=7$ and $n_2=1$ sequence with $L_2=1$. With $p_3(x)^2=(1+x+x^4)^2$ there are $n_3=240$ sequences with $L_3=30$, $n_3=15$ sequences of length $L_3=15$ and $n_3=1$ sequence of length $1$. This time there are $12$ different combos.

$$ \begin{array}{c|c|c|c|c} L_1,n_1&L_2,n_2&L_3,n_3&L=\operatorname{lcm}\{L_1,L_2,L_3\}&\text{number of sequences of this type}=n_1n_2n_3\\ \hline 1,1&1,1&1,1&1&1\cdot1\cdot1=1\\ 1,1&1,1&15,15&15&1\cdot1\cdot15=15\\ 1,1&1,1&30,240&30&1\cdot1\cdot240=240\\ 1,1&7,7&1,1&7&1\cdot7\cdot1=7\\ 1,1&7,7&15,15&105&1\cdot7\cdot15=105\\ 1,1&7,7&30,240&210&1\cdot7\cdot240=1680\\ 3,3&1,1&1,1&3&3\cdot1\cdot1=3\\ 3,3&1,1&15,15&15&3\cdot1\cdot15=45\\ 3,3&1,1&30,240&30&3\cdot1\cdot240=720\\ 3,3&7,7&1,1&21&3\cdot7\cdot1=21\\ 3,3&7,7&15,15&105&3\cdot7\cdot15=315\\ 3,3&7,7&30,240&210&3\cdot7\cdot240=5040 \end{array} $$ So altogether there are for example $15+45=60$ sequences with period $15$ (from rows $2$ and $8$ of the table) and $1680+5040=6720$ sequences with a period of length $210$ (from rows $6$ and $12$).

$\endgroup$
  • $\begingroup$ Thanks very much for this detailed answer. I am still struggling with the part explained in the last 3 lines :-S. I added an example in the original post to show where I get confused. Could you give me an additional hint ? $\endgroup$ – acapola Aug 5 '14 at 23:15
  • $\begingroup$ @acapola: I added a full census of sequences with your example feedback polynomial. I think all 8192 are in there. This time I used both two sets of variables. The $L_i$ tell the period lengths, the $n_i$ the number of residue classes with respect to that factor that lead to a sequence with this "partial" period. Sorry about not making their distinction clear earlier. $\endgroup$ – Jyrki Lahtonen Aug 6 '14 at 14:18
  • $\begingroup$ Thanks very much the census clarified everything :-) The crucial point is to build the combination table with 3 columns, not 4 as I was doing.... $\endgroup$ – acapola Aug 6 '14 at 22:44

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.