# Fast Cross Correlation and Time Series Synchronization in Python

Computing the cross-correlation function is useful for finding the time-delay offset between two time series. Python has the numpy.correlate function. But there is a much faster FFT-based implementation. Check out the following paper for an application of this function:

[bibtex file=lanes.bib key=fridman2015sync]

```import numpy as np
from numpy.fft import fft, ifft, fft2, ifft2, fftshift

def cross_correlation_using_fft(x, y):
f1 = fft(x)
f2 = fft(np.flipud(y))
cc = np.real(ifft(f1 * f2))
return fftshift(cc)

# shift < 0 means that y starts 'shift' time steps before x # shift > 0 means that y starts 'shift' time steps after x
def compute_shift(x, y):
assert len(x) == len(y)
c = cross_correlation_using_fft(x, y)
assert len(c) == len(x)
zero_index = int(len(x) / 2) - 1
shift = zero_index - np.argmax(c)
return shift
```

We can test the above function by shifting the second series manually and seeing if the shift is accurately computed:

```for n in range(1000, 1050, 7):
for s in range(-5, 5):
a = [random.random() for _ in xrange(n)] # big random sequence of values
b = a
if s >= 1:
a = a[s:]
b = b[:-s]
elif s <= -1:
a = a[:s]
b = b[-s:]

assert s_optimal == s
```