Fast Fourier Transform in realtime

I want to develop an algorithm/code (whatever you want to call it) that would allow me to do a Fast Fourier Transform in realtime. I have seen it done on youtube videos of people who used arduinos to developed spectrum analyzers for music however they all seem to use preexisting libraries which tend to be in assembly language, buggy, and are difficult to really understand.

This brings me to my question, is it possible to do FFT without using assembly code (at least directly)? Also, does anyone have any good reference material that would help me develop my own algorithm.
Many Thanks.

A good guide to all the trouble you could want :wink:

http://www.arduinoos.com/wordpress/?p=1022

is it possible to do FFT without using assembly code

Yes, it is slower thats all.
The speed limit will cut down on your sample size. By defination it is never real time because you need a number of samples before you can take an FFT but for just a music display you only have to refresh a few times a second.

Grumpy_Mike:

is it possible to do FFT without using assembly code

Yes, it is slower thats all.

Either you write assembler, or the compiler writes it. It ends up the same.

is it possible to do FFT without using assembly code (at least directly)?

It is actually far more difficult to do FFT in assembly code. FFT in C and Fortran is far more common.

A fast FFT, 128 points and 8 bits, will take about 20 - 30ms on a 8Mhz / 8 avr.

I posted some results of playing around with FFT here: http://arduino.cc/forum/index.php/topic,96562.0.html

But there is an implementation of the Fast Hartley Transform here: ArduinoFHT - Open Music Labs Wiki
The FHT is faster than FFT.

Pete

(I maybe arguing semantics here) 'Same' could be misleading... Same instruction set sure, but not necessarily the same code, nor as performant or predictable. In many coding scenarios neither matters much or at all, but sometimes for outright speed, or guaranteed timing (e.g. generating video signals) assembly is the only way.

Possibly a side point to the OP though, because if I was trying to tackle FFT for the first time, I'd do it in C first, then consider optimising inner loops into assembly. The whole thing done in assembly, from the get go, would be some painful coding I'd imagine. :slight_smile:

paulo999:
... sometimes for outright speed, or guaranteed timing (e.g. generating video signals) assembly is the only way.

I'll have to challenge you on that statement. See this thread:

I have jitter-free VGA signal generation, using C++. No assembler, except maybe NOP, in one spot, purely for timing in one of the examples.

I used a disassembly to check what was generated, and then tweaked the C code (eg. moving an array to address row first rather than column first or vice versa). The disassembly proved that the generated code was as good as "hand-coded" assembler would be. Thus actually doing the hand-coding would not achieve anything except obfuscation.

Definitely possible to bend the compiler and work backwards. :slight_smile:

I'm an assembly coder by trade so it's easier for me to work forwards. :slight_smile:

I guess it must depend on the compiler, and the coder, but it seems to me that there are relatively few coders who can optimise code better than a decent compiler. (Mind you, I've worked with plenty of people who thought that they knew better. Conceivably some of them were smart enough to beat a compiler, but most of them clearly weren't.)

would it be possible to code in using the "Arduino language/syntax" or should I learn C?

Read this before posting a programming question

The Arduino language is C++ so yes, you should learn C (or C++).

What is the difference between C and C++? Ive heard C++ be referred to as a "naked language". Also do I need to learn C to learn C++ and any good texts or resources you could refer to me?

Google will help you here. C isn't really a "naked" language these days as they have tightened up the rules so you don't shoot yourself in the foot as easily.

What language is this code in ? I don't recognize some sections and I'm wondering if its because it's assembly code
http://arduino.cc/forum/index.php/topic,38153.0.html

It's C.

What is it that you don't understand, exactly ?

for example

const prog_int8_t Sinewave[N_WAVE-N_WAVE/4] PROGMEM = {
0, 3, 6, 9, 12, 15, 18, 21, 
24, 28, 31, 34, 37, 40, 43, 46, 
48, 51, 54, 57, 60, 63, 65, 68, 
71, 73, 76, 78, 81, 83, 85, 88, 
90, 92, 94, 96, 98, 100, 102, 104, 
106, 108, 109, 111, 112, 114, 115, 117, 
118, 119, 120, 121, 122, 123, 124, 124, 
125, 126, 126, 127, 127, 127, 127, 127, 

127, 127, 127, 127, 127, 127, 126, 126, 
125, 124, 124, 123, 122, 121, 120, 119, 
118, 117, 115, 114, 112, 111, 109, 108, 
106, 104, 102, 100, 98, 96, 94, 92, 
90, 88, 85, 83, 81, 78, 76, 73, 
71, 68, 65, 63, 60, 57, 54, 51, 
48, 46, 43, 40, 37, 34, 31, 28, 
24, 21, 18, 15, 12, 9, 6, 3, 

0, -3, -6, -9, -12, -15, -18, -21, 
-24, -28, -31, -34, -37, -40, -43, -46, 
-48, -51, -54, -57, -60, -63, -65, -68, 
-71, -73, -76, -78, -81, -83, -85, -88, 
-90, -92, -94, -96, -98, -100, -102, -104, 
-106, -108, -109, -111, -112, -114, -115, -117, 
-118, -119, -120, -121, -122, -123, -124, -124, 
-125, -126, -126, -127, -127, -127, -127, -127, 

/*-127, -127, -127, -127, -127, -127, -126, -126, 
-125, -124, -124, -123, -122, -121, -120, -119, 
-118, -117, -115, -114, -112, -111, -109, -108, 
-106, -104, -102, -100, -98, -96, -94, -92, 
-90, -88, -85, -83, -81, -78, -76, -73, 
-71, -68, -65, -63, -60, -57, -54, -51, 
-48, -46, -43, -40, -37, -34, -31, -28, 
-24, -21, -18, -15, -12, -9, -6, -3, */
};

Ok, that's the code. And what is the question ?

Looks like regular c/c++.

for example
Code:
const prog_int8_t Sinewave[N_WAVE-N_WAVE/4] PROGMEM = {
0, 3, 6, 9, 12, 15, 18, 21,

It's a constant table declaration, with a directive to put the code into ROM.