Can FFT Substitute Correlation for This Case?

Question

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.

Answer 1

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.