I was following along with Christof Paar's lecture on Linear Feedback Shift Registers. He explains the structure coherently as a set of flip flops where the 'taps' are defined by a bit vector (0 for no tap on that flip flop, 1 for a tap on that flip flop). This makes perfect sense to me.

But then he brings up the point that people describe an LFSR not as a set of flip flops and a bit vector to define the taps, but as a polynomial equation.

I don't understand what this polynomial representation is trying to do.

P(x) = x^4 + x + 1 would represent a network of 4 flip flops, the right-most two being 'tapped' to XOR into the new bit.

What is the value P(x) supposed to be? In fact, I'm not even sure what the x value is. Further mysteries to me: (1) the far right flip flop is represented by 1. Is this shorthand for x^0 ? (2) the x^4 term.... the four flip-flops are labelled 0,1,2,3. So why a power-four term?

Makes me wonder if this 'equation' isn't really an equation you expect to emit a value to use, but some kind of hand-wavy way to just describe the architecture of a LFSR?

  • $\begingroup$ Visual guide and $P(x) = 0$ as usual! $\endgroup$
    – kelalaka
    Oct 4, 2021 at 13:52
  • 1
    $\begingroup$ By the way, generating functions in combinatorics are based on the same idea. $\endgroup$
    – Fractalice
    Oct 4, 2021 at 16:06

1 Answer 1


What is the value $P(x)$ supposed to be?

Nothing. We are interested in the coefficients of the polynomial $P(x)$, which are restricted to the Booleans $\{0,1\}$. These coefficients reflect the wiring of the LFSR. For other polynomials, they could reflect the state of the LFSR. We seldom¹ need to evaluate that polynomial $P(x)$, or other polynomials we use, for a particular value of $x$, or even specify the set $x$ belongs to. Think of $x$ as an unspecified variable, be it in integers $\mathbb Z$, rationals $\mathbb Q$, reals $\mathbb R$, complexes $\mathbb C$, as you see fit; and confidently perform arithmetic on such polynomials per the standard rules of algebra, modified by $1+1=0$ (equivalently, by reducing all coefficients of polynomials modulo $2$).

The far right flip flop is represented by $1$. Is this shorthand for $x^0$?

Yes. Another reason we write $1$ is to avoid having to define $0^0$.

The four flip-flops are labelled $0,1,2,3$. So why a power-four term?

The degree-four term is only in $P(x)$, which represents the wiring of the LFSR, not the state of it's flip-flops. When dealing with the state, it will be represented by a polynomial $S(x)$ of degree at most three.

Also: when we reduce any polynomial modulo the polynomial $P(x)$, the remainder $S(x)$ has degree strictly lower that $P(x)$, thus it's coefficients (typically a new state of the LFSR) fit the four flip-flops.

Yet another way to see it is that the term $x^4$ in $P(x)$ corresponds to the bit that gets out of the shift register when we shift by one bit (equivalently, multiply the state by $x$), while the other bits correspond to adjustments of the new states of each flip-flop.

Makes me wonder if this 'equation' isn't really an equation you expect to emit a value to use, but some kind of hand-wavy way to just describe the architecture of a LFSR?

Indeed, $P(x)$ is about the architecture of the LFSR. The representation as polynomial $P(x)$ for architecture and $S(x)$ for state is useful to establish properties of LFSRs. In particular, for a LFSR in Galois form, the state evolves per $S_{i+1}(x)=S_i(x)\,x\bmod P(x)$, from which it follows $S_i(x)=S_0(x)\,x^i\bmod P(x)$.

Note: here, $\bmod$ yields the remainder per polynomial division, again with coefficients in the Booleans.

¹ Exceptions: evaluation of $P(x)$ at $x=1$ in the Booleans, or $x=2$ for the integers, yield occasionally interesting values.


Your Answer

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

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