search

adafruit / Adafruit_ZeroFFT

simple FFT for cortex m0
BSD 3-Clause "New" or "Revised" License
42 stars 18 forks source link

Return FFT's magnitude #6

Open nkonopinski opened 4 years ago

nkonopinski commented 4 years ago

This changes the output of the function to return the value users would expect from an FFT, it's magnitude.

The previous behavior was to discard the imaginary data, which can cause the output to vary sinusoidally over time. Returning the magnitude of the real and imaginary vector produces a consistent result.

Calculating the magnitude with multiplications and square roots can be computationally expensive. It can slow the function down by 4x for a 1024 length input. This approach uses the alpha max plus beta min algorithm (https://en.wikipedia.org/wiki/Alpha_max_plus_beta_min_algorithm) to efficiently return the magnitude. Using this method produced no measurable differences in the function's runtime.

dhalbert commented 4 years ago

@jepler may be of interest for ulab

jepler commented 4 years ago

@dhalbert thanks! I think ulab already handles this with the spectrum function, though you can also get the real and imaginary parts and work with them independently if that's important for your use case

jepler commented 4 years ago

though .. the optimization might be nice to have

jepler commented 4 years ago

@v923z thoughts?

v923z commented 4 years ago

I think ulab already handles this with the spectrum function,

That's correct. We could rename it to spectrogram, if you want: https://docs.scipy.org/doc/scipy/reference/generated/scipy.signal.spectrogram.html

@v923z thoughts?

A 1024-point FFT costs approx. 2 ms on the pyboard. spectrum returns in 2.2 ms with the same data, so the square/square root operation costs 200 us. That is 10%. I am not sure this is worth the effort, especially that the speed-up comes at a price in accuracy. One should also keep in mind that values in an FFT vary wildly (this is why logarithmic plots are much more useful), so the variations in accuracy might be uncontrolled (since there is no obvious scaling).

And I think the comparison of https://github.com/nkonopinski/Adafruit_ZeroFFT/ to ulab is not entirely fair: ulab calculates the twiddle factors on the fly, because there is no way we could store those in flash. The function in question seems to take the factors from https://github.com/nkonopinski/Adafruit_ZeroFFT/blob/topic/return_magnitude/arm_common_tables.c.

Having said that, I am not totally against the approximation, but if the 10% gain is deemed necessary, I would rather implement it as a keyword option to spectrum. I would be OK with fast = True, or something similar in spectrum.