Synchronization sequences

Synchronization sequence catalog (decision D29).

Free functions returning the classic synchronization sequences, each with its reference and its defining property (tested in tests/core/test_frames_sequences.py): Zadoff-Chu (LTE/NR PRACH), Schmidl & Cox (OFDM timing + CFO), Barker (802.11b), Golay pairs (802.11ad) and maximum-length sequences.

These sequences carry no information: they are chosen for a correlation property, which is what makes them detectable in noise after a single correlation with a locally stored replica. Each Signal Model below therefore states that property – not only the construction rule – and the doctest that follows computes it.

zadoff_chu(u: int, N: int) → ndarray

Zadoff-Chu (CAZAC) sequence of root \(u\) and length \(N\).

Signal Model

For an odd length \(N\), the sequence of root \(u\) is

\[x_u[n] = \exp\left(-j \pi u \frac{n(n+1)}{N}\right), \qquad n = 0, \dots, N-1\]

This is the odd-length convention; the even-length variant replaces \(n(n+1)\) by \(n^2\) and is not accepted here (odd \(N\) is enforced, see Raises).

CAZAC stands for constant amplitude, zero autocorrelation, the two properties that make the sequence a preamble. Writing the periodic (cyclic) correlation of two roots as

\[\theta_{uv}[k] = \sum_{n=0}^{N-1} x_u[n] \, x_v^*[(n + k) \bmod N],\]

the sequence satisfies, whenever \(\gcd(u, N) = 1\),

\[\left|x_u[n]\right| = 1 \quad \forall n, \qquad \theta_{uu}[k] = N \, \delta[k]\]

– unit modulus (so the peak-to-average power ratio is 1 and no amplifier back-off is wasted on the preamble), and a periodic autocorrelation that is exactly zero at every nonzero lag, not merely small. Two distinct roots with \(\gcd(|u - v|, N) = 1\) are in addition maximally separated: their cross-correlation has constant magnitude

\[\left|\theta_{uv}[k]\right| = \sqrt{N} \quad \forall k, \qquad \text{i.e.} \quad \frac{\left|\theta_{uv}[k]\right|}{N} = \frac{1}{\sqrt{N}}\]

once normalized by the sequence energy \(N\). A single correlation therefore both locates the sequence and identifies its root, which is why cell search in LTE (PSS) and 5G-NR, and the random-access preambles (PRACH) of both, are built from Zadoff-Chu sequences.

Axes: element-wise – generator: each sample is a closed-form function of its index; the output is 1-D of length N.

param u:

Root index \(u\), coprime with \(N\). Distinct roots give the low, flat cross-correlation floor above.

type u:

int

param N:

Sequence length \(N\), odd.

type N:

int

returns:

np.ndarray – Complex sequence \(x_u[n]\) of length \(N\), unit modulus.

raises ValueError:

If \(N\) is even, or if \(\gcd(u, N) \neq 1\) (the autocorrelation property does not hold otherwise).

References

D. C. Chu, “Polyphase codes with good periodic correlation properties,” IEEE Trans. Inf. Theory 18(4), pp. 531-532, 1972; usage in 3GPP TS 36.211 (LTE) and 3GPP TS 38.211 (5G-NR).

Examples

>>> x = zadoff_chu(25, 139)
>>> print(round(float(np.max(np.abs(np.abs(x) - 1))), 12))  # constant amplitude
0.0
>>> theta = np.array([abs(np.vdot(x, np.roll(x, k))) for k in range(139)])
>>> print(round(float(theta[0]), 9), round(float(np.max(theta[1:])), 9))
139.0 0.0
>>> y = zadoff_chu(34, 139)  # a second root, |u - v| = 9 coprime with 139
>>> c = np.array([abs(np.vdot(x, np.roll(y, k))) for k in range(139)])
>>> print(round(float(np.max(np.abs(c - np.sqrt(139)))), 9))  # flat, = sqrt(N)
0.0

schmidl_cox_preamble(N_fft: int, seed: int | None = None) → ndarray

Schmidl & Cox OFDM preamble (two identical time-domain halves).

Signal Model

Unit-power QPSK symbols \(c[k]\) are placed on the even subcarriers of an \(N\)-point OFDM symbol, the odd ones being left empty:

\[\begin{split}X[k] = \begin{cases} \sqrt{2}\, c\!\left[k/2\right], & k \text{ even} \\ 0, & k \text{ odd} \end{cases} \qquad x[n] = \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} X[k] \, e^{\,j 2 \pi k n / N}\end{split}\]

the \(\sqrt{2}\) restoring unit average power \(\mathbb{E}\left[|x[n]|^2\right] = 1\) on the half-filled grid. Because only even \(k\) contribute, every exponential is \(N/2\)-periodic and the preamble consists of two identical halves:

\[x\!\left[n + N/2\right] = x[n], \qquad n = 0, \dots, N/2 - 1\]

This is the structure the Schmidl & Cox synchronizer exploits. On the received signal \(y[n]\) the metric

\[P(d) = \sum_{m=0}^{N/2-1} y^*[d+m] \, y\!\left[d+m+N/2\right], \qquad M(d) = \frac{\left|P(d)\right|^2} {\left(\sum_{m=0}^{N/2-1} \left|y\!\left[d+m+N/2\right]\right|^2\right)^2}\]

reaches its plateau \(M(d) = 1\) when the window \(d\) is aligned with the preamble – that gives the timing. A carrier frequency offset of \(\varepsilon\) subcarrier spacings turns the repetition into \(y[n + N/2] = y[n] e^{\,j \pi \varepsilon}\), so the same quantity also gives the CFO:

\[\hat{\varepsilon} = \frac{\angle P(\hat{d})}{\pi}, \qquad \left|\varepsilon\right| < 1\]

one correlation delivering both estimates.

Axes: element-wise – generator: returns a 1-D preamble of length N_fft.

param N_fft:

FFT size \(N\) (even, so that the two halves have equal length).

type N_fft:

int

param seed:

Seed of the RNG drawing the QPSK symbols \(c[k]\). Fix it to make the preamble reproducible between transmitter and receiver.

type seed:

int, optional

returns:

np.ndarray – Time-domain preamble \(x[n]\) of length \(N\), of unit average power, with \(x[n + N/2] = x[n]\).

raises ValueError:

If N_fft is odd.

References

T. M. Schmidl, D. C. Cox, “Robust frequency and timing synchronization for OFDM,” IEEE Trans. Commun. 45(12), pp. 1613-1621, 1997; R. van Nee, R. Prasad, OFDM for Wireless Multimedia Communications, Artech House, 2000, Chapter 4.

Examples

>>> x = schmidl_cox_preamble(64, seed=1)
>>> print(round(float(np.max(np.abs(x[32:] - x[:32]))), 12))  # x[n + N/2] = x[n]
0.0
>>> eps = 0.25  # CFO of a quarter subcarrier spacing
>>> y = x * np.exp(2j * np.pi * eps * np.arange(64) / 64)
>>> P = np.vdot(y[:32], y[32:])  # Schmidl & Cox metric, window aligned (d = 0)
>>> M = abs(P) ** 2 / float(np.sum(np.abs(y[32:]) ** 2)) ** 2
>>> print(round(M, 12), round(float(np.angle(P) / np.pi), 12))  # timing, then CFO
1.0 0.25

barker(length: int) → ndarray

Barker code of the given length.

Signal Model

A Barker code is a binary sequence \(x[n] \in \{-1, +1\}\) of length \(N\) whose aperiodic autocorrelation

\[R_x[k] = \sum_{n} x[n] \, x[n + k], \qquad k = -(N-1), \dots, N-1\]

(the sum running over the overlapping samples, so no cyclic extension) has all its sidelobes bounded by one:

\[R_x[0] = N, \qquad \left|R_x[k]\right| \leq 1 \quad \forall k \neq 0\]

This is the best possible sidelobe level for a binary sequence, and the reason the aperiodic – rather than periodic – autocorrelation is the relevant one: a packet preamble is transmitted once, so the receiver correlates over a partial overlap at every trial lag. A merit factor \(N^2 / (2 \sum_{k \neq 0} R_x[k]^2)\) that grows with \(N\) is what makes the peak detectable in noise.

Only a finite set of lengths is known – this implementation provides \(N \in \{2, 3, 4, 5, 7, 11, 13\}\). No longer Barker code exists for odd \(N > 13\), and none is conjectured to exist for any \(N > 13\). The length-11 code is the DSSS spreading sequence of 802.11b; the length-13 code is the classic radar pulse compression code.

Axes: element-wise – generator: returns a 1-D bipolar sequence of length length.

param length:

Code length \(N\), one of {2, 3, 4, 5, 7, 11, 13}.

type length:

int

returns:

np.ndarray – Integer array \(x[n] \in \{-1, +1\}\) of length \(N\).

raises ValueError:

If no Barker code of the requested length is tabulated.

References

R. H. Barker, “Group synchronizing of binary digital systems,” in Communication Theory, W. Jackson (ed.), Academic Press, 1953, pp. 273-287; J. G. Proakis, M. Salehi, Digital Communications, 5th ed., McGraw-Hill, 2008 (spread-spectrum signalling); IEEE 802.11-2020, clause 15.4.4.4 (length 11).

Examples

>>> code = barker(7)
>>> print(code)
[ 1  1  1 -1 -1  1 -1]
>>> R = np.correlate(code, code, "full")  # aperiodic autocorrelation
>>> print(R)
[-1  0 -1  0 -1  0  7  0 -1  0 -1  0 -1]
>>> print(int(np.max(np.abs(np.delete(R, 6)))))  # every sidelobe bounded by 1
1

golay_pair(length: int) → tuple[ndarray, ndarray]

Complementary Golay pair \((a, b)\) of the given length.

Signal Model

Two bipolar sequences \(a[n], b[n] \in \{-1, +1\}\) of length \(N\) form a complementary pair when their aperiodic autocorrelations

\[R_a[k] = \sum_{n} a[n] \, a[n + k], \qquad R_b[k] = \sum_{n} b[n] \, b[n + k]\]

cancel each other everywhere except at the origin:

\[R_a[k] + R_b[k] = 2 N \, \delta[k]\]

Neither sequence has small sidelobes on its own – it is their sum that is a perfect impulse. Correlating the received signal with both replicas and adding the two outputs therefore removes the sidelobes exactly, at any length, where a Barker code only bounds them by one and stops at \(N = 13\). This is what makes Golay pairs the channel-estimation fields of 802.11ad/ay and of many radar waveforms.

The pair is built by the standard recursive doubling, starting from \(a_0 = b_0 = [1]\):

\[a_{m+1} = \left[a_m, \; b_m\right], \qquad b_{m+1} = \left[a_m, \; -b_m\right]\]

which preserves complementarity and doubles the length at each step, hence the restriction to powers of two.

Axes: element-wise – generator: returns two 1-D sequences of length length.

param length:

Sequence length \(N\), a power of two.

type length:

int

returns:

tuple of np.ndarray – The pair \((a[n], b[n])\), each of length \(N\) with values in \(\{-1, +1\}\).

raises ValueError:

If length is not a positive power of two.

References

M. J. E. Golay, “Complementary series,” IRE Trans. Inf. Theory 7(2), pp. 82-87, 1961; IEEE 802.11ad-2012, clause 21.11.

Examples

>>> a, b = golay_pair(8)
>>> print(np.correlate(a, a, "full"))  # sidelobes are large on their own
[ 1.  0.  1.  0.  3.  0. -1.  8. -1.  0.  3.  0.  1.  0.  1.]
>>> print(np.correlate(b, b, "full"))  # and opposite in the partner
[-1.  0. -1.  0. -3.  0.  1.  8.  1.  0. -3.  0. -1.  0. -1.]
>>> print(np.correlate(a, a, "full") + np.correlate(b, b, "full"))  # 2N delta[k]
[ 0.  0.  0.  0.  0.  0.  0. 16.  0.  0.  0.  0.  0.  0.  0.]

m_sequence(degree: int, seed_state: Iterable[int] | None = None) → ndarray

Maximum-length sequence from a degree-\(m\) LFSR.

Signal Model

A linear-feedback shift register of degree \(m\) produces the binary recursion

\[b[n] = \bigoplus_{i \in \mathcal{T}} b[n - i] \qquad (\text{modulo } 2)\]

where the tap set \(\mathcal{T}\) is that of a primitive polynomial \(g(D) = 1 + \sum_{i \in \mathcal{T}} D^{i}\) of degree \(m\) (tabulated here for \(m = 2, \dots, 10\)). The output is mapped to a bipolar sequence

\[x[n] = 1 - 2 \, b[n] \in \{-1, +1\}\]

Primitivity is what makes the register visit every nonzero state exactly once before repeating, so the period is maximal:

\[N = 2^m - 1\]

Two properties follow, and they are the reason m-sequences are used as spreading and ranging codes. First the balance property: one period contains \(2^{m-1}\) ones and \(2^{m-1} - 1\) zeros, hence \(\sum_{n=0}^{N-1} x[n] = -1\) – a nearly zero-mean, noise-like waveform. Second, the periodic autocorrelation takes only two values:

\[\begin{split}\theta_x[k] = \sum_{n=0}^{N-1} x[n] \, x[(n + k) \bmod N] = \begin{cases} N, & k \equiv 0 \pmod N \\ -1, & \text{otherwise} \end{cases}\end{split}\]

a single sharp peak over a floor at \(-1/N\) of the peak, which is why a receiver can acquire code phase by sliding correlation and why the sequence behaves, spectrally, almost like white noise.

Axes: element-wise – generator: returns one 1-D period of length \(2^m - 1\).

param degree:

LFSR degree \(m\), from 2 to 10; the primitive polynomial \(g(D)\) (hence the tap set \(\mathcal{T}\)) is built in.

type degree:

int

param seed_state:

Initial register state, a nonzero binary word of length \(m\). Only the phase of the sequence depends on it, not its properties. Default: all ones.

type seed_state:

iterable of int, optional

returns:

np.ndarray – One full period \(x[n] \in \{-1, +1\}\) of length \(N = 2^m - 1\).

raises ValueError:

If degree has no tabulated primitive polynomial, or if seed_state is not a nonzero word of length \(m\).

References

S. W. Golomb, Shift Register Sequences, Holden-Day, 1967 (Chapters 3-4: randomness postulates and the two-valued autocorrelation); J. G. Proakis, M. Salehi, Digital Communications, 5th ed., McGraw-Hill, 2008 (PN sequences in spread spectrum).

Examples

>>> x = m_sequence(4)
>>> print(x)
[-1 -1 -1 -1  1  1  1 -1  1  1 -1 -1  1 -1  1]
>>> theta = [int(np.dot(x, np.roll(x, k))) for k in range(15)]
>>> print(theta)  # two-valued: N at lag 0, -1 at every other lag
[15, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
>>> int(np.sum(x == 1)), int(np.sum(x == -1)), int(np.sum(x))  # balance
(7, 8, -1)