Fixed Point FFT Algorithm Needed

Question

I am developing an algorithm for an audio application for mobile platforms. It appears to me that currently the float point calculation support on many mobile processors is not ubiquitous and developing in fixed point would be a safer bet.

I have written FFT routines in float point form for some time now to a degree of success, however writing one in fixed point turned out to be rather difficult. Namely, I would be happy to improve the precision, as well as to find a way to handle potential overflows. The problem is, unlike float point FFTs, descriptions of fixed point FFT algorithms are hard to come by on the Internet.

Has anyone had some experience developing such algorithms?

Answer 1

Your first choice should probably be to use a native-optimized FFT. There are processing requirement for fixed point FFTs that are difficult to express efficiently in portable C (or any language probably): saturation arithmetic is probably the biggest obstacle. Assembly libraries will tend to take advantage of processor-specific instructions for these .

If you still want a portable ANSI C fixed point FFT, I only know of one choice: kissfft. (Disclaimer : I wrote it)

Answer 2

I have read great things about http://anthonix.com/ffts/index.html - this works well on mobile platforms - The site contains benchmarks

Answer 3

I have been working on an automated tool that converts floating-point C code to fixed-point, with a variety of options for tradeoffs between accuracy and execution time. I have had good results with a number of algorithms, including a 2D 8x8 discrete cosine transform. My target platform is typically an ARM Cortex-M processor but similar results should be achievable on other platforms. Would you be interested in letting me take a crack at your FFT?