The Schmidl & Cox Synchronization Technique for OFDM¶

tl;dr: Given some received OFDM signal like the following, how can one know at which point in time the OFDM symbols are located? Or, equivalently, on which signal part the receiver needs to perform the FFT?

In the OFDM example, we have described the OFDM modulation and demodulation, including channel estimation and CP insertion. On the significance of the CP we have already elaborated in another article. However, in all these works, we have assumed that the receiver knows, at which point in time the OFDM symbol is received and hence on which received samples to perform the FFT.

However, in reality this information is not available by default. Instead, the receiver needs to perform a synchronization procedure to obtain the start of the OFDM symbol. When talking about OFDM, the most fundamental work was published by Timothy Schmidl and Donald Cox in their paper Robust Frequency and Timing Synchronization for OFDM. In this notebook, we are going to illustrate their algorithm presented in this paper concerning the estimation of the frame start in the time domain. In addition, the authors propose a method for frequency offset estimation, which we silently ignore in the present description.

So, to summarize, here's the task of synchronization:

Given a received OFDM signal, how can we obtain knowledge about where in the signal the OFDM symbols are located?

In what follows we will describe the proposal by Schmidl&Cox and implement this algorithm for timing synchronization. However, before we dive into the implementation, we need to setup the system model.

System Model and Frame Structure¶

Mathematically, in this notebook we describe the received signal $r(t)$ by a delayed and noisy version of the transmitted signal $x(t)$:

$$ r(t) = x(t-\tau)+n(t)$$

where $\tau$ is the delay and $n(t)$ is AWGN. $\tau$ is unknown at the receiver and needs to be estimated.

Schmidl and Cox propose a synchronization algorithm that bases on an OFDM symbol that has a special structure. In particular, the special symbol, denoted as the preamble, consists of two repeated parts, prepended by a cyclic prefix (CP). As such, in this notebook, we will employ the following overall frame structure:

Each frame starts with a preamble which consists of two repeated parts, denoted by $A$. Subsequently, there will be $N$ OFDM symbols following containing the payload information. Note that in the Schmidl and Cox proposal, also the preamble can contain information, as the part $A$ can be arbitrary. The only criterion is that the part is repeated twice.

Modeling the received signal¶

To implement the synchronization algorithm, let us first generate an appropriate receive signal. We start with a dummy structure which holds all the OFDM parameters:

Moreover, let's define a function for generating random QAM symbols:

Now, we define a function to perform OFDM modulation and CP insertion:

Now, let's generate an example preamble. To generate two repetitive parts, we exploit a property of the Fourier Transform: The DFT of a $P$-periodic sequence (i.e. a sequence consisting of $P$ repetions on one part), is non-zero only every $P$th sample. Hence, if we create a frequency domain signal with every other sample zero, the corresponding time-domain signal is 2-periodic:

Now, that we can create a preamble, let's write a function that creates one frame according to the structure defined earlier:

Let's plot the frame and annotate the symbol. For letting the preamble shine out, we amplify it a bit:

Now, let's define the channel, which we model with some functions:

We can try out these functions in the following:

Now that we can create a receive signal, we can implement the proposed synchronization algorithm. The algorithm is based on a metric which is calculated from the received signal. In short, when the metric goes beyond a certain threshold, the preamble is detected.

Calculating $P(d)$¶

In their paper, the authors propose the following metric $P(d)$ given by equation (5) as

$$ P(d) = \sum_{m=0}^{L-1}(r[d+m]^*r[d+m+L]) $$

which we can calculate directly:

As we see, the metric $P(d)$ shows a plateau starting at the timing offset. Moreover, the plateau has the width equal to the CP length. With this observation, it might be problematic to determine the exact start of the OFDM frame as no distinct peak occurs. However, by using the CP we explicitely allow to overcome slight timing offsets and subsequent channel estimation will recover the residual timing offset.

As an alternative calculation, Schmidl and Cox give a recursive method to calculate $P(d)$ by

$$ P(d+1) = P(d) + r[d+L]^*r[d+2L] - r[d]^*r[d+L] $$

which we can also implement directly. However, note that the starting point $P(0)$ still needs to be calculated in the standard way. Let's first check if both ways to calculate the metric are equal:

Unsurprisingly, both methods yield the same result. Let's see, what happens, if we set the initial condition to $P(0)=0$ to overcome the initial calculation of $P(0)$:

The curve marginally changes, however the general shape remains the same. To further formalize the calculation of $P(d)$ let us define the following signal $v[d]$ by

$$ v[d] = r[d+L]^*r[d+2L]$$

With this definition, we can rewrite the recursive calculation of $P(d)$ as

$$ P(d+1) = P(d) + v[d] - v[d-L], $$

which seemingly becomes a linear IIR filtering operation of $v[d]$. However, note that, unfortunately, $v[d]$ is not causal, as it depends on data from the future, namely on $r[d+L]$ and $r[d+2L]$. To make the system causal, we can introduce an artificial delay of $2L$ samples to $r[d]$ to yield $\bar{r}[n]=r[n-2L]$. Now, defining

$$ \bar{v}[d] = \bar{r}[d+L]^*\bar{r}[d+2L]=r[d-L]^*r[d]$$

we can find a causal version $\bar{P}(d)$ by

$$ \bar{P}(d+1) = \bar{P}(d) + \bar{v}[d] - \bar{v}[d-L] $$

which we can calculate by a standard IIR filter implementation:

Apparently, the filter has a delay of $2L$ samples compared to the non-causal (and hence not realizable) original implementation. Now, given that we have a linear IIR filter, it might be interesting to look at its impulse response:

The impulse response of the filter is a rect function of width of $L$ samples. This makes sense, looking at equation (5) in the original paper. But wait, ... didn't we just say we have an IIR (infinite impulse response) filter? Hm, let's have a look in more detail into the Z domain of the filter. Here, we simplify a bit and use the common $x[n]$ and $y[n]$ for input and output signals, respectively:

$$\begin{align} y[n] &= y[n-1] + x[n] - x[n-L] \\ Y(z)(1-z^{-1})&=X(z)(1-z^{-L})\\ H(z)&=\frac{Y(z)}{X(z)}=\frac{1-z^{-L}}{1-z^{-1}}\\ &=\frac{(1-z^{-1})(1+z^{-1}+z^{-2}+\dots+z^{-(L-1)}}{1-z^{-1}}=1+z^{-1}+z^{-2}+\dots+z^{-(L-1)}\end{align}$$

There, the last rows follows from the general rule $1-x^{-n}=(1-x)(1+x^{-1}+\dots+x^{-(n-1)})$. Hence, we see that the pole and zero at $z=1$ cancel out and hence leaves us with a FIR filter, which can still be implemented recursively.

Calculating $R(d)$¶

In addition to the autocorrelation metric $P(d)$, Schmidl and Cox propose to employ the receive energy $R(d)$ given by

$$R(d) = \sum_{m=0}^{L-1}|r[d+m+L]|^2 $$

which can again be calculated with steps similar to $P(d)$. In particular, the non-causal recursive version is given by

$$ R(d+1) = R(d) + |r[d+2L]|^2-|r[d+L]|^2 $$

and the corresponding causal version is given by

$$ \bar{R}(d+1) = \bar{R}(d) + |r[d]|^{2} - |r[d-L]|^{2}. $$

Let us compare their implementation:

Calculating the final metric $M(d)$¶

Finally, the authors propose to normalize the autocorrelation $P(d)$ with the receive energy $R(d)$, yielding the final metric $M(d)$ given by

$$ M(d) = \frac{|P(d)|^2}{R(d)^2}. $$

Let's look at this metric for our frame:

As shown, the original $M(d)$ reaches the maximum, when the preamble starts. However, this filter is non-causal, as it requires knowledge of the upcoming samples from the signal. The causal version $\bar{M}(d)$ has a delay of 2L samples but is practically realizable.

Evaluation of the metric magnitude¶

In their paper, the authors derive that the metric $M(d)$ evaluated at the correct timing (i.e. within the CP of the preamble) is Gaussian distributed, with mean $\mu$ and variance $\sigma^2$, which are given by

$$\begin{align} \mu &= \frac{\sigma_s^4}{(\sigma_s^2+\sigma_n^2)^2} & \text{equation (19)}\\ \sigma^2 &= \frac{2\sigma_s^4[(1+\mu)\sigma_s^2\sigma_n^2+(1+2\mu)\sigma_n^4]}{L(\sigma_s^2+\sigma_n^2)^4}&\text{equation (20)} \end{align}$$

where $\sigma_s^2$ is the preamble power and $\sigma_n^2$ is the noise power. With the relation of the SNR $\rho$ given by $$ \rho=\frac{\sigma_s^2}{\sigma_n^2}, \quad \sigma_n^2=\rho\sigma_s^2$$ we find these two equations to become

$$ \begin{align}\mu &= \frac{1}{(1+\rho)^2}\\ \sigma^2 &= \frac{2[(1+\mu)\rho+(1+2\mu)\rho^2]}{L(1+\rho)^4} \end{align}.$$

Let us verify this numerically. First, let's define a common function that calculates our metric $\bar{M}$. However, we already erase the first $L$ samples, as they contain largely garbage information:

Now, let's calculate the metric for different SNRs:

Finally, let's evaluate the results and compare against the theoretic values:

Apparently, the simulated and theoretic curves overlap. Moreover, the values coincide with Fig. 4 from the original reference.

Using $M(d)$ for synchronization¶

Given the metric $M(d)$, it still remains unclear how the metric shall be practically used for timing synchronization. We will explain this is the following. Intuitively, it's clear that whenever $M(d)$ goes beyond a certain threshold, a preamble was detected. However, given that the metric does not have a clear peak, but a plateau, some extra logic is necessary to detect the actual frames.

Consider a frame structure as previously. In addition, there can be arbitrary delay between frames to make timing synchronization more difficult. Let's first create a sample signal. For illustration purposes we also indicate where the preamble and where the payload symbols are located:

Now, let's create a signal consisting of 3 frames with some delays between them. We plot the signal and the corresponding genie-sync information.

Now, the task is to write a function that recreates the sync-info solely based on the received signal. To start out, let's calculate the our metric and plot it on top of the preamble_valid metric.

As visible in the zoomed-in version, the genie preamble-valid signal becomes true at the end of the plateau of the metric. Hence, we need to write an algorithm that detects the end of the plateau. We know, the plateau has a with of the size of the CP. One option to transform the plateau into a peak is to perform a matched filtering operation with a rectangle of the width of the plateau:

As shown, the filtering with a rectangle as two effects: First, it smooths out some noise, second it transforms the plateau into a peak, though the peak is not very pronounced. Let us now try to perform some peak detection on the green line. As known, a peak in a curve corresponds to a zero in its derivative. So, let's look at the derivative:

This looks good already! The derivative seems to have zeros where the preamble starts. Let's further investigate and detect the zero-crossings of the derivative. The zero-crossings of a signal are determined by a sign change of adjacent samples, hence the product of two adjacent samples should be negative:

Hm, there are a lot of erroneous zero-crossings detected. Sure, when the metric is small (i.e. there is no preamble), there is only noise on the preamble, and there a lot of zero-crossings happen. So, let's add another criterion: Detect the zero-crossings, where the metric goes beyond a certain threshold:

Ah, this looks much better. But, now let's zoom into one preamble start to examine a bit more in detail how the detected zero-crossings look:

Hm, there are multiple zero-crossings detected. This is clear, when looking at the derivative, as it indeed has multiple zero-crossings. Moreover, the position of the detected zero-crossings does not match exactly the expected position. Instead, the zero-crossings appear few samples before the correct starting point. However, this is not a problem as the OFDM symbol contains a CP and hence makes it robust against slight timing misalignments.

Let's try to remove the multiple peaks and just keep the first sample. The idea is to ignore all detected zero-crossings except the first one in a range of $K+CP$ samples:

Now, we delete all detected zero-crossings when the ignore-window is non-zero:

Now, we have extracted the first zero-crossing and hence extracted an estimate of the preamble start. As the final step, we need to extract the OFDM symbols and preamble from the received signal stream. Let's simply do this with a FIR filter describing the structure of the frame:

Great! Now, we have nicely extracted the OFDM payload symbols excluding the CP. The estimated frame position sufficiently matches the exact positions of the symbols. However, due to the CP, a slight timing offset is not problematic.

In a subsequent step, we would send these symbols to the OFDM demodulator and channel estimator, as described in e.g. the OFDM Example.

Summary¶

1. Synchronization in OFDM is necessary to detect the start of an OFDM frame, such that the FFT window can be located correctly.
2. For OFDM, the most basic algorithm is the Schmidl&Cox-Algorithm which bases on a synchronization sequence that consists of two repeated parts.
3. The synchronization algorithm calculates a metric which shows a plateau around the position of the preamble.
4. To implement a real OFDM synchronization, additional logic for plateau detection and preamble and payload extraction is necessary after the metric has been obtained successfully.