Dan Newcome, blog

I'm bringing cyber back

Simple Fourier transform in Javascript

with 16 comments

I’m gearing up to do some signal processing stuff, and I thought it would be good to brush up a little on some of the mathematical concepts. I’m very familiar with the uses of the various transforms including the Fourier. However, although I’ve used others’ implementations of the FFT algorithm, I’ve never attempted to write my own.  The code shown here is a naive implementation (ie non-FFT – we don’t do the ‘butterfly’ method of successive reduction of the input) of the Fourier transform.  This code is for illustrative purposes — you probably won’t want to use this in any real code, since it will be very slow compared to something that uses the FFT method.  Note that this is probably the simplest code that I’ve seen that does a Fourier transform. If you see anything even simpler than this around on the net, let me know.


function fourier( in_array ) {
 var len = in_array.length;
 var output = new Array();

 for( var k=0; k < len; k++ ) {
   var real = 0;
   var imag = 0;
   for( var n=0; n < len; n++ ) {
     real += in_array[n]*Math.cos(-2*Math.PI*k*n/len);
     imag += in_array[n]*Math.sin(-2*Math.PI*k*n/len);
   }
   output.push( [ real, imag ] )
 }
 return output;
}

Advertisements

Written by newcome

November 4, 2009 at 11:33 am

Posted in Uncategorized

16 Responses

Subscribe to comments with RSS.

  1. […] I found this here. Obviously, this is going to be a lot slower than taking a proper FFT but I’m using it in some code right now because it was so easy to understand and I liked it. It’s working plenty fast. The first comment I got was “How did you make this animation run so fast?” […]

  2. Hello

    Can anybody drop some hints on how to get this working? I have tried testing it on some data (a combination of two sine waves with different frequencies) but I only ever get one “spike” in the output. And this is always in the zeroth element of the array, which suggests something is a bit wrong? My attempt at using the script is below:

    y=[];output=[];

    for(x=0;x<1000;x++)
    {
    y[x]=2*Math.cos(Math.PI*2*x)+Math.cos(Math.PI*4*x);
    }

    //alert(y);
    var len = y.length;
    var output = new Array();
    for( var k=0; k < len; k++ ) {
    var real = 0;
    var imag = 0;
    for( var n=0; n < len; n++ ) {
    real += y[n]*Math.cos(-2*Math.PI*k*n/len);
    imag += y[n]*Math.sin(-2*Math.PI*k*n/len);
    }

    output.push( [ real, imag ] ) }

    alert(output);

    Thank you

    Matt

    Matthew Klein

    July 2, 2011 at 12:10 am

  3. Sorry, forgot to leave my email address: ruby_murray1@hotmail.com

    Cheers

    Matthew Klein

    July 2, 2011 at 12:12 am

  4. @matt – Double check your input array. I ran your code and I ended up with an array filled with the value ‘3’. It looks like your sin/cos functions are always taking integer multiples of 2pi, which will always evaluate to the same number. In other words, your sampling interval is perfectly chosen to exhibit extreme signal aliasing – the wavelength and the sampling period are the same.

    You’ll want to choose a sampling frequency over your desired sampling interval that is significantly higher than the waveform frequency. Your code had two sine waves in-phase at 2Hz. I’d pick a sampling rate of 1kHz or something like that to get decent resolution.

    Try something like this:

    for(x=0;x&lt;1000;x++) {
        y[x]=Math.cos(2*Math.PI*2*(x/1000))+Math.sin(2*Math.PI*2*(x/1000));
    }
    

    This would give you two 2hz waveforms 90 degrees apart sampled at 1kHz.

    I'd also normalize the absolute values to the range [ -1 .. 1 ]. This is normal in DSP code when dealing with real values of a signal.

    Hopefully this gets you on the right track.

    newcome

    July 3, 2011 at 4:11 pm

  5. Hello , this is Matt (cannot log in via any accounts from work)

    Thanks so much for your reply. This does make a lot of sense.

    I will definitely try out your suggestions tonight , and I will post my findings back here.

    Thank you !

    Matt Klein

    July 4, 2011 at 1:05 am

  6. Just an after-thought to my last post….

    I can see that in the lines:
    real += in_array[n]*Math.cos(-2*Math.PI*k*n/len);
    imag += in_array[n]*Math.sin(-2*Math.PI*k*n/len);

    … you divide by the length of the signal array. This is like a base frequency of 1/len. Should there be a relationship between this “frequency” and the frequency of the signal?

    I don’t remember much from my uni physics days, but you could possibly explain, in laymans terms, what we are doing when we multiply the signal by Math.cos(-2*Math.PI*k*n/len). I can see that the k and n integers both loop over the whole of the signal array – why do we have this nested loop?

    Thanks again

    Matt

    Matt Klein

    July 4, 2011 at 1:32 am

  7. @Matt, the definition of the DFT defines the result for each point in the input as a sum of the input items scaled by a factor taking into account frequency and the proportion that the element represents relative to how many total elements there are. So in order to determine the resultant DFT values we iterate over the input array, each time computing the sum. The inner loop calculates this sum.
    Hope this helps.

    newcome

    July 5, 2011 at 12:50 am

  8. Great, thank you. I really need to revise some of this stuff, but I find the orthogonal functions and integration etc a bit hard going.

    I did implement your earlier reccomendation re. the step size, and I am getting much better results now. Cheers !

    Matt Klein

    July 5, 2011 at 10:48 pm

  9. Great job, it’s perfect and such a simple code.
    – Could you also write a function with complex input data?
    – Could you also write a function for the inverse fourier transform with complex input data?
    That would help soooooo much.
    Thanks a lot in advance

    Harald

    June 27, 2012 at 3:16 am

  10. This is amazingly clear. I know the transform from my physics days, but seeing your code makes it so clear how the frequencies are summed up. I wish someone had shown me this 15 years ago.

    Jer

    March 17, 2013 at 5:24 am

  11. @jer – thanks, I’m glad this helped you. I too wish that I had seen something like this back when I was in school. In a semi-related vein, I saw this article on doing calculus with a really simple lisp function recently: http://funcall.blogspot.sg/2009/03/not-lisp-again.html I think it’s helpful sometimes to see computational implementations of mathematical formulas to make it more obvious how something works in practice.

    newcome

    March 19, 2013 at 12:41 pm

  12. what kind of library do you use?

    Andrej

    April 19, 2016 at 3:54 am

  13. Thanks a lot for this. I think the lecturer probably explained the subject OK, but it takes a few different voices to get it to sink in, and my effort at writing my own javascript was close but no cigar. The part about avoiding the integer multiple of PI was a big help.
    I did this:
    make some values to combine into a complicated signal
    n=2000 //samples
    h=[]; for(i=0;i<10;i++){ h.push(Math.floor(n/2*Math.random())+0.2) }
    h.sort(function(a,b){ return a – b })
    then your code to create the signal and decompose it, but because of the mirroring effect only going up to n/2 in the inner loop.
    & then peak detection..

    peaks=[]; flag=true; count=-1;
    for(i in output){ o=output[i][0]; if(ocount){ flag=true } count=o }
    h and peaks are the same

    what’s so cool is that when looking at a drawing of the output and the signal..
    x=”
    for(i in output){
    x+=’·’
    x+=’-‘+” ;
    x+=’·’
    }
    document.write(x)
    ..it works even though the sampling rate is much too crude to actually draw the signal

    chris

    May 1, 2016 at 12:59 pm

  14. sorry, I put some angle brackets in there..
    for(i in output){
    x+=’ [span style=”position:absolute;left:’+(200+1*Math.abs(output[i][1]))+’;top:’+i/2+'”]· [\/span]’
    x+=’ [span style=”color:red;position:absolute;left:’+(400+Math.abs(output[i][0]))+’;top:’+i/2+'”]-‘+’ [\/span]’
    x+=’ [span style=”position:absolute;left:’+(600+4*signal[i])+’;top:’+i/2+'”]· [\/span]’
    }

    chris

    May 1, 2016 at 1:02 pm

  15. If anyone reading this is still looking for the equally simple version of the inverse Fourier transform, here it is:

    function fourier_inverse(in_array) {
    var len = in_array.length;
    var output = [];

    for (var n = 0; n < len; n++) {
    var out = 0;
    for (var k = 0; k < len; k++) {
    out += in_array[k][0]*Math.cos(-2*Math.PI*k*n/len);
    out += in_array[k][1]*Math.sin(-2*Math.PI*k*n/len);
    }
    out = out/len;
    output.push(out);
    }
    return output;
    }

    Jeremy Dormitzer

    December 14, 2016 at 12:32 am

  16. Boom. Thanks for posting this! I might try adding the JS formatting tags to see if I can get it to show up with indentation.

    newcome

    December 21, 2016 at 12:02 pm


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: