6
$\begingroup$

I was trying to generate maximal length pseudo random sequence using an linear feedback shift register (LFSR). I have read from many sources that the length of the pseudo random sequence generated from the LFSR would be maximum if and only if the corresponding feedback polynomial is primitive.

I have tried to generate the pseudo random sequence for the primitive polynomial (4,1,0) (corresponding to polynomial $x^4 + x + 1$) by tapping at bits 4 and 1, and it has resulted in a sequence with a period of $2^4$ - 1 = 15. Similarly I have tried primitive polynomial given by (3, 1, 0) (corresponding to polynomial $x^3 + x + 1$) by tapping at bits 3 and 1 and it has resulted in a sequence of period $2^3$ - 1 = 7.

When I tried to apply this same logic to the primitive polynomial (5, 2, 0) (corresponding to polynomial $x^5 + x^2 + 1$) it yields a sequence with period 15. While it should have yielded a sequence with period 2^5 -1 = 31. Following is the circuit diagram for (5, 2, 0)

(5, 2, 0) LFSR

1) What is the exact procedure to convert the given polynomial into a maximal length LFSR?

2) How do I determine the correct tap bits for a given polynomial?

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
3
$\begingroup$

The LFSR that you give is really of length $4$ rather than $5$, since $b_1$ never gets used. The correct way to implement a "Fibonacci" LFSR is explained in the Wikipedia article: $b_1$ should be the leftmost bit rather than the rightmost bit.

There is also an alternative kind of LFSR knows as a "Galois" LFSR, also described in Wikipedia, which is dual to a Fibonacci LFSR: at each point, the contents of the register is shifted, and if the bit which is shifted out is 1, then a mask is XORed to the contents. In both types of LFSR, the resulting sequence has maximum period iff the feedback polynomial is primitive.

The polynomials that you give as examples are known as trinomials, polynomials with three non-zero monomials. Not all trinomials are primitive. There are algorithms for deciding whether a trinomial, or any other polynomial, is primitive. As far as I know, there is no explicit construction of primitive polynomials.

How do we test whether a given polynomial $P$ of degree $n$ is primitive? The first step is verifying that it is irreducible. The second step verifies that $x^{(2^n-1)/p} \not\equiv 1 \pmod{P}$ for every prime divisor $p$ of $2^n-1$ – this step requires factoring $2^n-1$. A list of primitive polynomials can be found on Wikipedia.

Improve this answer
$\endgroup$
6
  • $\begingroup$ I totally agree with you that not all tri-nomials are primitive polynomials. However, (3,1,0), (4, 1, 0), (5,2,0) are all primitive polynomials. $\endgroup$
    – CryptoNovice
    Commented Jun 18, 2015 at 15:16
  • $\begingroup$ If the resulting sequence has period 15 then $(5,2,0)$ isn't primitive, by definition. That said, $(5,2,0)$ appears on the list of primitive polynomials linked to on Wikipedia, so perhaps your code has a bug. $\endgroup$
    – Yuval Filmus
    Commented Jun 18, 2015 at 15:17
  • $\begingroup$ Finally I understand your question and can answer it (see my updated answer). $\endgroup$
    – Yuval Filmus
    Commented Jun 18, 2015 at 15:29
  • $\begingroup$ Here is a Matlab code snippet which tells that (5,2,0) is primitive. >> poly3 = primpoly(5) Primitive polynomial(s) = D^5+D^2+1 poly3 = 37 >> dec2bin(poly3) ans = 100101 >> $\endgroup$
    – CryptoNovice
    Commented Jun 18, 2015 at 15:30
  • $\begingroup$ Thanks for that update @Yuval Filmus. I still have some doubts on this. My polynomial is (5,2,0) that will translate to $x^5+x^2+x^0$=$x^5+x^2+1$. This sequence, being a primitive polynomial should have a length of $2^5 - 1 = 31$. That means that this shift register should traverse through 31 states before repeating the state again. Now that we need to represent 31 states, we need 5 bits ($2^5$ -1) . That means my register would have bits b5, b4, b3, b2 and b1 (each represents a bit). Could you please elaborate on how you say that this diagram represents shift register of length 4? $\endgroup$
    – CryptoNovice
    Commented Jun 18, 2015 at 15:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.