2
$\begingroup$

I am trying to implement Discrete Fourier Transform (by definition, in quadratic time).

I wrote this http://jsfiddle.net/uunsm/12/

My result function really goes through discrete points, but it is too "wavy".

When I inserted a sine wave:

var nums = [0.000, 0.707, 1.000, 0.707, 0.000, -0.707, -1.000, -0.707] 

I was expecting to get a smooth sine, but again, there are too many "waves". Am I doing anything wrong?

BTW. I found this implementation http://home.fuse.net/clymer/graphs/dft.html which is much smoother. Is it still Fourier transform? Where can I find any info about that algorithm?

  • 0
    The behavior that $y$ou are seeing is correc$t$. It is called Gibbs Phenomenon (see http://en.wikipedia.org/wiki/Gibbs_phenomenon). It is a natural artifact of trying to represent a non-continuous function (i.e. step) with a set of continuous functions (i.e. sinusoi$ds$).2012-09-06

1 Answers 1

4

That's the expected behavior. In your first example, where var nums = [2, 2, 2, 2, -2, -2, -2, -2];, you're essentially trying to replicate a square wave with a series of sines and cosines. You cannot do that with so few terms; in fact, you cannot eliminate the waviness, only make it arbitrarily close (and then you have ringing phenomena, etc).

With your example above, you're trying to represent one low-frequency oscillation with a sum of several higher frequency oscillations. Again, you cannot do that perfectly, so you will get some waviness.

If you want a nice smooth wave, your data has to change with the same frequency as your components. Try this and see what happens.

var nums = [2, -2, 2, -2, 2, -2, 2, -2];

  • 0
    @IvanKuckir Yes, this is essentially a Fourier series approximation. However, notice how the coefficients are conditioned by examining the output: every term is zero, except the term that corresponds to $\sin x$. If you view the source of that site, you can see how the coefficients are conditioned to achieve such a condition. The algorithm there is essentially the same as yours, with some additional steps outside the initial loop. Also, notice that code loops over $0 \le i \le n/2$.2012-09-05