# autocorrelation of non-linear shift register with the period of $2^n$ (full period)

throughout the question I will talk about sequences in bipolar alphabet, meaning, over {1,-1}.

I have read in the book Shift Register Sequences by Solomon W. Golomb that sequences with the period of $$2^n$$ can be created by pure cycling register of order n ($$PCR_n$$). Moreover, it gives some properties about the autocorrelation (that I also read in some papers): $$C(\tau)= \ \begin{cases} 2^n & \tau =0 \\ 0 & 0< \tau \le n-1 \\ \ne0 & \tau =n \end{cases}$$

Another statement (and that is where my question) is that $$C(n)$$ can bound by the number of cycles of the $$PCR_n$$ (we can denote the number of cycles as $$Z(n)$$)

Where this come from I don't really understand.

You have misunderstood Sol Golomb. A pure cycling register (PCR) of length $$n$$ generates a sequence of period $$n$$ and no longer period. It is physically impossible. It just cycles the loaded sequence of length $$n$$. The sequence it generates may have shorter minimal period, a divisor of $$n.$$

Take $$n=3$$ and keep shifting left as in a PCR.

$$000\rightarrow 000 \rightarrow 000$$ actually has minimal period 1. The same for the loading $$111.$$

$$001\rightarrow 010\rightarrow 100\rightarrow 001$$ has minimal period 3. Same with the loading $$011.$$

The PCR of length 3 has decomposed the space $$\{0,1\}^3$$ into four cycles. This is because the minimal periods add to the size of the state space: $$3+3+1+1=2^3$$

Now, he proves this is always the case for a PCR of length $$n$$ with respect to the state space $$\{0,1\}^n,$$ and since all this has to do with divisibility relates the number of cycles in the PCR decomposition of length $$n,$$ which he calls $$Z(n)$$ to the Euler totient $$\phi(n):$$ $$Z(n)=\sum_{d|n} \phi(d)2^{n/d}.$$

Now if you take a maximal length sequence of minimal period $$2^n-1$$ in the $$\pm 1$$ formulation and insert a +1, next to the unique run of +1 of length $$n-1$$ (remember +1 corresponds to 0 mod 2) this PCR decomposition applies. So your statement about $$C(\tau)$$ is I believe his Theorem 4, p.124, in the reprinted edition of the Aegean Park original.

The autocorrelations of the augmented sequence of period $$2^n$$ now have an extra term in the sum, and the peak $$C(0)=2^n,$$ is clear.

Since the way to augment this period is to add a degree $$n$$ term into the feedback function, and that term is active only once in the period, the autocorrelations at nonzero shifts where $$\tau \neq 0\pmod n$$ are now 0 instead of -1 for the $$2^n-1$$ period sequence due to this extra term.

What about when $$\tau=n$$? Well this won't be zero and getting a hold on its exact value is difficult for a general sequence of period $$2^n$$, the sequence of theorems 5 through 10 are used here to obtain it for the case that we have an augmented maximal length sequence.

• I think I got what you are saying, but the question is whether there is a connection between $C(n)$ to $Z(n)$? – Mr.O Jun 5 '20 at 11:01
• $Z(n)$ gets large pretty fast with $n$ while $C(n)$ is typically small as Golomb says. I don't know of any other results in this direction, I'll have a look and report if I find anything. – kodlu Jun 5 '20 at 11:16
• Maybe it is connected to the fact that DB(n,2) (de bruijn sequence of length $2^n$ over binary {1,0} or {1,-1}) is partitioned into cycles exctly by $PCR_n$? – Mr.O Jun 7 '20 at 10:08