1
$\begingroup$

Is there a known algorithm or an existing implementation that performs a "continuous autocorrelation"?

Meaning, in a situation where I sample a signal and every time I get a new sample (or every several samples) I want to calculate an autocorrelation function for N samples back.

It seems preferred to do it in a continuous or "streaming" manner while reusing some of the calculations made previously. The alternative I know is an FFT based AC calculation but I expect a lot of overlap and wasted calculations.

$\endgroup$
3
  • 1
    $\begingroup$ Looks like someone wants a real-time pitch detector that updates pitch as often as necessary with the least possible latency. $\endgroup$ Jan 16 at 18:16
  • $\begingroup$ @robertbristow-johnson , exactly. Any pointers? $\endgroup$ Jan 16 at 20:14
  • 2
    $\begingroup$ oh dear. maybe. i gotta be careful about some stuff (that might be considered a trade secret at places like Eventide). lemme think about it. One thing that you might wanna do is consider information in this answer. $\endgroup$ Jan 17 at 17:48

1 Answer 1

2
$\begingroup$

With a circular auto-correlation in the time domain, it is clear that we can at the cost of storage reuse prior multiplications for a significant savings on each subsequent computation for a streaming auto-correlation (where we compute the complete auto-correlation function over the past $N$ samples for each new input sample). I suspect (but haven't concluded) we are not able to reuse prior computations in the frequency domain approach to circular auto-correlation which is very efficient using FFT's given as:

$$R_{xx}[m] = \text{ifft}\bigg\{\text{fft}\{x[n]\} \text{fft}^*\{x[n]\}\bigg\}$$

Where $R_{xx}[m]$ is the circular autocorrelation function at offset $m$ for $0 \le m \le N-1$ of $x[n]$ over $N$ samples, and $\text{ifft}\{\}$ represents an inverse Fast Fourier Transform operation and $\text{fft}\{\}$ represents a Fast Fourier Transform operation.

Assuming there is no savings of computation with the FFT approach, this suggests there would be a cross-over for a length $N$ where it would be more efficient to perform the streaming auto-correlation in one domain or another. Let's look at an estimate of the number of multiplications and additions needed for both approaches assuming a real signal:

Time Domain Approach

Consider the time domain approach illustrated below, demonstrating the computations involved for $N=6$ for the first sample offset $m=0$, consisting of $N$ real multiplications and $N$ real additions. This would be repeated $N$ times for each of the $N-1=5$ additional circular shifts for a complete autocorrelation function. I used an index $k$ to indicate the sample for a complete auto-correlation function (so $k$ indexes with each new sample input once the buffer $N$ is first filled).

Autocorrelation function time domain

Thus with the time domain approach for the first computation of the autocorrelation function, once we have collected our first $N$ samples, we would compute $N^2$ real multiplications and $N^2$ additions for the first autocorrelation $k=0$.

If we store our prior autocorrelation results (the summations for each offset $m$), and last sample in the buffer ($x_0$ in this case), when the next sample is input (here, $x_6$), we can for each offset $m$ simply subtract the product for the sample dropping off and add the product for the new sample coming in. Resulting in 2 real multiplications and 2 real summations for each $m$, repeated $N$ times for the complete autocorrelation. Thus we would compute $2N$ real multiplications and $2N$ real additions for each next autocorrelation $k$.

next sample processing

And similarly for the remaining offsets $m$ to compute the full circular auto-correlation we would get:

$R_{xx}[m=1, k=1] = R_xx[m=1, k=0] - x_0x_1 + x_6x_1$

$R_{xx}[m=2, k=1] = R_xx[m=2, k=0] - x_0x_2 + x_6x_2$

$R_{xx}[m=3, k=1] = R_xx[m=2, k=0] - x_0x_3 + x_6x_3$

$R_{xx}[m=4, k=1] = R_xx[m=2, k=0] - x_0x_4 + x_6x_4$

$R_{xx}[m=5, k=1] = R_xx[m=2, k=0] - x_0x_5 + x_6x_5$

Summary for Time Domain Processing:

First Autocorrelation: $N^2$ real multiplications, $N^2$ real additions.

Each subsequent Autocorrelation: $2N$ real multiplications, $2N$ real additions.

Frequency Domain Approach

The Cooley-Tukey FFT requires $2NLog_2(N)$ real multiplications and $2NLog_2(N)$ real additions for each FFT or IFFT. In the formula introduced at the start of the post for $R_{xx}[m]$ using FFTs, we see there is a product of two ffts, and then an ifft of that result. Thus we have three total FFT or IFFT operations each with $N$ samples, as well as $N$ complex multiplies for the product. A complex multiplier requires 4 real multiples and 2 additions. Adding this all up, for a single circular cross-correlation the process would require:

FFT/IFFT: $2NLog_2(N) \times 3$ real mults, $2NLog_2(N) \times 3$ real adds

product: $4N$ real mults, $2N$ real adds

Total of above: $4N+6NLog_2(N)$ real mults, $2N+6NLog_2(N)$ real adds.

Conclusion

For large $N$ that first computation in the time domain can be significant, and perhaps never recovered with the subsequent savings. For example if $N=1024$, then the first time domain auto-correlation would require $N^2=1,048,576$ multiplies, while the FFT approach would require only $4N+6NLog_2(N) =65,536$ multiplies. After that the time domain approach would only need $2N=2048$ multiplies while the FFT approach continues at $65,536$ per new input sample. We would be ahead with the time domain approach by the 16th sample in this case. If we double $N$ to $2048$ we would not be ahead until the 29th sample. The break even computation as explained here results in the following generalized equation:

$$\frac{N-4-6Log_2(N)}{2+6Log_2(N)}$$

Which is plotted below:

break even chart

If the initial computation was a concern, the first auto-correlation can be computed using the FFT approach, and then all subsequent autocorrelations can be computed using the time domain approach! Since as suggested we only need the results and final sample in the buffer for each $k$, this would be a pragmatic approach for a streaming circular auto-correlation. For comparison to any other approach, this would require $4N+6NLog_2(N)$ real mults and $2N+6NLog_2(N)$ real adds for the first auto-correlation and $2N$ real mults and $2N$ real adds for each subsequent auto-correlation in the streaming process.

$\endgroup$

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.