1
$\begingroup$

I'm reading through wikipedia about Linear Feedback Shift Registers (Specifically Fibonacci LFSRs) and the only restrictions it mentions about the taps are:

  • The LFSR will only be maximum-length if the number of taps is even; just 2 or 4 taps can suffice even for extremely long sequences.
  • The set of taps must be relatively prime, and share no common divisor to all taps.

It has two other bullet points basically saying that there can be more than one working set of taps, and if you find one set of taps, you can use that to determine another set of taps. Is this all it takes to find taps?

Are these the only restrictions to finding taps in a Fibonacci LFSR?

I know there are plenty of reference tables to look up taps, but I'm trying to understand the fundamentals of an LFSR better.

1 Answers 1

1

The taps, including an extra "zero" tap, form a polynomial $P(X)$ over $GF(2)$, we should satisfy two properties:

  1. $P(X)$ must be irreducible. Otherwise, the sequence decomposes (in some way) as a "direct sum" of several different LFSRs (try an example to see what this means).

  2. The order of $X$ modulo $P(X)$ is the period of the LFSR sequence. If the period is maximal ($2^{\deg P} - 1$), then the polynomial is called primitive.

If the number of taps is odd then $P(X)$ will have an even number of elements, so $P(1) = 0$. This implies that $P(X)$ is divisible by $X+1$, and so is reducible.

If the taps have a common factor $k$, then taking $Y=X^k$ you can recover LFSR sequences of a smaller polynomial $Q(Y) = P(X)$ (look at the output at intervals of $k$), and this implies that the period of the original sequence can't be maximal. Try and see.

It's not difficult to calculate (using Moebius inversion) the number of irreducible/primitive polynomials, and there turn out to be lots of them. There are also ways to test if a polynomial is irreducible (in general, to factor it) and whether it's primitive (this requires factorizing $2^{\deg P}-1$ and then becomes trivial). So in practice, you can just "do it yourself" - try several polynomials, and soon enough you'll hit upon a nice one.

  • 0
    Is there an example? Can you define what P(X) and GF(2) might look like?2010-10-30
  • 0
    GF(2) is the field with two elements. Examples of P(X) can be found in the Wikipedia article you mentioned.2010-10-31