How to code sound FFT ?

[va!n]

hi guys! me and a friend are trying to code something, where we need a fast FFT algo... we searched the web and found a lot of algos but sadly all are written cryted math signs (like on wikipedia), we dont understand anymore... (to long ago, when we had some of this math signs in scool ^^)

So, does someone of you know or have a working and easy to read and undestanding codesnip that works? atm we are trying to understand and convert a VB source with bad variablenames and without comments ^^

First attached image (scope) looks like something, we still managed to work atm...
Second attached image (fft) is what we are looking for (in realtime !)

many thanks in advance!!!

[slippy]

Morning dudes,

@va!n: I'd recommend having a look at this url: http://www.musicdsp.org/archive.php?classid=2#79

I'm pretty sure you'll find something useful there as this site is a real cool knowledgebase ...

SLiPPY

[taj]

Wow fantastic link! Karma++ , thanks slippy.

[Jim]

Also http://www.nrbook.com/a/bookcpdf.php
Chapter 12.  Watch out, code works but coding style is shocking!

Jim

[frea]

Jim -> numerical correct & fast algo is always horrible to read .
Btw if you needed basic FFT explanation try cormen's book.

[Jim]

Yeah, I know The problem is the code was ported from FORTRAN to C by the authors, and that makes it far worse that if it had been re-coded cleanly.

Jim

[va!n]

thx guys... i know the url dsp... but i dont found something that is easy to understand / useable for me... i will try it again

[stormbringer]

here is some simple FFT processing (although it can be optimized further)

It has simple code to create different classic analyzers from the basic FFT

[Jim]

The Numerical Recipes code is actually pretty straightforward, but not very optimised, and the accompanying explanation is pretty good  - if you're not grokking that then it might not matter how simple the code is.  Can you post some attempts or ideas, or plans that you have for using the code?

Jim

[va!n]

@Stormbringer:
thanks for the code.... atm i dont really understand it (need to convert it to PB or a working (very fast and extreme small in size compiled lib ^^) however, own PB code would be much better, even to understand the math and how it works ^^

btw, is is possible, there are 2 differend kind of sound FFT algos available?  One floating and one integer version? O.O  If so, i think i only need a fast integer version 10x in advance...  best regards

[stormbringer]

@va!n: you are welcome. The code to perform the 1D FFT is quite simple actually. It takes a window of samples (BTW, can be any signal, not just audio) and does the transform forwards and backwards. The floating point version is slower but propably simpler to understand as the basic idea is to transform real numbers into complex numbers (therefore sin() and cosin() functions are used). I suggest you have a look at some theory here: http://zone.ni.com/devzone/cda/tut/p/id/4278

The explanation is quite good in my opinion.

Try the floating point version with some basic signal (a sine function for which you know the frequency) first. Let me know how it goes.

[va!n]

@stormbringer:
thanks a lot... i will try it out very soon... first i have to send my notebook to the manufractor to repair the keyboard and wait to get it hopefully very soon back

[va!n]

Due fact we need a very very fast and small size FFT algo, i found that intel Math Lib (comercial) has a very fast FFT inbuild... O.O   Does someone has a very fast optimized version like intels or something like this? ^^   thx    (source and compiled lib would be nice )

[slippy]

va!n ... I just found another solution which might work for you as well ... as Hitchhikr updated his site, he released the sourcecode of a music disk (Scoopex'n'Chips #3 Final) ... there's an fft algo built in ... perhaps it might help if you study these sources ...

http://pagesperso-orange.fr/franck.charlet/demoscene.html

Cheers,
SLiPPY

[va!n]

@slippy:
thanks, i will try to take a look to his source! K++

Edit:
Ah as i see, he is using bass.dll and i think there is a inbuild FFT like in fmod which is not acceptable to use any external DLLs like Bass, Fmod ^^ Its for a tiny exe size projec. anyway thx

[Jim]

You really should try the floating point code from Numerical Recipes.  I used it in 1992 on a 20MHz Sun Sparc and was able to FFT 1MB or so in 20seconds.  Today's CPUs are way faster, and you are only getting around 800samples/frame or 44100/second with audio.  You don't need the Intel one, or anything near it - it's total overkill.

Jim

[p01]

Are you sure you actually need an FFT ? I guess you want to detect the beats and that sort of things. Reading the patterns of your track, or synth, should be enough.

[taj]

Va!n,

how about this: http://local.wasp.uwa.edu.au/~pbourke/other/dft/  ? Both dft and fft are in the source half way down the page...

Chris

[Jim]

Oh, nice link!
Jim

[va!n]

sorry but i am back again with this topic... first i want to thank you all for some nice links and your help... my main problem is to read/understand and convert this crypted-looked math symbols. (sadly my best friend and me cant read them like following graphic

)

However, until now we did not managed to code an own FFT nor to understand how does it work, because readable basic sources like  VB-Sources are using silly variable-names where we dont know what they stand for and whats going on in the procedure.

I have to thanks JIM, who showed me a C/CPP source for DFT, i tried to convert to PB but we still have even problems with this DFT source. here is what i have (DFT instead needed (fast and small FFT) ^^

Code: [Select]

Type : fourier transform
References : Posted by Andy Mucho
Code :

AnalyseWaveform(float *waveform, int framesize)
{
   float aa[MaxPartials];
   float bb[MaxPartials];
   for(int i=0;i<partials;i++)
   {
     aa[i]=0;
     bb[i]=0;
   }

   int hfs=framesize/2;
   float pd=pi/hfs;
   for (i=0;i<framesize;i++)
   {
     float w=waveform[i];
     int im = i-hfs;
     for(int h=0;h<partials;h++)
     {
        float th=(pd*(h+1))*im;
        aa[h]+=w*cos(th);
        bb[h]+=w*sin(th);
     }
   }
   for (int h=0;h<partials;h++)
       amp[h]= sqrt(aa[h]*aa[h]+bb[h]*bb[h])/hfs;
}


Code: [Select]

Type : fourier transform
References : Posted by Andy Mucho
PB conversion: Mr.Vain / Secretly!
Code :

Procedure AnalyseWaveform( *waveform.f, framesize.l )
   aa.f ( MaxPartials )
   bb.f ( MaxPartials )

   For i = 0 To partials
     aa(i) = 0
     bb(i) = 0
   Next

   hfs.l = framesize/2
   pd.f  = #Pi/hfs
   
   For i = 0 to framzesize
     w.f  = waveform( i )
     im.l = i-hfs
     For h = 0 To partials
        th.f = (pd*(h+1))*im
        aa( h ) = aa( h ) + w*Cos( th )
        bb( h ) = aa( h ) + w*Sin( th )
     Next
   Next

   For h = 0 to partials
       amp( h ) = Sqr( aa(h)*aa(h)+bb(h)*bb(h) ) /hfs
   Next

EndProcedure


I hope i converted the source correctly to PB. Now lets have a look to the sources and try to explain following *confusing* things, we dont understand pls ^^

a)
There is the variable named MaxPartials, but what is it for and what value does it must have?

Code: [Select]

   aa.f ( MaxPartials )
   bb.f ( MaxPartials )


b)
Why does we must fill aa(i) and bb(i) with 0? If they will be initialized the first time, they will be always 0. Seems to me, its useless code that can be removed...?

Code: [Select]

   For i = 0 To partials
     aa(i) = 0
     bb(i) = 0
   Next


c)
What does the procedure should return, as it can only return one value each call...



Does someone have an own or know a very fast and very small FFT *.lib? Credits will be given! Thanks!