FFT on AVR

Hi all,

I have a project that reads a K-Band radar sensor for traffic speed measurment. The frequency of the signal is related to the speed of the car. Samplig must be done @ 8 to 10khz (256 points).
Most designs use FFT to get the fundamental frequency (wich gives the correct speed).

As anyone implement something like it on AVRCO ? It there any lib or algoritm for this?
I don't even know if AVR as the power to do this.

I know that Microchip (and is dsPIC devices) had a FFT library avaiable, but I really don't want to use Pics and C...


Thanks

Joaquim

It can be done with AVR, but you will probably have to use ASM and fixed point numbers. AvrCo has support for fix64 numbers (64 bit fixed point numbers), but since you need every cycle you should also take a look at fix32 (use forum search for AvrCo source).
Not Pascal, but certainly worth looking:
http://www.adrianlombard.com/physical-computing/avr-fft-code
http://en.pudn.com/search_db.asp?keyword=FFT+AVR
http://elm-chan.org/works/akilcd/report_e.html
http://sourceforge.net/projects/avrfftlcd/
http://tinkerish.com/blog/?p=39
http://www.youtube.com/watch?v=GTb6RsJd2yc
http://www.youtube.com/watch?v=va32YtZc6pE
http://www.youtube.com/watch?v=GTb6RsJd2yc
http://www.youtube.com/watch?v=fC8YQNQQey8
http://www.youtube.com/watch?v=LKSYwUlggRQ
http://www.youtube.com/watch?v=Bn6BIfr_UgY

Let's take a look at Pascal path for a second, just one more time... As I could see, Chan's code is just implementation mixture of fixed point numbers and FFT. You already have fix32 fixed point numbers in AvrCo, and if I remember well you also have square root and basic trigonometric functions in the source. So you just need to implement FFT. You can try implementing FFT on your own, but I have seen around some Pascal FFT code that uses floating point numbers (Google is your friend, but be careful and read licenses well). You should just use fixed point numbers instead of floating point numbers in the code, so that part is solved. Also Chan's code is well commented so even without knowing ASM you can recode FFT in Pascal from scratch, by just looking at comment that explain the math behind the code. Whatever. Then, when you have working code and measure your performance, you can do necessary optimizations. You will probably want to improve calculation speed, and two things come first to my mind. First is implementing fix16 instead of fix32 (you have full commented source of the fix32 library here) by using fix16 s7.8 which is actually fixed 7 bits + 1 sign bit for integer part and fixed 8 bits for fractional part (fixing this improves calculation speed dramatically - this is why fix64 in AvrCo has s31.32), and second is by making lookup table for trigonometric functions. You could use this Chan's table for comparison:

Of course, speed heavily depends on how many FFT points you have in your goal. Just a guess, but with very low number of points and above mentioned optimizations implemented, you might even save your self from ASM.

Huh, 256 is not a low number of points. Anyway, I haven't touched XMEGA yet so only experiment can tell...