Arduino and FFT

Development Boards MicroMod
1

I have been searching tirelessly through the internet to find an FFT library designed specifically for the Arduino. I have found heaps of FFT algorithms for Atmega AVRs but they are either in C or ASM, not in the Arduino language. Is there an easy way to convert those files (written for either Atmega8 or Atmega168) to the Arduino’s language? I don’t really want to write an FFT function from scratch in the Wiring language when there are so many great pieces of code that are very efficient.

All I’m trying to do is attach a microphone to the Arduino and do a 256 or 512 piont FFT (Radix 2 algorithm) and send values back to PC over serial and display the spectrum (for debugging). The Arduino will basically do differencing of the spectrum to find patterns and make decisions based on those differences.

I’ve read how to change prescale factors on the ADC to improve sampling frequency up to ~77KHz, which is a bit overkill, but we need ~40KHz giving us nyquist frequency of 20KHz.

Any thoughts / suggestions? Would be appreciated!

Cheers

2

ADmoney:
I have been searching tirelessly through the internet to find an FFT library designed specifically for the Arduino. I have found heaps of FFT algorithms for Atmega AVRs but they are either in C or ASM, not in the Arduino language.

Cheers

Arduino’s language is C, just some macros atop standard C.

Same C as in Atmel Studio + WinAVR, both free.

You’ll need an AVR with a fairly large RAM to store all those samples and bins, and unless you warp the math to be fixed point, floating point will be rather slow. Depends on the speed you need. Discrete cosine FFT, IFFT, etc.

3

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.

4

you have one big error:

AVRs are Harvard Architecture whereas PCs that you are used to are Von Neuman. Thus, the AVRs (and others) have TWO address spaces: one for code in flash memory and another for RAM.

The RAM size in AVRs is small compared to the flash size because of how AVRs are used. So you want to choose an AVR with 2KB or more of RAM and probably at least 32KB of flash.

Even so, I think you are trying for a sampling rate of something like 70Ksps. You’ll not do continuous sampling/FFT with a $5 microprocessor. You can do about that sampling rate, then do a DCT or some such in many 10’s of miliseconds, perhaps even 100 or more mSec. The trick to fast FFT in cheap micros is to scale everything so there’s an implicit decimal point and use fixed point math, not floating point.

There are several implementations of fast FFT for DTMF (Touch Tone) decoding. You might start with one of these. Not 70Ksps of course. However, for DTMF decoding the painless way is to use a $3 DTMF decoder chip.

5

I would add to stevech’s post and say that if any part of your math involves division, it would be best to rework everything so you only divide by 2^n if possible.

I did a project in college where we were trying to implement a simple DSP system on a 4MHz cpu. The problem was that the sampling rate left us with very few CPU cycles to do any actual math and the div instruction on that CPU took 200 cycles to complete, which was far too long. The way I solved the problem was to change the math in such a way that when I needed to divide, I was dividing by 32. It turns out that one way to optimize integer division is to simply shift the value to the right 5 times.

6

ADmoney:
OK well I’ve decided to write my own FFT … something like Q10.5 …

I was hoping someone could share some insight into converting floating point to fixed point in C … assuming we use a 256 point FFT, with each sample occupying 16 bits …

Good news:

Have you seen the tips for fixed-point FFTs at http://en.wikibooks.org/wiki/Embedded_S … Point_Unit and http://massmind.org/techref/method/ffts.htm ?

It appears to be almost exactly what you are looking for.

The ATMEGA32 has 2 KBytes of SRAM, which may be enough for a 256 byte FFT.

(It also has 32 KBytes of program flash, which seems more than adequate for this application).

I’ve heard that some Atmel AVRs have slightly more RAM.

For a 256 real point FFT, many people calculate 512 output values (2 values each at 256 distinct frequencies), but the 2 values in frequency bin 5 are always identical to the 2 values in frequency bin 256 - 5.

I’ve heard that it is possible to calculate only the 256 output values (2 values at each of 128 distinct frequencies) for a given 256 real input values.

Skipping the calculation of those “redundant” values may allow you to use less time and RAM.

If you are really only interested in few of those 256 bins, using the Goertzel algorithm at any 8 frequencies of your choosing may be faster than a 256 point FFT. http://en.wikipedia.org/wiki/Goertzel_algorithm

Bad news:

I agree with stevech: the Atmel168 has only 1 KByte of RAM, and I’m not sure that is enough for a 256 point FFT. (Its 16 KByte of program memory can’t be used for rapidly changing data).

I’m not sure 16 bit resolution will be enough. Have you calculated what number you expect the FFT to give in the “DC” (“0 Hz”) bin when given a flatline constant at the maximum expected level?

Many DSPs do internal calculations at 24 bit resolution (fixed point) for a reason, even though that at first glance seems overkill when they are connected to “CD quality” 16 bit ADCs and DACs.

7

Thanks for all the input! Really appreciated. I found a great post from ELM-Chan at http://elm-chan.org/works/akilcd/report_e.html. He has developed an FFT library that runs on Atmega8s! He’s written a 128 point FFT algorithm with sampling frequency of 9.6KHz in assembler that seems quite efficient… it can display onto a neat little LCD as a pseudo oscilloscope. I am going to rewrite this for Atmega168 and Atmega32 and see how it goes.

8

I now have ELM-chan’s FFT working on an Atmega168, it can do 64 point or 128 point but runs out of memory for 256 and above. I am going to switch to the Atmega328 soon so I can do 256 point ops. Specifically, it uses 6830 bytes for flash and 484 bytes for SRAM when doing 64 point, and 7150 bytes for flash and 932 bytes for SRAM when doing 128 point.

It is currently transmitting this FFT to an Arduino over UART which handles other operations like motor control & sound output (Soundgin). If anybody is interested in the code for the AVR I’d be happy to share.

I’m also researching a better microphone than the Sparkfun one: http://www.sparkfun.com/commerce/produc … ts_id=8669. I’m getting a bunch of rubbish coming through on the FFT, it seems for low frequencies it pulses every couple seconds or so. I’m looking at some nicer filters & mics, if anybody has any recommendations that would be great.

UPDATE: the mic seems to work properly now, I get really nice data coming through and visualize it in Processing.

  • A -
9

OK I’ve been getting a few messages about the code. I am in the process of starting up my own website and I’ll post it there, if you can hold tight… thanks

A

10

HI,

I’m interresting by your code for ARDUINO is it possible to have it ?

Manuel

11

ADmoney:
OK I’ve been getting a few messages about the code. I am in the process of starting up my own website and I’ll post it there, if you can hold tight… thanks

A

Could you share the code?

Pessanha24

12

Pessanha24:

ADmoney:
OK I’ve been getting a few messages about the code. I am in the process of starting up my own website and I’ll post it there, if you can hold tight… thanks

A

Could you share the code?

Pessanha24

Anyone can help with this question?

13

ADmoney:
I have been searching tirelessly through the internet to find an FFT library designed specifically for the Arduino. I have found heaps of FFT algorithms for Atmega AVRs but they are either in C or ASM, not in the Arduino language. Is there an easy way to convert those files (written for either Atmega8 or Atmega168) to the Arduino’s language? I don’t really want to write an FFT function from scratch in the Wiring language when there are so many great pieces of code that are very efficient.

All I’m trying to do is attach a microphone to the Arduino and do a 256 or 512 piont FFT (Radix 2 algorithm) and send values back to PC over serial and display the spectrum (for debugging). The Arduino will basically do differencing of the spectrum to find patterns and make decisions based on those differences.

I’ve read how to change prescale factors on the ADC to improve sampling frequency up to ~77KHz, which is a bit overkill, but we need ~40KHz giving us nyquist frequency of 20KHz.

Any thoughts / suggestions? Would be appreciated!

Cheers

Have you considering writing an Arduino library based on those AVR implementations?

14

OK I posted it on my server temporarily. You can access it here:

EDIT:

Code and details are now found on my site here:

http://www.adrianlombard.com/physical-c … -fft-code/

Enjoy

A

15

ADmoney:
OK I posted it on my server temporarily. You can access it here:

http://web.arch.usyd.edu.au/~alom9080/FFTatmega168.zip

Enjoy

A

ADmoney,

So you’re not actually using this from the Arduino IDE, correct?

Zach

16

Hi

What compiler do you use to compile it?

I cannot get it to work in arduino ide.

Please explain.

Thank you

17

Is there an easy way to get the assembly part into the Arduino IDE?

I would like to try getting a spectrum display on the S65 Shield.

18

As an afterthought:

Guess it would be unpractical with all that inline assy.

The ideal would be as an earlier poster asked for: make a stand-alone library for the FFT.

Hope, hope … :smiley:

19

It would be good to change this code that is now in the timer interrupt service routine:

SIGNAL(SIG_OVERFLOW0) { 
...
fft_input(capture, bfly_buff);
fft_execute(bfly_buff);
fft_output(bfly_buff, spektrum);
print_FFT(spektrum, NUM_SAMPLES/2);

to run in the main() code. It’s unwise/risky to do library calls like (printf, etc) and do extensive function calls from an ISR - due to reentrancy. Indeed, the butterfly FFT calcs are called from the ISR.

20

Just got the FFT up and running on the Arduino by using AVR Studio.