3
$\begingroup$

I'm trying to determine frequency of a repeating pattern in a time series. The sampling rate 100Hz and the pattern repeats itself with periods between 0.5 second and 1.25 second. This corresponds to a frequency range between 0.8Hz and 2Hz. At each second, I want to find the period of the pattern with 10msec precision, i.e. I want to differentiate 0.7sec(1.4Hz) and 0.6sec(1.6Hz).

I can attain this goal using correlation: For possible windows lengths (periods) I calculate correlation between two successive windows with same length. The window length with highest correlation gives the period of pattern.

Can I obtain the same results by using FFT?

As far as I see if I use 128-point FFT with this 100Hz series, then it will give me 100/128=0.8Hz (1.25sec), 1.6 Hz (0.62sec), 2.4Hz (0.42 sec),... components which obviously won't meet my requirement of 10msec period precision.

I know I can increase precision by using 256-point FFT but this corresponds to 2.5-second window for 100Hz and I want to determine pattern frequency for each window of ~1second.

|improve this question
$\endgroup$

migrated from stackoverflow.com Aug 20 '12 at 19:52

This question came from our site for professional and enthusiast programmers.

  • $\begingroup$ Perhaps you're asking about the convolution theorem, that ${\frak F}[f g]={\frak F}[f]*{\frak F}[g]$, where $\frak{F}$ is the Fourier Transform and $*$ is convolution, for two functions $f$ and $g$. So, yes, FFT can substitute convolution: $f*g={\frak F}^{-1}\{{\frak F}[f]{\frak F}[g]\}$. $\endgroup$ – Geremia Jan 29 '17 at 0:29
6
$\begingroup$

How did you plan to use the FFT in the first place?

If it is to naively look for peaks in the magnitude spectrum and deduce the frequency from it, this is a bad idea. As you have seen, this has a limited resolution in the lowest frequencies. Resolution limitations aside, looking for a peak in the FFT is a poor way of estimating periodicity since the true fundamental frequency might not be the one with the most salient amplitude.

However, you can use FFT as an intermediate step to efficiently compute the autocorrelation function (FFT with zero-padding of the input to avoid wrapping -> square of magnitude of coefficients -> IFFT). Looking for peaks in the autocorrelation function is a more reliable period estimator than FFT peaks.

Thus, given your requirements, you could use sliding windows of 256 samples, with a 61% overlap, compute the autocorrelation through the FFT, look for the autocorrelation peak in the [50, 125] samples range and use this as an estimate of the period. Because of the 61% overlap, this will give you one period value per second. Observe here that it is possible to use large analysis windows (256 samples, or more) and make them overlap so that we can still get a detection for every 100 sample. The downside is that if the period of the signal rapidly change, your detection will be "smudged".

I see a few other approaches for your problem that do not suffer from any resolution compromise on the temporal axis:

  • If the waveform of your input signal is known (square, sawtooth, sine...), you could try locking an oscillator of similar waveform to it through a PLL, and use the PLL frequency as your estimator.
  • If your signal is purely sinusoidal, you can fit a complex exponential to it (through eigenanalysis of the autocorrelation matrix).
  • An approach that would give a very high resolution (one decision per sample) would be to run your signal through a bank of 75 comb filters in parallel, with delays of 0.5, 0.51, 0.52 .. 1.25 seconds. Compute the energy of the output for each of these 75 signals ; the one with the highest energy gives you the period.

Note that your problem has very similar requirements to that of tempo detection (onset detection yields an envelope signal at 100 Hz or the likes, we aim to get a tempo map in the 60 BPM - 180 BPM, ie 0.33 - 1Hz range, with a temporal resolution of 1s). Historically, the comb filterbank approach was used ; while most recent solutions are based on autocorrelation or similar autocorrelation-based pitch estimators (yin) ; with analysis windows in the 5 - 10s range.

|improve this answer
$\endgroup$
  • $\begingroup$ Thank you @pichenettes. Do you think my use of correlation is a good or a bad solution for this problem in terms of memory and cpu requirements compared to alternative methods you listed above. $\endgroup$ – mostar Aug 20 '12 at 20:56
  • $\begingroup$ It's a good solution if you compute it efficiently (through FFTs). $\endgroup$ – pichenettes Aug 20 '12 at 21:05
  • $\begingroup$ First: Computing the autocorrelation naively in the time domain is O(N^2), while doing it through an FFT/IFFT is O(N log N). You might argue that N might be small enough for the naive time-domain thing to require less MACs than the FFT and IFFT... However, there are very efficient libraries for computing FFTs, using all the artillery available on your hardware platform (such SIMD instruction sets). Your ad-hoc implementation of your algorithm will have to use the same tricks to be competitive... $\endgroup$ – pichenettes Aug 20 '12 at 21:30
  • $\begingroup$ the above answer was a reply to a question about efficiency of direct time-domain computation of autocorrelation vs autocorrelation through FFT. $\endgroup$ – pichenettes Aug 20 '12 at 21:31
  • $\begingroup$ thank you very much and sorry for deleting the question. $\endgroup$ – mostar Aug 20 '12 at 21:33

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.