DFT or FFT library

[LBarratt]

Hi,
My programmer has given up on IPP and Xcode3.26. I plan to build a DFT for frequency analysis in the near future, but as a temporary measure for a Logarithmic 512 band frequency response and phase curve can anyone suggest a DFT or even FFT library. Polar co-ordinates at 512 logarithmic intervals would be good.
Hopefully not to big an ask.

Sorry I only ask questions rather than contributing on a regular intervals. My communication and programming are pretty poor.
Even a programmer going bump in the middle of the night is helpful.
Thanks

[mystran]

The only sane way to do DFT (with very few exceptions) is to use an FFT (the results are the same, and the naive one gets really slow really fast). There's supposedly a really good one in IPP.. but the "next best" alternative is probably OouraFFT (though usually it goes like "use OouraFFT until you can afford IPP").

Anyway, they all give you linearly spaced frequencies, because that's how DFT (and FFT which is just a fast version of the same thing) is defined. So for log-scale, you either need something other than DFT, or you need to process the results in one way or another. Processing the results is the more common thing to do, at least for a typical analyzer.

As for how to process.. well that depends on what information you find the most valuable to preserve. If you want peaks, try searching for the maximum in the given range. If you want "average power" try running some weighted mean-square for each band (with some overlap of the band windows probably).

You can also split the signal into "coarse" bands before FFT, resampling the low-freq bands to a lower samplerate to reduce the required FFT length for a given frequency separation. This way you can use longer windows (in terms of time) at lower frequencies. Whether it's worth it, depends on what you want.

As for "polar" well FFTs usually give you the real and imaginary components, but it's simple enough to calculate magnitude (or squared magnitude, which works just as well if you're going to log-scale it anyway) and phase from those.

[ralphb]

There's supposedly a really good one in IPP.. but the "next best" alternative is probably OouraFFT (though usually it goes like "use OouraFFT until you can afford IPP").

Just curious mystran, what do you mean when you say "best"? Are we purely talking about speed here?

(As opposed to e.g. how simple it is to figure out, how long it will take to compile?... sorry, I don't know much about this.)

[mystran]

There's supposedly a really good one in IPP.. but the "next best" alternative is probably OouraFFT (though usually it goes like "use OouraFFT until you can afford IPP").

Just curious mystran, what do you mean when you say "best"? Are we purely talking about speed here?

(As opposed to e.g. how simple it is to figure out, how long it will take to compile?... sorry, I don't know much about this.)

"Next best" as in "most commonly suggested alternative" but .. it's pretty easy to figure out, should compare well in terms of performance (except against IPP), it's simple to add a single C file to a project and comes with a liberal license..

Still, if you got IPP (which I assume means Intel Performance Primitives) then.. I wonder what's the problem with that.. I can't afford a license (so can't help with the specifics), but most of the time FFT is just a black-box that you call to transform one thing to the other, no?

[LBarratt]

My programmer wants to stay on Xcode 3.26 for Mac and is developing on PC. Can you suggest how to get IPP working on Xcode 3.26. vDSP is ok, but it is messy with two versions-one for Mac-one for PC.
I understand that an fft is a dft using patterns in the maths based upon samples at regular intervals. I agree that the magnitude and phase of a signal is no big step from an fft, but I was hoping some really smart person had sped that step up with some fancy pattern that matches logarithmic intervals and published it as a C++ library. I think I was dreaming.
Thanks

[mystran]

My programmer wants to stay on Xcode 3.26 for Mac and is developing on PC. Can you suggest how to get IPP working on Xcode 3.26. vDSP is ok, but it is messy with two versions-one for Mac-one for PC.
I understand that an fft is a dft using patterns in the maths based upon samples at regular intervals. I agree that the magnitude and phase of a signal is no big step from an fft, but I was hoping some really smart person had sped that step up with some fancy pattern that matches logarithmic intervals and published it as a C++ library. I think I was dreaming.
Thanks

Well.. there are.. http://www.cims.nyu.edu/cmcl/nufft/nufft.html and probably something else (search Non-Uniform Fast Fourier Transform) but no personal experience, I'm afraid.

[LBarratt]

Thanks
I will check it out.

[LBarratt]

My programmer has given up on IPP and Xcode3.26.

I thought I should clarify before I offend my programmer. He is a real trooper, but is really up against a brick wall with IPP and Xcode 3.26. He is still trying despite the fact that Intel don't appear to provide the appropriate files to download and don't provide much info on compatibility. Any one able to help him?
Thanks

[HiFi-LoFi]

AUTO-ADMIN: Non-MP3, WAV, OGG, SoundCloud, YouTube, Vimeo, Twitter and Facebook links in this post have been protected automatically. Once the member reaches 5 posts the links will function as normal.

Hi,

if you're looking for a simple to use and fairly fast FFT library for various platforms, you might have a look at AudioFFT:
https://github.com/HiFi-LoFi/AudioFFT (https://github.com/HiFi-LoFi/AudioFFT)

AudioFFT is a kind of side-product from my audio programming projects. It basically provides a uniform interface to different pretty efficient FFT implementations and is intended for usage in real-time audio algorithms (e.g., I use it for real-time audio convolution):

- Ooura: This is the fallback (pretty fast and very portable).
- vDSP (Apple Accelerate): The by far fastest FFT on Apple platforms
- FFTW3: Faster than Ooura but slower than vDSP (if you can handle the license).

However, currently there's no support for Intel IPP, but basically it shouldn't be a problem to add also support for it.

You also can find a few speed comparisons on the project site, maybe this helps you with chosing a replacement for IPP (but IPP will be very probably the fastest, and if you've got already a license, some kind of wrapper around IPP might be a good way to go).

Regards,

HiFi-LoFi

[LBarratt]

Thank you HiFi-LoFi.

[AnalogGuy1]

If having 512 log-spaced samples is really critical, then you'll need to perform a much higher order DFT (which as many have said linearly spaces the data) and then throw out progressively more and more of the higher-frequency samples - a higher order by exactly a factor of 512. In other words you'd need a 512^2 = 262,166 length DFT to get the same accuracy in a log scale between the lowest two frequencies as in the highest if the frequencies are log spaced. That essentially converts the efficiency of the FFT algorithm used to find the DFT from N log N to N^2 log 2N, so you'd be better off "manually" computing the DFT using the complex sum formula at each of the desired frequencies to get your log-spaced frequency samples.

That's the reason why all the spectrograms out there don't evenly log-space frequency samples, and why the bass frequency analysis looks jagged compared with the upper frequencies.

There are other spectrogram methods out there like the MUSIC algorithm that don't linearly-space output samples, but if there are issues implementing the more widely-distributed code then it's probably better to deal with linear-spaced frequency samples and go with one of the DFT packages others have mentioned.