2
$\begingroup$

As far as I understand the math you can reverse a real valued signal by Fourier transformation, taking the complex conjugate of the result and inverse Fourier transformation, i.e. \begin{equation} \tag{1} f(-x) = \mathcal{F}^{-1}(\overline{\mathcal{F}(f(x))}) \end{equation} where $\mathcal{F}$ is the fourier transformation operation and the overline denotes complex conjugation. This all makes sense and from a mathematical perspective this isn't very useful. However, from a DSP perspective its very useful because the autocorrelation of a signal can be conveniently cast as the convolution of a signal with a time-reversed version of itself. If you're using an FFT convolution it means that you only have to calculate one FFT of the signal.

When I tried to confirm that equation (1) was working in python I found that the result is shifted by one sample. Here's the example code:

import numpy as np
from numpy.fft import rfft, irfft
x = np.arange(128)
y = np.sin(2 * np.pi * x / 128 * 4 + np.pi / 3)
y_rev = y[::-1]
y_rev_fft = irfft(conj(rfft(y)))
plt.plot(y, label="Original Signal")
plt.plot(y_rev, label="Straight Reverse")
plt.plot(y_rev_fft, label="FFT Reverse")

FFT Conjugation Reversal

Is this the expected result? If so, can the conjugate still be used in the FFT correlation algorithm I described?

Also, is this question better suited to another stackexchange site?

$\endgroup$
  • $\begingroup$ Involves FFT and in some sense not a programming question so DSP seems like a good site. $\endgroup$ – Olli Niemitalo Oct 26 '16 at 12:19
0
$\begingroup$

Try plotting the signal and the straight reversed signal in points rather than lines and you will see that, unlike with reversal via FFT, none of the values stay the same throughout the reversal. The straight reversal flips the 128-long data around index 63.5 or equivalently around index -0.5 if you think of the data as periodic with a period of 128, rather than around index 0 (or 64) as in reversal via FFT.

According to user David Hoffman's tests both

roll(irfft(conj(rfft(y))*rfft(y)), -1)

and

irfft(rfft(y[::-1])*rfft(y))

work for autocorrelation, roll being numpy circular shift.

$\endgroup$
  • $\begingroup$ So is it then still correct to use conjugation when calculating the correlation or autocorrelation? $\endgroup$ – David Hoffman Oct 26 '16 at 12:49
  • $\begingroup$ Certainly! You will still cover all integer time shifts in the auto/correlation calculation, no matter which one of the two ways you used to reverse the data. $\endgroup$ – Olli Niemitalo Oct 26 '16 at 12:59
  • $\begingroup$ Ok, but the outputs of the two methods won't be identical. For instance: allclose(irfft(conj(rfft(y))*rfft(y)), irfft(rfft(y[::-1])*rfft(y))) returns False. The two are shifted by 0.5 samples as before. Do I need to be wary of this difference in my computations? $\endgroup$ – David Hoffman Oct 26 '16 at 14:13
  • 1
    $\begingroup$ Yup, circular shift left 1. $\endgroup$ – David Hoffman Oct 26 '16 at 19:01
  • 1
    $\begingroup$ allclose(roll(irfft(conj(rfft(y))*rfft(y)), -1), irfft(rfft(y[::-1])*rfft(y))) is True roll being numpy for circular shift. $\endgroup$ – David Hoffman Oct 27 '16 at 0:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.