1
$\begingroup$

I need to compute the complex cross-correlation between two signals a and b and the take only the maximum value of the cross-correlation, regardless of the lag time where this occurs. I can do it either in time domain or in frequency domain. This needs to be later incorporated in a FPGA, so I want to be efficient.

An alternative is to go to frequency domain correlation, but I would need to do

max(IFFT(FFT(a)*conj(FFT(b))))

which is probably computationally costly.

Is there a way to avoid going back and forth twice to the frequency and time domain?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ You need to limit the maximum time lag to some reasonable number and the best choice of algorithm depends on what this number is $\endgroup$
    – Hilmar
    Feb 23, 2022 at 16:39

1 Answer 1

Reset to default
2
$\begingroup$

Assuming $a$ and $b$ are of length $N$, the cross-correlation is calculated using the convolution operator which has complexity $O(Nm)$ for $m$ different lags (source), meaning the operation takes $N$ times $m$ real-valued multiplications. Addition is usually much faster than multiplication which is why it is typically ignored in Big O notation*. Going the frequency domain route requires three FFT/IFFT operations each with complexity $O(N \log_2 N)$ (source), and one element-wise complex product $O(3N)$ (the 3 comes from this reference). Summing these complexities results in

$$3\ O(N \log_2 N)+O(3N)=O(N(3+3 \log_2 N))$$ Both methods will have the same complexity for performing the maximum and absolute value, so I will omit those operations.

Comparing the two, $Nm$ will be larger than $N(3+3 \log_2 N)$ when $m>3+3 \log_2 N$. If this statement is true, it will be more efficient to use the frequency-domain method. Otherwise, you would be better using the convolution method.

*This statement isn't always valid on modern computing hardware because the speed of multiplication has increased substantially in the past decade to the point where addition and multiplication take roughly the same time to compute.

Improve this answer
$\endgroup$
8
  • $\begingroup$ True (+1), but see Hilmar’s comment on the OP. $\endgroup$
    – Peter K. ♦
    Feb 23, 2022 at 17:04
  • $\begingroup$ @PeterK. In an effort to improve the response, I've opened the answer up to the community. $\endgroup$
    – Ash
    Feb 23, 2022 at 17:25
  • $\begingroup$ I agree with the points raised and also to Hilmar's comment especially if the number of lags can be reduced. I don't understand the rationale under computing the O values and how you get to the 1+3logN. I think understanding this can help me in comparing both implementations also depending on the number of lags. Thanks! $\endgroup$
    – Albert
    Feb 24, 2022 at 11:09
  • $\begingroup$ One thing, time domain convolution takes real multiplication and add, while frequency domain convolution takes complex multiplication-add, which results in a slightly different turning point. $\endgroup$
    – ZR Han
    Feb 24, 2022 at 12:59
  • $\begingroup$ @ZRHan, thank you for bringing this up. I've updated the answer accordingly. $\endgroup$
    – Ash
    Feb 24, 2022 at 16:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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