0
$\begingroup$

Disclaimer: I am neither an electronics engineer nor am I a mathematician.
I understand what an LFSR is. I can derive the periodic sequence if an LFSR is described by it's taps.

My question is - why are LFSRs represented as polynomials?

What is the advantage of representing taps as x^n? What is the x? What is the constant at the end?

I see a very similar question - Why is the polynomial of an LFSR called so?

But I am still asking my question because I don't understand the answers. I don't understand what a delay operator is. So the answer is not useful to me.

Also that answer doesn't really cover the advantage of representing it as a polynomial.

$\endgroup$
4
  • 2
    $\begingroup$ So what is your background? What have you searched for else for your answer? To analyze we need to represent almost all as a mathematical representation! This question is like why cars have tires. $\endgroup$
    – kelalaka
    Sep 3 '20 at 12:26
  • 3
    $\begingroup$ Because the LFSR update step is perfectly described by multiplication by $x$ modulo the defining polynomial. And mathematics of this are used to learn properties of the LFSR. $\endgroup$
    – Fractalice
    Sep 3 '20 at 13:18
  • $\begingroup$ I second the above. For details about the fact that follows "because", this answer might help, especially the part after "The next state of the LFSR is, by definition". $\endgroup$
    – fgrieu
    Sep 3 '20 at 14:41
  • $\begingroup$ @kelalaka - I am an experienced C++/Java programmer. I have learnt a lot of Math in my undergrad but that was all applied math unrelated to Comp Sci or Crypto. Recently I am reading up on Congruences & Modulos - and I have a basic understand of that. $\endgroup$
    – user93353
    Sep 3 '20 at 15:00
4
$\begingroup$

why are LFSRs represented as polynomials?

Because it gives useful insights into the behavior of the LFSR.

If the feedback terms are represented by the polynomial $P$, and if the initial state of the LFSR is represented by the polynomial $Q$, then the state of the LFSR after $n$ steps will be the polynomial $x^n Q \bmod P$ (where the calculation is done on polynomials, and not on the underlying field - algebra on polynomials is not difficult, however it is different than what you may be used to).

Why is this a useful insight? Because we can determine the long-term behavior from this observation. For one, we have $x^n Q \bmod P = (x^n \bmod P) \times Q \bmod P$; assuming that the constant term of $P$ is relatively prime to the field characteristic, then $x^n \bmod P = 1$ for some $n$, and so the LFSR will eventually return to its initial state (and not fall into an intermediate-state loop).

Furthermore, we can deduce that, as long as $Q$ is relatively prime to $P$, then the number of steps that the LFSR will take before it returns to the original step is independent of the actual setting of $Q$.

Thirdly, if $P$ is an "irreducible polynomial", that is, if there do not exist polynomials $R, S$ with degree > 0 s.t. $P = R \times S$, then the amount of time taken before the LFSR returns to its initial state will be a factor of $p^k$, where $p$ is the size of the field used (2 if we're doing out LFSR in a binary field) and $k$ is the degree of $P$.

These observations (except for the first) are not obvious from the abstract definition of an LFSR.

And your final question:

What is the final constant in the polynomial?

It's just another feedback term from the LFSR. The LFSR can be represented in 'Fibonacci' or 'Galois' modes (and the above abstraction works for both, so it doesn't matter which for the above discussion). In the 'Fibonacci' mode (which appears to be what you are asking about), this constant term corresponds to the sum of the feedback terms that is used to generate the new bit within the LFSR.

$\endgroup$
5
  • $\begingroup$ Thank you. I didn't understand the last line - this constant term corresponds to the sum of the feedback terms that is used to generate the new bit within the LFSR. $\endgroup$
    – user93353
    Sep 4 '20 at 15:05
  • $\begingroup$ What do you mean sum of the feedback terms? $\endgroup$
    – user93353
    Sep 4 '20 at 15:06
  • $\begingroup$ @user93353: in a Fibonnaci-style LSFR, each iteration we generate a new bit by computing $a_0x_0 + a_1x_1 + … + a_nx_n$, where $a_i$ are the LFSR coefficients, and $x_i$ is the previous LFSR state. This is the sum I'm talking about (and if you're using a binary LFSR, $+$ is the same as exclusive-or) $\endgroup$
    – poncho
    Sep 4 '20 at 15:15
  • $\begingroup$ No, I get that. Also the co-efficient of each x^n is 0 or 1 depending on whether that bit is tapped or not. But what is the co-efficient of x^0 - i.e. the final constant in the polynomial $\endgroup$
    – user93353
    Sep 4 '20 at 15:39
  • 1
    $\begingroup$ @user93353: For a Fibonacci LFSR (where all the bits are shifted without change and a single new one is entered), the coefficient x^0 (=1) represents the new bit computed by XOR of the other inputs under the convention that x^n is the bit that falls off the register. Another convention exists where x^0 falls off, and x^n represents the new bit. In both conventions, the XOR of all the bits with a coefficient is zero. The two conventions can be thought as running the LFSR in the forward direction, or walking back. The formula $x^n\,Q\bmod P$ does not apply directly to a Fibonacci LFSR. $\endgroup$
    – fgrieu
    Sep 4 '20 at 16:26
1
$\begingroup$

Since you said you learnt a lot of math in your undergrad, here is an analogy (just an analogy):

Differential Equations:

$x’’(t)=a x’(t)+bx(t)$

Why are $a,b$ there? What does linking $x’’(t),x’(t),x(t)$ this way mean?

It is the model for a physical dynamical process.

Why do we use the characteristic polynomial below?

$\lambda^2 + a \lambda + b =0 $

Fourier/Laplace theory relates it to the model. Then we can express the solutions as something like

$ x(t)=c_1 e^{\lambda_1 t} + c_2 e^{\lambda_2 t} $

where $\lambda_i$ are the roots of the polynomial.

In discrete maths either over reals or over finite fields there is a completely analogous theory of difference equations

$x_n= a x_{n-1}+ b x_{n-2}$

and roots of characteristic polynomials are used to represent solutions.

The LFSR implements a difference equation over the binary field $GF(2).$ The solutions as linear combinations of powers of roots of the characteristic polynomial. Plus we build the LFSR pick the coefficients in the binary field.

Edit: For primitive polynomials which give maximum length LFSR sequences, the roots have a special algebraic structure (conjugates) which means you can write and efficiently calculate (say) the 199,999th term of the sequence without computing the previous terms, via the trace representation. You cannot do this otherwise, say with the taps.

Bonus: Everything being finite the solutions are exact which we need in coding, cryptography, etc.

$\endgroup$
4
  • $\begingroup$ Why are a,b there? - I understand the co-efficients in the LFSR - the co-efficients are {0,1} depending on whether the bit is tapped or not. The co-effs aren't the problem - the problem is the x^n - I don't understand what they are. $\endgroup$
    – user93353
    Sep 4 '20 at 3:25
  • $\begingroup$ What does linking x′′(t),x′(t),x(t) this way mean? - x' is the rate of the change of x. x" is the rate of change of x'. But what is the x^n in polynomial representation of LFSRs? $\endgroup$
    – user93353
    Sep 4 '20 at 3:27
  • $\begingroup$ Your answer though informative doesn't answer either of my questions? 1) What do we get by using the polynomial notation 2) What is the final constant in the polynomial? $\endgroup$
    – user93353
    Sep 4 '20 at 3:28
  • $\begingroup$ Everything being finite the solutions are exact which we need in coding, cryptography, etc - this is what I am interested in - how is the polynomial using in coding or crypto if at all that's the only reason the LFSR is represented as polynomial of x^ns? What advantage do I get by representing the LFSR as a polynomial of x^ns. I can calculate the periodic sequence of an LFSR by just knowing which of the bits are tapped. So what extra does the x^n give me? $\endgroup$
    – user93353
    Sep 4 '20 at 3:30

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.