10
$\begingroup$

As far as I understand, the "polynomial" of the LFSR tells us the positions of the register where taps are situated.

However, the natural way to look at the positions would be to think of them as $x_1, x_2, x_3,\cdots$. But we instead identify them as powers of something and call them $x, x^2, x^3, \cdots$

My question is, what are they powers of? And why do we add a 1 to the polynomial?

$\endgroup$
3
  • $\begingroup$ you mention taps, are you more interested in the mathematics or hardware implications? $\endgroup$
    – b degnan
    Feb 14, 2017 at 22:33
  • $\begingroup$ I am interested in mathematical implications @b degnan $\endgroup$ Feb 15, 2017 at 2:32
  • $\begingroup$ Old, but see here: blog.fkraiem.org/2013/10/06/… (it requires some notion of linear algebra, which can be found in any standard text) $\endgroup$
    – fkraiem
    Feb 15, 2017 at 12:48

2 Answers 2

2
$\begingroup$

The polynomial $X^i$ is a delay operator, so formally $X^i(s_t)=s_{t-i}$.

It's also a linear operator so $X^i(a s_t)=a s_{t-i}$.

Let's apply this to the following simple LFSR in Fibonacci configuration
3-stages LFSR

At each clock cycle, a new state $s_t$ is computed from delayed states $s_{t-1}$ and $s_{t-3}$, as $s_t=s_{t-1}+s_{t-3}$. That recurrence can be rewritten as $s_{t-3}+s_{t-1}-s_t=0$, and represented as the polynomial $X^3+X-1=0$ (the $1$ is a shorthand for $X^0$). In binary, both $+$ and $-$ are eXlusive-OR $\oplus$ and we write the polynomial modulo 2, as $X^3+X+1.$

Moreover, not only is there a one to one correspondence between recurrences (equivalently LFSRs) and polynomials, but the roots of the polynomial feature in the solutions, i.e., the sequence generated.

$\endgroup$
3
  • $\begingroup$ Do the delay operator and XOR form a field? $\endgroup$ Feb 15, 2017 at 2:33
  • $\begingroup$ I'll clarify when I get some time, on the answer itself. $\endgroup$
    – kodlu
    Feb 15, 2017 at 5:46
  • 1
    $\begingroup$ @fgrieu, I have no problem with you editing and improving this terse answer. Thank you. $\endgroup$
    – kodlu
    Feb 15, 2017 at 21:29
1
$\begingroup$

Assuming that you are not a mathematician, this is what I tell my engineers: What polynomials represent in the mathematical sense are "extension fields" of Galois Fields, which are modulo(2) fields of binary. The smallest prime field that exists is $GF(2)$, and then we represent the others as extension fields of $GF(2^m)$, where $m$ is the number of bits. Again, this is because these are binary fields. These powers represent bit values in the field.

From the practical sense, what is a reducible polynomial? Here is an example:

$x^4+ x^3+ x^1+ 1 =(x^2+ x^1+ 1)(x^2+ 1)$

This is reducible and thereby cannot be used to create a prime extension field. This is why we use irreducible polynomials. The polynomial for AES is

$P(x)=x^8+x^4+ x^3+ x^1+ 1$

Even though this field is not reducible, it still has that $+1$ on it. The short description for the 1 is from set theory, where all elements in a field must form a multiplicative group, and there must me the identity element. Primes can still be multiplied by 1 to get a prime number. The $+1$ is there for completeness and drops out if you do any binary addition between two polynomial values because $+1$ XOR $+1$ is $0$

$\endgroup$

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.