What are bit strings where all non-trivial rotations match at a minimum number of places called?

Question

Basically, I'm trying to figure out the name of the thing I want to look up. All the terms I've looked up so far have been related, but not close enough to be useful.

---

I'm trying to find bit strings where the auto-correlation between the string and some rotation of the string shows a clean maximum at the rotated-by-zero position. A little logic suggests that on average, bits will match at least half the time. Some brute force searching supports than and shows that (for some lengths: 2,3,4,5,6,7,11,13,15,19,23) it's possible to find strings that match at exactly the same number of position (usualy $\lceil n/2 \rceil$) for all non-trivial rotations. My application would benefit from longer strings than are tractable to brute force so I'm really hoping I can look up the theory behind these structures.

There are some other interesting properties and application I'm seeing that suggest this would be interesting to research, so I strongly suspect that someone has, but I've been unable to find anything so far.

Answer 1

Gold codes are not really what you are looking for as far as I understand. With Gold codes you have many sequences and you want to control (i.e., have small absolute values) for all nontrivial auto and cross correlations in the set. That's overkill for you, and the Welch bound implies that you cannot obtain the $\lceil n/2 \rceil$ Hamming distance between shifts that you require.

You have one binary sequence, say $(x_0,\ldots,x_{n-1})$ and the usual definition of (cyclic) autocorrelation is $$ \theta_{x}(\tau)=\sum_{0\leq k \leq n-1} (-1)^{x_t + x_{t+\tau}} $$ where the shift in the index is taken modulo $n.$ There is a one to one correspondence between the Hamming distance between a sequence and its cyclic shift and this correlation.

Clearly if $n$ is odd then this correlation is in the best case equal to $-1$ for nontrivial shifts.

---

For $n=2^m-1,$ you can use maximum length sequences obtained from the Galois field trace function to get what you want. Let $$ x_k=\mathrm{tr}(c \alpha^k),\quad c\neq 0, $$ where $\mathrm{tr}:GF(2^m)\rightarrow GF(2)$ is the trace map and $\alpha$ is a primitive element (of multiplicative order $2^m-1$) in $GF(2^m).$

---

For $n=p$, for some prime $p$ congruent to $3$ modulo 4 you can use the Legendre sequences to get the same correlation. Use the Legendre symbol as a multiplicative character which means map the quadratic residues in $GF(p)^\ast$ to $+1$ and the quadratic nonresidues to $-1$ with the zero element mapped to $+1$ as well.

Example: $N=7,$ the quadratic residues are $1,4,9\equiv 2\pmod 2,$ so you get the sequence $$ \begin{array}{c|rrrrrrr} k & 0 & 1 & 2& 3& 4 & 5& 6 \\ \hline x_k & +1 & +1 & +1 & -1 & +1 & -1& -1 \end{array} $$

---

Relevant keywords are m-sequences (maximum length sequences), Legendre sequences. For ranging applications m-sequences are used very widely in communications, Legendre sequences are used in the GPS system, as well as other places.

Finally, for $n=4,$ there is the circulant Hadamard sequence $(-1,+1,+1,+1)$ which gives perfect autocorrelation, but no longer examples are known and are believed not to exist.

Edit: For Barker codes and similar signal sets the relevant correlation is aperiodic correlation, given by $$ C_{x}(\tau)=\sum_{0\leq k \leq n-1-|\tau|} (-1)^{x_t + x_{t+\tau}},\quad |\tau|<n. $$