## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

## 8.5 PROPERTIES OF MAXIMAL LENGTH LFSR SEQUENCES

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(t2t1), 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 ...

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required