7
\$\begingroup\$

To put this in context, I'm looking to achieve both high speed and high accuracy for measuring biosignals through the FFT. I'll describe a quick example to see if I understand this properly as well as to illustrate my question. So, if I have this correctly, if I wanted to take a low-frequency FFT, say frequencies 0-64 Hz for example, to mmeet the Nyquist criterion my sampling frequency would have to be at least twice that, thus 128 Hz. Then, if I wanted a frequency resolution of 1 Hz to one bin, I would need 64 bins, which would put me at 128 samples because there are both real and imaginary parts. Therefore, to achieve that 1 Hz resolution, I would be presented with having a sampling rate of only 128 Hz while needing to take 128 samples, which would put me in the position of having only 1 full performance of the FFT for every second of time that elapses.

Ultimately, this leads me to my real question: at low frequencies, is it possible to take a high resolution FFT (say 1 or 2 Hz per bin) while still maintaining some semblance of speed? Or is this simply impossible due to the limitations of the transform? If so, is there some alternative method or some sort of compromise to be made between resolution and speed? As an aside, I read an article a while ago about oversampling and throwing out samples at certain integer multiples past a certain point (or something like that, sorry it was a little while ago) in order to speed up the sampling process. Maybe somebody knows what that is (or maybe I'm jut rambling at this point). Either way, thanks for any help you can provide in advance.

\$\endgroup\$
  • 1
    \$\begingroup\$ Please use paragraph spacing to make your question readable. \$\endgroup\$ – Peter Smith Jun 7 '16 at 18:10
  • \$\begingroup\$ There are also other methods for estimating a power spectrum, and different ways to process an FFT. en.wikipedia.org/wiki/Spectral_density_estimation \$\endgroup\$ – Voltage Spike Jun 7 '16 at 19:06
  • 3
    \$\begingroup\$ Wavelet transforms may also be very useful in this environment, because they will provide increased temporal resolution at higher frequencies while permitting the lower frequency signals to rise and fall as slowly as they may need to. \$\endgroup\$ – Cort Ammon Jun 8 '16 at 3:29
  • \$\begingroup\$ If you want high resolution FFT, take long measurements with sampling rate complying with Nyquist Rate. FFT of 1 second measurement gives 1 Hz resolution, 10 seconds measurement gives 0.1 Hz resolution \$\endgroup\$ – Aenid Jun 8 '16 at 8:16
10
\$\begingroup\$

One usually needs to acquire multiple samples per waveform period to get good results from an FFT. The Nyquist limit of 2 samples per period is a lower bound but usually 10 samples per period or more is what is practically used. So to analyze a 64Hz signal you probably want to acquire samples at a rate of 640Hz or more.

Also (up to a point) you will get better results when measuring actual periodic signals if you acquire multiple waveform periods worth of samples. You will need to determine what window size makes the most sense for your application but to capture 1Hz signals I would suggest capturing somewhere around 10s worth of data.

So basically you need to acquire samples at a high rate relative to your highest frequency and for a long time relative to your lowest frequency to get good results. This mandates that there will be some sort of processing delay that will be a multiple of the period of your lowest frequency. This does not however prevent you from performing that processing as often as once every sample time.

So if you want to analyze the frequency components of a signal as it changes over time, and you want to see what the FFT looks like at a high rate then you can just take in however many samples you need. Run the FFT. Shift all the samples over 1 position, and then take the FFT again at the next sample time.

EXAMPLE:
1) Sample at 819.2 samples per second with a time window of 10 s.
2) Let samples accumulate for 10 s (for a total of 8192 samples)
3) Run the FFT on 8192 samples.
4) Discard the first sample in the buffer, and keep the other 8191 samples shifting them over 1 position.
5) 1/819.2 seconds later add in the next sample to the end of the buffer and re-run the FFT.
6) Repeat steps 4-6 until you have completed your analysis.

This would give you an FFT that analyzes a sliding window of data 819.2 times a second

The processing power needed for the example would be approximately 13*8192*819.2 Multiply-Accumulate opeations per second (87 Million MACs/s). An ordinary PC could easily handle this. You can of course reduce the processing power by a factor of N by only running the FFT ever N samples (for example running it every 8 samples only requies 11M MACs per second).

\$\endgroup\$
  • \$\begingroup\$ OK, that makes sense i think. My original premise was operating under the idea that I had to collect an entirely new set of data every time I wanted to perform a transform, but it makes sense that you could simply run the fft every time a new piece of data is pushed into the array. That seems to be what everybody else is getting at as well, but it didn't really click until I read your explanation. Thanks \$\endgroup\$ – Scorch Jun 7 '16 at 20:48
  • 6
    \$\begingroup\$ Two things I think might be useful for this approach which may have been too obvious to mention: 1) You cannot distinguish a 1Hz signal from a lower-power 1Hz signal plus a DC bias any faster than 1 second, so that is a mathematical limit. 2) This approach, once primed, gets around this limit by reusing old signals. This will have the obvious effect of creating strong correlations between adjacent signals. Neither of these may matter to you in the end, but I found them useful for explaining why this approach appears to get to "cheat." \$\endgroup\$ – Cort Ammon Jun 8 '16 at 3:28
13
\$\begingroup\$

I assume for "high speed" you mean a small delay from data collection to the resultant FFT. With a low sample rate, your computational ability isn't the limiting factor, given modern computers. The delay problem lies in having enough data for analysis. If you want your 1Hz bin to be different from DC/0Hz, you have to accumulate enough signal data to capture a full cycle of that signal. This is why, for a fixed sample rate, a longer FFT gives you a higher frequency resolution.

Thus, for very low frequencies, your low sample rate (128Hz) means that it will take only a few samples to differentiate these frequencies: a 128-point FFT will have 1Hz resolution and a 256-point FFT will have 0.5Hz resolution. The problem lies in getting that data. 256 points takes a whole 2 seconds to accumulate at a 128Hz sample rate. For a faster FFT update rate, you could re-use samples: take say 32 samples as data blocks, then compute a 256-point FFT using the most recent 8 blocks. Then, when you have 32 new samples, you can throw out the oldest and update the FFT 4 times per second.

Essentially, you have encountered the trade offs required in creating a spectrogram: you have to choose between frequency resolution and time-locality. (MATLAB activity and example here) More frequency resolution requires more samples, thus making your FFT represent a long span of time. Using a short span of time means using fewer samples, thus making your FFT frequency resolution lower. You'll have to choose which is more important in your application.

\$\endgroup\$
  • 4
    \$\begingroup\$ +1 for recognizing the real problem (taking data); the waveform has to occur for it to be measured, and slowly varying data by definition takes a long time to measure deviations of. \$\endgroup\$ – helloworld922 Jun 7 '16 at 18:30
2
\$\begingroup\$

Modern DSP ships can easily handle the function you describe; if you only sample 128 time per second, you could easily do an FFT on every sample and shift one sample per FFT.

\$\endgroup\$
2
\$\begingroup\$

If your only tool is a hammer, every problem looks like a nail. I think you don't understand what an FFT actually is. It is a fast implementation of a DFT (discrete Fourier Transform). The DFT is an analytical tool for discrete signals with a periodicity of the analysis interval.

For real-world signals (outside of analysing motor signals or other rotating machines), your measuring interval will not actually correspond to a periodicity of the signal.

As a consequence, the "frequency bins" become meaningless and only correspond to actual features of the signal through the lens of windowing artifacts and spread spectrums.

While the efficiency of the FFT and its base functions' relation to the Eigenfunctions of linear shift-invariant systems make it likely that the work horse under the hood of many frequency-based tools will end up being an FFT, interpreting the raw results in terms of "frequency bins" is almost certain to end up at best loosely related to reality.

If it is a single signal you are trying to track/characterize, you are likely better off with something based on LPC coefficients.

\$\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.