fixed-point real FFT for embedded

Thread view:

Enable EMail Alerts

Start New Thread

Thread rating:

Shlomi - 04 Apr 2004 12:09 GMT

Hi !

I'm working on real-time speech recongnition application for embedded
systems (with ARM compatible processor).
I'm looking for a very fast (for real-time) real FFT fixed-point
version, with 16-32 bit input percision, up to 512 array-size.

I found fftw to be one of the fastest, but no fixed-point version :(

help would be very appreciated.

Regards,
Shlomi

Reply to this Message

Mark Borgerding - 04 Apr 2004 21:04 GMT

> Hi !
>
[quoted text clipped - 9 lines]
> Regards,
> Shlomi

Check out KISSFFT on sourceforge.net:
* ANSI C
* floating or fixed point processing
* optional code for real-only fft (see tools/kiss_fftr.c )
* small code size
* BSD open source license

The fixed point code currently uses Q15 format. It could easily be made
to work with Q31. Beware, Q31 multiplies may be very slow without a 64
bit accumulator.

There should be a version coming out rsn that will be more
embedded-friendly, thanks to Frank van der Hulst. He is using kissfft
on a microcontroller that makes many ARMs look like supercomputers
(Renesas M16c).

-- Mark Borgerding

Reply to this Message

Mark Borgerding - 04 Apr 2004 23:47 GMT

> Hi !
>
> I'm working on real-time speech recongnition application for embedded
> systems (with ARM compatible processor).
> I'm looking for a very fast (for real-time) real FFT fixed-point
> version, with 16-32 bit input percision, up to 512 array-size.

I just released KISSFFT version 1.2.1, which focuses on embedded & code
size issues.

See
http://sourceforge.net/projects/kissfft/

At the risk of dissuading you from using my fine little library ...
Have you looked on developer.intel.com for FFT libraries for your
flavor of ARM? If they provide an FFT, it is *gulp* probably better
than portable C code such as kissfft. Using assembly code, one can most
efficiently implement bit-reversed indexing, overflow managment,
rounding, scaling, etc.

-- Mark Borgerding

Reply to this Message

Shlomi - 07 Apr 2004 08:13 GMT

> >
> > Hi !
[quoted text clipped - 18 lines]
>
> -- Mark Borgerding

Thanks Mark,
I'm going to try your library, though with 32 bits accuracy,
and check it on the iPaq.
but I need some other fixed-point sources to compare it with.

I think we should do a contest for fixed-point FFT by benchmarking on
iPaq/Palm (Windows CE/Palm OS) etc..
what do you think ? you have a good starting point with your _small_
library !

if anyone is up to the challenge please post here,
I believe the embedded community will definitely harvest the fruits.

good luck !

Reply to this Message

Math Forum / Mathematics / Numerical Analysis / April 2004

fixed-point real FFT for embedded