Go Down

### Topic: Fast Fourier Transform in realtime (Read 24659 times)previous topic - next topic

#### jkarimi

##### Oct 13, 2012, 06:58 am
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.

#### spcomputing

#1
##### Oct 13, 2012, 07:31 am
A good guide to all the trouble you could want

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

#### Grumpy_Mike

#2
##### Oct 13, 2012, 10:10 am
Quote
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.

#### nickgammon

#3
##### Oct 13, 2012, 12:18 pm

Quote
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.
Please post technical questions on the forum, not by personal message. Thanks!

#### dhenry

#4
##### Oct 13, 2012, 01:42 pm
Quote
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.

#### el_supremo

#5
##### Oct 13, 2012, 05:45 pm
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: http://wiki.openmusiclabs.com/wiki/ArduinoFHT
The FHT is faster than FFT.

Pete
Don't send me technical questions via Private Message.

#### paulo999

#6
##### Oct 13, 2012, 08:52 pm

Quote
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.

(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.

#### nickgammon

#7
##### Oct 13, 2012, 10:41 pm

... 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:

http://www.gammon.com.au/forum/?id=11608

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.
Please post technical questions on the forum, not by personal message. Thanks!

#### paulo999

#8
##### Oct 14, 2012, 01:30 am

... 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:

http://www.gammon.com.au/forum/?id=11608

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.

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

#### PeterH

#9
##### Oct 14, 2012, 03:11 am
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.)

#### jkarimi

#10
##### Nov 24, 2012, 07:08 am
would it be possible to code in using the "Arduino language/syntax" or should I learn C?

#### nickgammon

#11
##### Nov 24, 2012, 07:15 am
Read this before posting a programming question

The Arduino language is C++ so yes, you should learn C (or C++).
Please post technical questions on the forum, not by personal message. Thanks!

#### jkarimi

#12
##### Nov 24, 2012, 07:23 am
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?

#### nickgammon

#13
##### Nov 24, 2012, 07:32 am
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.
Please post technical questions on the forum, not by personal message. Thanks!