Proposition 8.4: If the characteristic polynomial p(z) = cN + cN−1z + ··· + c1zN−1 + c0zN 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 2N − 1,|
|8.4b||Every N-tuple v = (v0, v1, …, vN−1) ≠ (0)N is a state s(t) of the LFSR for some t with 0 ≤ t < 2N − 1,|
|8.4c||The sum of two states s(t1) and s(t2) of the LFSR with 0 ≤ t1 < t2 < 2N − 1 is another state of the LFSR, and|
|8.4d||If 0 < τ < 2N − 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 ≤ t1 < t2 < 2N − 1 and LFSR states at these times are the same. If s(t1) = s(t2), then by Proposition 8.1b s(0) = s(t2 − t1), which contradicts the periodicity of the sequence of states s(t).
Proof of (8.4b): If the 2N-states s(0), s(1), …, s(2N − 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 ≤ t1 < t2 < 2N − 1, then
which implies ...