In order for a particular LFSR to be a maximal-period LFSR, the polynomial formed from a tap sequence plus the constant 1 must be a primitive polynomial mod 2. The degree of the polynomial is the length of the shift register. A primitive polynomial of degree n is an irreducible polynomial that divides x^2n-1 + 1, but not x^d + 1 for any d that divides 2ⁿ - 1 (see Section 11.3). For the mathematical theory behind all this, consult [643,1649,1648].

Figure 16.3  4-bit LFSR.

In general, there is no easy way to generate primitive polynomials mod 2 for a given degree. The easiest way is to choose a random polynomial and test whether it is primitive. This is complicated—something like testing random numbers for primality—but many mathematical software packages do this. See [970,971] for some methods.

Table 16.2 lists some, but by no means all, primitive polynomials mod 2 of varying degrees [1583,643,1649,1648,1272,691]. For example, the listing (32, 7, 5, 3, 2, 1, 0) means that the following polynomial is primitive modulo 2:

x³² + x⁷ + x⁵ + x³ + x² + x + 1

It’s easy to turn this into a maximal-period LFSR. The first number is the length of the LFSR. The last number is always 0 and can be ignored. All the numbers, except the 0, specify the tap sequence, counting from the left of the shift register. That is, low degree terms in the polynomial correspond to taps near the left-hand side of the register.

To continue the example, the listing (32, 7, 5, 3, 2, 1, 0) means that if you take a 32-bit shift register and generate the new bit by XORing the thirty-second, seventh, fifth, third, second, and first bits together (see Figure 16.4), the resultant LFSR will be maximal length; it will cycle through 2³² - 1 values before repeating.

The C code for this LFSR looks like:

int LFSR () {
     static unsigned long ShiftRegister = 1;
     /* Anything but 0. */
     ShiftRegister = ((((ShiftRegister >> 31)
                ^ (ShiftRegister >> 6)
                ^ (ShiftRegister >> 4)
                ^ (ShiftRegister >> 2)
                ^ (ShiftRegister >> 1)
                ^ ShiftRegister))
                & 0×00000001)
                << 31)
                | (ShiftRegister >> 1) ;
     return ShiftRegister & 0×00000001;
}

Figure 16.4  32-bit long maximal-length LFSR.