## 8.4 THE CHARACTERISTIC POLYNOMIAL OF A LINEAR FEEDBACK SHIFT REGISTER

The *characteristic polynomial* of the *N*-stage LFSR with recursion

and feedback coefficients {*c*_{i}} is

We will always assume *c*_{0} = *c*_{N} = 1.

*Example 8.3*

The LFSR with characteristic polynomial *p*(*z*) = 1 + *z* + *z*^{2} + *z*^{3} is shown in Figure 8.3. As *p*(*z*) does not divide 1 + *z*^{k} for *k* = 1, 2, 3 and (1 + *z*)*p*(*z*) = 1 + *z*^{4}, the exponent of *p*(*z*) is 4. Table 8.5 gives the output and states of this LFSR for three different initial states. Table 8.5 illustrates that the period of the sequence *s*_{0}(0), *s*_{0}(1), *s*_{0}(2), … depends on the initial state *s*(0):

*s*(0) = (0, 0, 1) produces a sequence of period 3,
*s*(0) = (1, 0, 1) produces a sequence of period 2, and
*s*(0) = (1, 1, 1) produces a sequence of period 1.

**Proposition 8.3:** [Beker and Piper, 1982, pp. 192–193] If *p*(*z*) = *c*_{N} + *c*_{N−1}*z* + ··· + *c*_{1}*z*^{N−l} + *c*_{0}*z*^{N} is the characteristic polynomial of the LFSR, then

**8.3a** |
The period of the output sequence *s*_{0}(0), *s*_{0}(1), *s*_{0}(2), … is a divisor of the exponent of *p*(*z*), and |

**8.3b** |
If the initial state *s*(0) ≠ (0)_{N}, the period of the output sequence *s*_{0}(0), *s*_{0}(1), *s*_{0}(2), … is 2^{N} − 1 if and only if *p*(*z*) is primitive. |

*Example 8.4*

The LFSR with characteristic polynomial *p*(*z*) = 1 + *z* + *z*^{3} is shown in Figure 8.4. The exponent of *p*(*z*) was shown to be ...