2
$\begingroup$

Calculation of a delay between two signals is generally done by finding the maximum in the cross-correlation of the two signals (in time domain): $$ \tau_{delay} = \arg\max_\limits{t}(f(t) \star g(t)) $$ A cross-correlation can be easily computed in the frequency domain by pointwise multiplication of the Fourier transform of one signal with the complex conjugate of the Fourier transform of the other signal: $$ f(t) \star g(t) = f^*(-t)*g(t)=\mathcal{F}\{F\}^*\cdot \mathcal{F}\{G\} $$

Now I wonder how I can compute the cross-correlation peak in the frequency domain, thus without the need of an inverse transform. I can imagine two easy cases:

  • The case for two sinusoidal signals seems trivial, as the (smallest) delay then agrees with the phase (divided by the angular frequency) of the Fourier component (of this pointwise multiplication) for the respective frequency.

  • This can be generalized to two identic signals with a fixed delay, as the (unwrapped) phase response equals then the angular frequency multiplied by the delay, for all Fourier components. To avoid ambiguities, let's assume that the delay is smaller than half the period of the highest frequency that is considered.

However, when the two signals are not exactly identic, I suppose some kind of "weighed sum/integration" should be taken of the phase response, where the weighting factor scales with the relative contribution of the respective frequency, i.e., with the magnitude of the respective Fourier component. However, I am not able to find the exact formula rigorously.

Some "internal brainstorming" that might lead to the solution: if we consider one of the two functions ($f$) as a "basis" function, and project the other signal ($g$) on this function, the result of this projection (inner product) should contain the delay we are looking for. I guess this is only possible if the "basis" is first constructed as the analytic representation of $f$, such that phase differences can be taken into account. I also think that this inner product should be conserved after Fourier transform.

$\endgroup$
  • $\begingroup$ Your opening premise is incorrect. Correlation and convolution are not the same thing. Correlations are a dot product of a delay. Convolutions are a dot product of the reverse of the second function. $\endgroup$ – Cedron Dawg May 3 '18 at 15:36
  • $\begingroup$ That is what I wrote I think: correlation of f and g is convolution of complex conjugate of the reverse of f with g. See also: en.wikipedia.org/wiki/Cross-correlation#Properties $\endgroup$ – BNJMNDDNN May 3 '18 at 15:42
  • $\begingroup$ I'm sorry, I got the wrong kind of star. $\endgroup$ – Cedron Dawg May 3 '18 at 16:16
3
$\begingroup$

Calculating a delay between two signals is not as simple as you described and it cannot be generalized as easily either.

  • The case for two sinusoidal signals seems trivial, as the delay then agrees with the phase (divided by the angular frequency) of the Fourier component (of this pointwise multiplication) for the respective frequency.

This is not true in the general case. Calculating the delay from a single sinusoidal component is inherently ambiguous because of the signal's periodic nature. For a single phase $\phi$, there are infinitely many valid delays $\tau$.

$$ \tau = \frac{2\pi \cdot n + \phi}{2\pi f}, n \in \mathbb{Z} $$

  • This can be generalized to two identic signals with a fixed delay, as the phase response equals then the angular frequency multiplied by the delay, for all Fourier components.

This isn't true either. As noted above, the phase response plus a multiple of 2π equals the angular frequency multiplied by the delay, for all Fourier components. Even worse, this is a different multiple for each Fourier component in the general case.

You want to find the delay $\tau$ that fulfills this equation for all Fourier components, or at least for most of them, if the signals are not exacly identical.

The inverse fourier transform solves this problem in a brute-force manner. For each candidate delay, it calculates how strong the measured phase response agrees with it. Just pick the maximum and you're done. There is no better algorithm for the general case because the problem is inherently ambiguous and many (or even all) solutions might agree equally strong. Obviously, there cannot be a method to calculate the solution of such a problem directly.

Things change if you want to calculate the delay with higher precision than one sample. You could just zero-pad the phase response before calculating the inverse fourier transform, but this is computationally inefficient. A better approach is to calculate a coarse solution first, using an unpadded inverse fourier transform and then refine it using Newton's algorithm. Newton's algorithm is perfecly fine here because

  • it never requires the calculation of a delay from a phase response (which would be ambiguous). You can get away with calculating agreement scores for a given phase response and a candidate delay.

  • convergence to a local maximum is perfectly fine if all you wanted to do is to refine the global maximum.

There is no non-brute-force algorithm to find the global maximum of an arbitrary function. You are trying to find the global maximum of the cross correlation function, so unless you can guarantee certain properties of the signals (such as convexity or the like) or you're happy with a local maximum, there will be no way around an inverse fourier transform.

$\endgroup$
  • $\begingroup$ Thanks for your answer. I slightly edited my question by stating that I am looking for the smallest correct delay for two sines (so we assume that the delay is smaller than half the period of the sine), and that we look at the unwrapped phase response in the general case (or, ideally, that the delay is smaller than half the period of the maximal frequency under consideration). I am still not completely convinced that there is no closed-form solution in the frequency domain for this case. $\endgroup$ – BNJMNDDNN May 3 '18 at 15:18
  • $\begingroup$ @BNJMNDDNN - If you can guarantee the delay to be smaller than half the maximal frequency under consideration (or you're happy with a local maximum if it is not), Newton's method is the way to go, as described in my answer. $\endgroup$ – Rainer P. May 3 '18 at 15:25
  • $\begingroup$ But how can you be sure that it is only possible in the time domain? The information that you need is somehow in the phase response I would think? $\endgroup$ – BNJMNDDNN May 4 '18 at 9:49
  • 1
    $\begingroup$ @BNJMNDDNN - Calculating the delay from the spectrum only is the same problem as finding the frequency of a signal of which only the time domain representation is known. For sine/dirac signals you can do that with a zero-crossing detection but in the general case you need to run it through a fft and find the maximum of the result. $\endgroup$ – Rainer P. May 4 '18 at 20:51
  • $\begingroup$ That's a good analogy... if it is one frequency, but not exactly a sine (due to some noise), I would take half the inverse of the mean distance between each two adjacent zero-crossings. Now we search for one delay, but due to noise the phase response is not exactly the delay times the angular frequency. So I would take an average of the phase, but I suppose then that it should be weighed by the magnitude response (because for large magnitudes, the SNR is higher and thus the phase more accurate), but I don't know how (linearly? quadratically? ...) $\endgroup$ – BNJMNDDNN May 5 '18 at 22:25

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.