# Generating good synchronization sequences

As part of my work I am putting together a simple bursty BPSK communication system. I want to make the demodulation easy, so I am going to put a synchronization sequence at the beginning of each burst to help the receiver lock onto the frequency, phase, and timing.

In order to get good synchronization information and avoid false positives the autocorrelation of the synchronization sequence should be as close to a delta dirac as possible. There may also be additional constraints, like starting the sequence with all 1's to help the receiver get frequency lock quickly.

How does one go about generating such a sequence? Is there a systematic way of doing it, or do you use common sense and trial and error?

A synchronization sequence generally needs the property that its autocorrelation function resembles an impulse. There are two possible autocorrelation functions that can be considered. For a (real-valued) sequence $x$ of length $N$, the periodic autocorrelation function is $$R_x[n] = \sum_{k=0}^{N-1}x[k]x[k+n]$$ where the sequence is assumed to extend periodically so that $x[k+n] = x[k+n\bmod N]$. In this case, one commonly used solution to choose $x$ to be a maximal-length linear binary feedback shift-register (LFSR) sequence of period $N = 2^m-1$ whose periodic autocorrelation function is $$R_x[n] = \begin{cases} N, & n \equiv 0 \bmod N,\\ -1, & n \not\equiv 0 \bmod N, \end{cases}$$ which resembles an impulse train of period $N$ except that the "out-of-phase" value of the periodic autocorrelation function is not identically zero, but is small (and constant) compared to the "in-phase" value of $N$.
The other form of autocorrelation function is the aperiodic autocorrelation function which is given by $$C_x[n] = \begin{cases}\sum_{k=0}^{N-1-n}x[k]x[k+n], & 0 \leq n < N,\\ \sum_{k=0}^{N-1+n}x[k-n]x[k], & -N < n < 0,\\ 0, & |n| \geq N. \end{cases}$$ Now, for binary sequences where $x$ takes on values in $\{+1,-1\}$, the value of $C_x[n]$ alternates between even and odd integers as $n$ varies from $-(N-1)$ to $(N-1)$, and so a "flat" out-of-phase aperiodic autocorrelation function is impossible to achieve. The closest we can hope to come is to find sequences for which $|C_x[n]| \leq 1$ for $1\leq n < N$. Sequences with this property are called Barker sequences, and the longest known Barker sequence is of length $13$. it is widely believed, though not proven, that Barker sequences of longer lengths do not exist, and numerical studies show that if such a sequence exists, it it must be so long that it will not be be usable in any practical scheme as a synchronization preamble.
• Nice answer. I think in your $R_x[n]$ formula the top line should be n mod N equal to 0, and the bottom line should be n mod N not equal to 0. – Jim Clay Oct 10 '12 at 18:19