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$
1
  • $\begingroup$ Involves FFT and in some sense not a programming question so DSP seems like a good site. $\endgroup$ Oct 26, 2016 at 12:19

1 Answer 1

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$
7
  • $\begingroup$ So is it then still correct to use conjugation when calculating the correlation or autocorrelation? $\endgroup$ Oct 26, 2016 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$ Oct 26, 2016 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$ Oct 26, 2016 at 14:13
  • 1
    $\begingroup$ Yup, circular shift left 1. $\endgroup$ Oct 26, 2016 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$ Oct 27, 2016 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.