0
$\begingroup$

I tried to search on the internet, to read my course multiple times, but the only thing I see are definitions of the primitive polynomials for an LFSR.

I have an exercise: Find the primitive polynomial of the LFSR of width 4 with longest possible period.

And I just don't know where to begin from.

By all I read, I know that it is irreducible and that the period will be $2^4-1$, so 15.

How do I find it?

$\endgroup$
0
$\begingroup$

This is a problem that is small enough that we can do it by brute force. The quartic polynomial must have $x^4$ and $1$ terms in it, and so we need to look only at $8$ quartics. Of these, $x^4 + 1, x^4+x^2+1$ can be eliminated as obvious squares, while $x^4+x^3+x^2+1$, $x^4+ x^3+x+1$, $x^4+x^2+x+1$ have an even number of terms in them and thus have $1$ as a root (i.e., are divisible by $x+1$). That leaves $x^4+x+1$, $x^4+x^3+1$, and $x^4+x^3+x^2+x+1$ as possible candidates of which we can eliminate $x^4+x^3+x^2+x+1 = \frac{x^5-1}{x-1}$ as having period $5$ and not $15$.

$\endgroup$
1
$\begingroup$

What you are obviously looking for is a primitive polynomial of degree 4 over ${\Bbb F}_2$. There are two such polynomials, $x^4+x+1$ and $x^4+x^3+1$ (both are conjugate). There is another irreducible polynomial of degree 4 over ${\Bbb F}_2$, $x^4+x^3+x^2+x+1$, but it divides $x^5-1$ and so is not primitive.

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