/sci/ - Science & Math

[Anonymous No.5402207]

Hi, I'm not a retard when it comes to math but to... pages I would consider "poorly explained" I do become a retard. Fortunately, this only happens on what I consider "high level formulas". I'm looking at Fast Fourier Transform right now (pic is the formula).

What the fuck do I do with the following:

xn
i
k
n
N

I am simply trying to figure it out so I can calculate the FFT in a computer program, but if I do not understand how to implement the formula, I cannot create the program. The wikipedia page says nothing about the values I'd like to know how to use.

How do I get xn? I am wildly guessing that xn would be the same number as some Xk value, but how do I achieve that if n and k appear to have the same values?
What is i? If it is an imaginary number, how do I implement that in a computer program? Value of 1?
What is k? Why not call it n since it seems to be the same counter value?
What is n? Why not call it k since it seems to be the same counter value?
How do I decide N? Is it up to me to decide what number it is?

Thanks in advance, /sci/.

[Anonymous No.5402222]

Ooh, never mind about n and k. I see that k is the "outer loop" where I'd calculate the result of the formula for each k up to whatever N value I decide (assuming that I do decide N...). I also see that n is the "inner loop" where I'd calculate every result for the sigma sum thingy thing by incrementing n by 1 all the way up to N-1. However, I still remain baffled about xn, i, and how to decide N.

[Anonymous No.5402234]

xn is the sequence of elements you want to calculate the fast fourier transform of.
N is the number of elements of that sequence.
i is indeed the imaginary unit.
n is just an index used in the sum.
Xk is the kth number in your transformed sequence (you transform xn to Xn with the FFT)

If you have Matlab the fast fourier transform is already implemented in it with the function fft

[Anonymous No.5402276]

>>5402234

Thanks for the post.

>xn is the sequence of elements you want to calculate the fast fourier transform of.

That clears up a lot of things. How do I decide the sequence of elements to be used for FFT? I do see the following on the wikipedia article:

>Let x0, ...., xN-1 be complex numbers

So hmm... does this mean I just randomly generate a fuckton of complex numbers and use that as my sequence, no questions asked? That seems a bit weird so I would like confirmation on that.

>(you transform xn to Xn with the FFT)

This throws me off a little. I thought Xk would work exactly as this: for each k, I calculate the formula and the result is applied to Xk. Because k starts at 0 and goes all the way up to N-1, I will have a list of N-1 results of the FFT formula. But the whole xn to Xn thing throws me off. Does this mean xn inside the formula will equal Xk as long as n = k? In this case, why even bother calculating the rest of the numbers to be added up together for the sigma sum because we'll find xn first. I start rambling here so I apologize if I seem confused here.

[Anonymous No.5402288]

>>5402234

Also, thanks for the tip about Matlab. I can check my results there to make sure my program is working.

[Anonymous No.5402294]

>>5402276
Well what it is you think you are doing when you are calculating a fourier transform? In the continuous case you calculate the fourier transform of a function. Here, in the discrete case, you calculate the discrete fourier transform of a sequence. The sequence is whatever you want it to be, just like in the continuous case the input function is whatever you want it to be. Your input here is N numbers x0, x1, ..., xN-1, your output is N numbers X0, X1, ..., XN-1. You calculate X0, X1, ..., XN-1 with the formula in your pic

[Anonymous No.5402304]

>>5402294

I get it now. Thanks for the posts, mate. Much appreciated!