Choosing Codes or sequences with excellent Auto-Correlation properties

Question

The Auto-Correlation function of Walsh-Hadamard codewords does not have a good characteristics.

It can have more than one peak and thus, the Walsh-Hadamard codes do not have the best spreading behavior or correlation property.

The cross-correlation function of the Walsh-Hadamard codewords can also be non-zero for a number of time shifts and unsynchronized users can interfere with each other.

My Questions:

Which other codes or sequences show :

1. A good auto-correlation attribute?
2. Good Cross-correlation Property ?

Answer 1

The magic search term might be Barker code

Answer 2

The answer depends on whether you are interested in cyclic or linear auto-correlation. If you have a sequence $s(i)$ on length $L$, so $i=0,1,\ldots,L_1$, then its cyclic auto-correlations are $$ \Theta(s,\tau)=\sum_{i=0}^{L-1}s(i)\overline{s(i+\tau)}, $$ where the addition $i+\tau$ is done modulo $L$. The cyclic auto-correlation comes to the fore, when you are trying to synchronize to a repeating signal $s$. A widely used construction here is the so called binary (i.e.$\pm1$) $m$-sequence. Their length is of the form $L=2^m-1$. They have the best possible cyclic auto-correlations in the sense that $\Theta(s,\tau)=L$, if $\tau\equiv0\pmod L$ and $\Theta(s,\tau)=-1$ otherwise. We can build several larger and large families with good auto- and cross-correlation properties by combining an $m$-sequences with all the cyclic shifts of its carefully chosen decimations. The best known example of this may be the Gold sequences of $L=2^{10}-1$ that are used in tracking the distance to the family of satellites in GPS - each satellite has its own characteristic $s$, so good cross-correlation ensures that a GPS device can tell one satellite from another. There a single component of $s$ is a radio wawe of duration about $10^{-6}$ seconds, so we get 300 meter (=1000ft) difference in distance between $\tau$ and $\tau\pm1$ (in practice you can get an even better resolution by getting lock down to, say, one tenth of a symbol duration).

This type of sequences are often also used as pseudorandom sequences, e.g. in scrambling codes in cellular transmission. They are an attractive choice here, because they can be generated on the fly with a very simple circuitry known as a linear feedback shift register (=LFSR).

If you are interested in linear autocorrelation, where, instead of repeating the sequence $s(i)$ periodically, it just ends, then you get correlation functions such as $$ \hat\Theta(s,\tau)=\sum_{i=0}^{L-\tau-1}s(i)\overline{s(i+\tau)}. $$ These are nastier to calculate. There are some celebrated constructions known as Barker-sequences, but IIRC they are few. If you increase the number of phases from two, then the situation improves.

For more information there is an entire chapter dedicated to sequences in the Handbook of Coding Theory.