Autocorrelation

Given a signal $ x[n] $ and its reverse

$xrev[n] = x[N - n - 1]$

The autocorrelation is defined to be the convolution $x[n]*xrev[n]$

$DFT(x) = X[k] = a + bi$

$DFT(xrev) = X^*[k] = a - bi$

$(a+bi)(a-bi) = a^2 + b^2$

$DFT(x*xrev[n]) = |X[k]|^2$

In [8]:
import numpy as np
import matplotlib.pyplot as plt
t = np.linspace(0, 20*np.pi, 1000)
x = np.sign(np.sin(t))
x = np.concatenate((x, np.zeros(len(x))))
X = np.fft.fft(x)
XPow = np.real(X)**2 + np.imag(X)**2
xacorr = np.fft.ifft(XPow)
plt.subplot(211)
plt.plot(x[0:1000])
plt.subplot(212)
plt.plot(xacorr[0:1000])

/home/ctralie/anaconda3/lib/python3.7/site-packages/numpy/core/_asarray.py:85: ComplexWarning: Casting complex values to real discards the imaginary part
  return array(a, dtype, copy=False, order=order)
Out[8]:
[<matplotlib.lines.Line2D at 0x7ff152b8f2d0>]
In [ ]: