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.

  • $\begingroup$ I think I got what you are saying, but the question is whether there is a connection between $C(n)$ to $Z(n)$? $\endgroup$ – Mr.O Jun 5 '20 at 11:01
  • 1
    $\begingroup$ $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. $\endgroup$ – kodlu Jun 5 '20 at 11:16
  • $\begingroup$ 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$? $\endgroup$ – Mr.O Jun 7 '20 at 10:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.