8

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).

yan bellavance
  • 4,710
  • 20
  • 62
  • 93
  • Considering the Wavelet Transform is not computed in the same way as DFT, I would say there's no wavelet-like FFT algorithm. – rlbond Oct 20 '09 at 03:55
  • how about a Wavelet-like fft in the sense of instead of having a square matrix(4096by4096 for a FFT of 4096 samples) we use 4096 time samples by 1024 frequency bins...these would not cover the whole nyquist band and so would keep the desired frequency resolution without require to compute them all....this is the multi resolution scale aspect of wavelets but with only one scale....so its like I was applying a filter....which is part of WFT – yan bellavance Oct 20 '09 at 06:14

6 Answers6

12

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.

alexbw
  • 2,028
  • 2
  • 21
  • 25
8

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

alexbw
  • 2,028
  • 2
  • 21
  • 25
  • just a follow-up (three years later) — you should try to NOT use iPhoneFFT in your project. Apple has released vDSP and Accelerate.h on the iPhone, and you should be using functions like vDSP_fft_zrip() to calculate the FFTs. They are a GREAT deal faster than anything I've written. – alexbw Apr 21 '12 at 17:51
  • Indeed great pieces of work Alex, checked out Octave and Oscope both. I am wondering if there is any iOS libraries around that successfully wraps vDSP to detect human sounds - now let me tell you that I don't know if it means pitch detection or band pass or what. – Nirav Bhatt Mar 22 '13 at 08:58
  • That itself is a bit of an open research question in computer science (to do it reliably). If you're interested in a certain sound, record a bunch of examples, and look at their spectrograms. That should help you build a filter which is able to selectively respond to it. – alexbw Mar 22 '13 at 15:10
4

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.

hhafez
  • 38,949
  • 39
  • 113
  • 143
  • 1
    It does use shared memory FYI, you can't safely run it in parallel. not really sure if this is an issue on the iphone or not (probably not?) – Brian Gianforcaro Oct 20 '09 at 04:54
  • 1
    If you don't mind releasing your app under GPLv2 (you can't use GPLv3 for an iPhone app), it's completely free. If that's not compatible with your business model, you'll have to check the commercial options. – David Thornley Oct 20 '09 at 21:59
3

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.

Georg Fritzsche
  • 97,545
  • 26
  • 194
  • 236
Paul
  • 5,376
  • 1
  • 20
  • 19
2

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/

ctpenrose
  • 1,467
  • 2
  • 18
  • 28
  • FFTW should be a lot faster for lengths that are not round numbers in binary, e.g. for primes. – J D Aug 10 '10 at 19:28
0

As answered before, the Accelerate Framework now provides some APIs that might help you.

Check:

Accelerate Framework Reference

vDSP Reference

Using Fourier Transforms

dwbrito
  • 5,194
  • 5
  • 32
  • 48