I’m feeling bored, so I’ll add a quick tutorial as I understand it. The real question is how much Reuben needs to know.
The really short version is that any function f(t) that is periodic can be broken down into a sum of sines and cosines:
f(t) = A+Acos(tw)+Acos(2tw)+Acos(3tw)+…+Bsin(tw)+Bsin(2tw)+Bsin(3tw)+…
where w=(2*PI)/T, T being the period of the whole signal. The terms with the higher constant factors inside the parentheses correspond to higher frequencies.
This formula looks freaker than it is, and life is complicated by the fact that you often see this in form:
f(t) = e^(- i w t) + e^(-2 i w t) + e^(-3 i w t) + …
because of the relationship between complex exponentials and the trig functions. For computer programming, though, the explicit cosine and sine formula is easier to swallow.
We assume that any periodic function you have, even if its just data in an array, can be represented in the above form (proof not forthcoming). So take it as read that the function f that represents the data you have, is in the above form.
What you’re really trying to solve for when doing a Fourier transform is to find the amplitudes A[k] and B[k] for all relevant k. If you know those amplitudes, then you know all of the ‘component signals’ that go into making up f(t).
That’s all in continuous math, of course, but there’s a discrete variation where your time t is in discrete quantities.
Let’s assume that you take out the constant component A so that f(t) is periodic around 0. (Simplifies the discussion). If you integrate under this curve, you end up with 0, because the curve is as much (area wise) under y=0 as above it, by the nature of being periodic. Note that you only need to integrate across one full period T of the signal, since it just repeats.
It turns out that if you multiply f(t) by cos(tw), and then integrate under the signal curve, you end up cancelling out most of f(t)'s terms. In fact, the only term that survives is the Acos(tw) term. The other terms in the formula f(t)cos(tw), when integrated, go to zero.
Integrating f(t)cos(wt)dt gives you the result A/2 (this can be shown with some basic trig calculus).
But A is precisely the amplitude of the first cosine term.
Similarly, if you multiply f(t) by cos(2wt), and then integrate that function, the only term that survives is the cos(2wt) term. So Integrating f(t)cos(2wt)dt gives you the result A/2.
But A is precisely the amplitude of the second cosine term.
It turns out that you can get all of the amplitudes in this manner, by multiplying the function by the appropriate trig function, and then integrating.
In the discrete world, you have two things going for you.
You have a finite number of samples over some period of time, and this means there is a highest frequency (a highest factor k inside the cos/sin terms) that you ever need to handle, meaning a finite number of sine and cosine terms. There are N pairs of terms for N samples. There’s a relationship between a sample number s and a time t by t=T*s/N for total time period T.
Integration of any function f where the samples are of a fixed ‘width’ is simply the sum of the sample values each multiplied by the width of a sample (in this case, the amplitude of a sample multiplied by the time slice of that sample). Alternately, sum up the samples, and divide by the number of samples (average). In math terms, this adds up the areas of the rectangles described by each sample, which is a discrete integration.
This lends itself fairly simply to computing a Discrete Fourier Transform, where you typically have your signal in an array f[s] where s is the sample number. First, find A, the constant term, by integrating over the whole signal. Take A away from f[s]. This centers f[s] around 0. A is the “DC component”, the constant offset in the periodic signal.
Then, find each other A[k] and B[k] individually. You do this by computing the discrete approximation of the integration of f(t)*cos(kwt) for A[k], and f(t)*sin(kwt) for B[k]. You can do this by generating a new array g[s]=f[s]*cos(wt) and then integrating g[s], although you can also do it without the need of an additional array (since all you’re really after is, in the end, a single number, being the ‘area under the curve’).
That’s all there is to it, for a basic Fourier transform, enabling you to get those amplitudes.
Those websites give lots more information, including how to produce a spectrum out of samples (typically meaning a Power Spectral Density).
Uh, I can probably explain bits of this if I got too mathematical, or shut up entirely if you already knew all this. I suspect some math guru’ll be around to correct me on gaping holes.
There is a Fast Fourier Transform family of operations to make the Discrete Fourier Transform computation faster, but it doesn’t improve understanding of the concepts.
So it comes down to: Integrating f(t)*h(kwt) where h is either sine or cosine results in all except one of the terms going to zero, and the resulting value being half the amplitude of term k.