Do you know a good and efficient FFT?

Question

Hi, I am trying to find a very fast and efficient Fourier transform (FFT). Does anyone know of any good ones. I need to run it on the iPhone so it must not be intensive. Instead, maybe you know of one that is wavelet like, i need frequency resolution but only a narrow band (vocal audio range up to 10khz max...even 10Khz might be too high). Im thinking also of truncating this FFT to keep the frequency resolution while eliminating the unwanted frequency band. This is for an iphone

...I have taken a look at the FFT in Aurio touch but it seems this is an int FFT but my app uses floats.....would it give a big performance increase to try and adapt program to an int FFT or not(which i really dont feel like doing...plus aurio touch uses a radix 2 FFT which is not that great).

Answer 1

Give the Fastest Fourier Transform in the West (FFTW) a go, The performance is good compared to others, but it is not completely free. See the details on commercial use here. Obviously being a c library you should have no problem linking it as a static library to your iphone app.

Answer 2

The performance of the FFTW sets the standard for arbitrary length FFT's - especially for non-power of 2 lengths in 2 and greater dimensions. The commercial license for FFTW is $5000, which may or may not fit in your budget.

However, it sounds like you have a 1D signal processing problem in which case you have a few more options - and if you can further either pad or sample your data to power-of-2 lengths, then many libraries will offer reasonable performance. Check out this list of FFT algorithms that FFTW used for comparison - many are free and some may be adequate. I'd probably start with good old numerical recipes which offers an easy power of 2, 1D FFT implementation for free and some typing - and would be very memory efficient.

BTW - for voice you probably only need to go to 3-4Khz....10Khz is way way up there for the human voice.

Answer 3

I've wrapped Ooura's FFT library in Objective-C. Ooura's code is of comparable performance to FFTW, but totally and utterly free.

This code uses double-precision and has several built-in window types (rectangular, Blackwell, Triangle, Hamming). I use Ooura's FFT code to implement Welch's method, which will generate a much smoother spectra when viewed over time.

Check it out at: http://github.com/alexbw/iPhoneFFT

You can see the FFT in action in my app, "oScope", here: http://oscopeapp.com/oscope-in-action

Answer 4

Here is a primary source link to Ooura's numerical software:

http://www.kurims.kyoto-u.ac.jp/~ooura/

I have been using many of Ooura's FFTs over the years, I should send him a "domo" at the very least, and I use his real radix-4 in several iPad and iPhone applications under development. I did translate the code to operate with 32-bit single precision for performance on ARM. Looking at the assembly produced with XCode 3.2.2, it vectorizes with NEON SIMD instructions very nicely. I was half disappointed actually, as I was willing to vectorize the code a bit myself for even more performance. These optimizations cannot be had without first translating the FFT to single precision obviously.

While I have used Objective-C for many years, I actively develop using it, and even taught an object oriented programming course using it, I did not prepare such a wrapper (though I had done the same back in 1992 with a different FFT) for performance reasons.

I haven't tested FFTW against Ooura's FFT in at least 10 years, but when I did Ooura's library was faster for 1024 point real FFTs. However, it is quite possible that FFTW may do much better now -- but licensing it and cross-compiling it for ARM is inconvenient and I have always found FFTW to be far too bulky and obtrusive for my DSP needs. Apple's VecLib is very nice but unfortunately they have not ported it to iPhoneOS. I opened a feature request in BugReporter and you can too: https://bugreport.apple.com/

Answer 5

The iPhone OS4 SDK will include the Accelerate framework, which will (finally) give us Apple-written FFT functions

Accelerate provides hundreds of mathematical functions optimized for iPhone and iPod touch, including signal-processing routines, fast Fourier transforms, basic vector and matrix operations, and industry-standard functions for factoring matrices and solving systems of linear equations.