## 8.5 PROPERTIES OF MAXIMAL LENGTH LFSR SEQUENCES

**Proposition 8.4:** If the characteristic polynomial *p*(*z*) = *c*_{N} + *c*_{N−1}*z* + ··· + *c*_{1}*z*^{N−1} + *c*_{0}*z*^{N} of an *N*-stage LFSR is primitive and the initial state is not null *s*(0) ≠ (0)_{N}, then

**8.4a** |
The sequence of states *s*(0), *s*(1), … are distinct and periodic with period 2^{N} − 1, |

**8.4b** |
Every *N*-tuple *v* = (*v*_{0}, *v*_{1}, …, *v*_{N−1}) ≠ (0)_{N} is a state *s*(*t*) of the LFSR for some *t* with 0 ≤ *t* < 2^{N} − 1, |

**8.4c** |
The sum of two states *s*(*t*_{1}) and *s*(*t*_{2}) of the LFSR with 0 ≤ *t*_{1} < *t*_{2} < 2^{N} − 1 is another state of the LFSR, and |

**8.4d** |
If 0 < *τ* < 2^{N} − 1, the sequence of sums of states |

is a translate of the state sequence *s*(0), *s*(1), …, that is *s*(*t* + *s*) = *s*(*t*) + *s*(*t* + *τ*) for some *s.*

*Proof of (***8.4a**): Suppose on the contrary that 0 ≤ *t*_{1} < *t*_{2} < 2^{N} − 1 and LFSR states at these times are the same. If *s*(*t*_{1}) = *s*(*t*_{2}), then by Proposition **8.1b** *s*(0) = *s*(*t*_{2} − *t*_{1}), which contradicts the periodicity of the sequence of states *s*(*t*).

*Proof of* **(8.4b):** If the 2^{N}-states *s*(0), *s*(1), …, *s*(2^{N} − 1) are distinct and *s*(*t*) ≠ (0)_{N}, then every *N*-tuple other than (0)_{N} must be a state of the LFSR.

*Proof of ***(8.4c):** If

with 0 ≤ *t*_{1} < *t*_{2} < 2^{N} − 1, then

which implies ...