DSP: Arbitrary Precision Fractional Time Synchronization

Overview

This page will discuss an efficient arbitrary precision fractional time synchronization technique. The algorithm computes the fractional offset between two similar discrete real waveforms via post-processing.

Setup

Suppose that we have two discrete real waveforms \vec v = (a_0, a_1, ..., a_{N-1}) and \vec w = (b_0, b_1, ..., b_{N-1}), which represent two separate noisy samplings of the same source waveform. Assume that there exists a fractional offset (sampling time offset smaller than the sampling interval) between \vec v and \vec w.

Algorithm

The first step involves continuously interpolating the waveforms \vec v \mapsto v(t) and \vec w \mapsto w(t) such that v(k) = a_k and w(k) = b_k. One possible choice for the interpolator is the cubic spline interpolator, which connects the discrete sample points smoothly with a sequence of piecewise cubic polynomials. The corresponding set of piecewise cubic polynomial coefficients can be efficiently computed via the tridiagonal matrix algorithm (also known as Thomas algorithm) in linear time with respect to the length of the waveforms N. The values of the interpolators v(t) and w(t) will be defined to be 0 if t < 0 or N - 1 < t.

Next, pick a sufficiently large window size W>0 and consider the windowed cross-correlation:

\chi(s)=\int_0^W{v(t)w(s+t)}dt

The maximizer of the windowed cross-correlation corresponds to the fractional offset. In other words, the fractional offset can be retrieved by computing:

argmax_s{\chi(s)}

The value of \chi(s) can be numerically approximated via summation combined with Horner’s method for faster polynomial evaluation:

\chi(s)=\int_0^W{v(t)w(s+t)}dt \approx \sum_{k=0}^{W-1}{v(k \Delta t)w(s+k \Delta t)}\Delta t

There is a slightly more complicated, but more efficient, way of evaluating \chi(s) that also eliminates the approximation error. Note that v(\cdot) and w(\cdot) are chains of 3rd order polynomials, which imply that v(t)w(t+s) is a chain of 6th order polynomial. Therefore, \int_0^W{v(t)w(t+s)}dt can be viewed as a chain of 7th order polynomial evaluations, which can be efficiently computed individually via Horner’s method and summed to give the exact value of the integral.

The key observation to make is that \chi(s) should exhibit a symmetric convex-like behavior around the optimum amenable to the log-time optimization algorithm such as binary search. For improved stability, the search method could be replaced with an “N-ary” search, such that each iterative step involves the evaluation of N candidate interim optimum. Either method will allow the optimum to be searched in logarithmic time with respect to the precision.

Leave a comment