2
$\begingroup$

In terms of signal analysis (especially frequency decomposition) would it be bad to use cyclic autocorrelation (AC) instead of acyclic/linear AC?

My use case:
I'm trying to characterize events in a sensor stream by periodicity/frequency. At the moment, I'm using DFT spectrum (spectral density) and AC of sliding windows.
On the one handside it's algorithmically way cheaper to calculate the cyclic AC via FFT than acyclic (pad with zeroes and do double length FFT). However, the cyclic AC looks similar (though not equal) to the acyclic for the first N/2 lags and is self-symmetric - thus at most half the information of acyclic AC can be contained.

My motivation:
If the cyclic AC would be sufficient for detection, that would mean better performance compared to linear AC (in terms of memory usage and computation time). I then could also calculate AC inplace (better parallelization potential).

Rephrased question:
Is there any rule when cyclic AC should NOT be used?
Or perhaps, are there known cases, when cyclic AC might actually be better than linear AC?

Thanks in advance :-)

$\endgroup$
  • $\begingroup$ The cyclic autocorrelation of a PN sequence has ideal properties; the acyclic autocorrelation does not, except at length $7$ when a couple of PN sequences happen to be Barker sequences and so have acylic autocorrelation that is also ideal. $\endgroup$ – Dilip Sarwate May 22 '14 at 13:25
  • $\begingroup$ code for cyclic autocorrelation??? $\endgroup$ – user34402 Mar 12 '18 at 7:03
  • $\begingroup$ this should be a comment. since the post is old, i doubt we'll get an answer. $\endgroup$ – robert bristow-johnson Mar 12 '18 at 10:28
  • $\begingroup$ @user34402 sorry I don't have access to the code anymore, since I left the project in the meantime. $\endgroup$ – hardmooth Mar 12 '18 at 12:29
1
$\begingroup$

If the cyclic autocorrelation output has the properties you need in your application (e.g., it's peak-to-average ratio is high enough for picking out the peaks), then it's probably okay to substitute the cyclical correlation for the linear one. For example, consider a length 7 maximal-length sequence: $$ \{+1, -1, -1, +1, +1, +1, -1\} $$ The cyclical and acyclical autocorrelation functions are plotted below. Comparison of cyclical and acyclical autocorrelation functions of a length 7 maximal length binary sequence

Notice that both functions have a peak value of 7. The acyclical autocorrelation function has a largest off-peak magnitude of 3, whereas the cyclical autocorrelation function has a largest off-peak magnitude of 1. The peak-to-off-peak amplitude ratios are $7$ and $7/3$ for cyclical vs. acyclical, respectively. This means that the cyclical autocorrelation function is basically three times more peaky, making it much easier to detect. If the extra peak-to-off-peak amplitude ratio is not necessary for your application, it would be okay to correlate using linear correlation instead.

If instead, you have something whose acyclical autocorrelation properties are optimal (such as a Barker code), and you would like to calculate that acyclical correlation but don't want to use the computationally inefficient direct form of convolution, there are algorithms that calculate the acyclical autocorrelation using the computational savings of FFTs. Two of these I know of are called the overlap-add and overlap-save methods. They work on blocks of the input data at a time, and using FFTs of the blocks of data and multiplication in the transformed domain, calculate the acyclical correlations/convolution of the data against your given sequence.

|improve this answer|||||
$\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.