The Radar Ambiguity Function - MATLAB Simulations for Radar Systems Design - page 216

Given an n-stage shift register generator, one would be interested in knowing
how many feedback connections will yield maximal length sequences. Zierler 1
showed that the number of maximal length sequences possible for a given n-
stage linear shift register generator is given by

ϕ 2 n

( – 1 )

N L = -----------------------

(4.52)

n

where is the EulerÓs totient (or EulerÓs phi) function. EulerÓs phi function is
defined by

ϕ

( p i – 1 )

∏

ϕ () k = ------------------ (4.53)

p i

i

where are the prime factors of . Note that when has multiples, then
only one of them is used (see example in Eq. (4.56)). Also note that when

p i k p i

k is

a prime number, then the EulerÓs phi function is

ϕ () k = – 1

(4.54)

For example, a 3-stage shift register generator will produce

ϕ 2 3

( – 1 ) ϕ ()

3

71 –

3

N L = ----------------------- = ----------- = ------------ = 2

(4.55)

3

and a 6-stage shift register,

ϕ 2 6 63

6

( 31 – ) ( 71 – )

( – 1 ) ϕ 6()

6

------ ---------------- ----------------

N L = ----------------------- = -------------- = × × = 6

(4.56)

6 3 7

Maximal Length Sequence Characteristic Polynomial

Consider an n-stage maximal length linear shift register whose feedback
connections correspond to . This maximal length shift register can
be described using its characteristic polynomial defined by

nkmetc ,, ,

x n x k x m

++++ … 1

(4.57)

where the additions are modulo 2. Therefore, if the characteristic polynomial
for an n-stage shift register is known, one can easily determine the register
feedback connections and consequently deduce the corresponding maximal
length sequence. For example, consider a 6-stage shift register whose charac-
teristic polynomial is

1. Zierler, N., Several Binary-Sequence Generators , MIT Technical Report No. 95,
Sept. 1955.