OK well I’ve decided to write my own FFT with some tweaks to be optimised for the Arduino.
Namely, I am converting floating point values to fixed point using a notation similar to Q8.7 described here: http://www.maxim-ic.com/appnotes.cfm/an_pk/3722. I will have to modify it slightly because the ADC values are from 0 - 1023 (10 bits), whereas the uC that the website uses only has 8-bit ADC. So something like Q10.5 I guess:
Bit 15: sign bit
Bits 14-5: Integer values
Bits 4-0: Floating point values
This gives me 5 decimal places of resolution, with values up to 1023.
I was hoping someone could share some insight into converting floating point to fixed point in C.
And as for RAM, assuming we use a 256 point FFT, with each sample occupying 16 bits (4 bytes), it will use 1024 bytes in memory. The Atmel168 has 16kb of memory so this should not be an issue. Or am I missing something here? EDIT: Uses 2*N values, one for real one for imaginary so 2048 bytes.
I’m also using trigonometric lookup tables to avoid using cos() and sin() functions in Arduino.
Will post results here.