Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
This is more related to programming I guess. Now what is the question? errors in your code? or if your code is correct? –  Seyhmus Güngören Sep 5 '12 at 19:49
    
I wanted to know if it is the correct behavior, or if I have any errors. –  Ivan Kuckir Sep 5 '12 at 19:56
    
The behavior that you are seeing is correct. It is called Gibbs Phenomenon (see 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. sinusoids). –  Tpofofn Sep 6 '12 at 2:31

1 Answer 1

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];

share|improve this answer
    
Thakn you very much! I thought that it is expected, but I was not sure. BTW. I added another link to my question, can you tell me something about it? –  Ivan Kuckir Sep 5 '12 at 20:04
    
@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$. –  Arkamis Sep 5 '12 at 20:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.