Essentially, this is just equating the function f(x) to the sum of a series of sines and cosines with different amplitudes and frequencies.

Figure 1 is a sample square wave with a period (T) of 480 points.

There are 240 possible frequencies to represent this square wave.

With a finite sequence of data this is called the discrete Fourier transform (DFT).

Figure 2 shows the area enclosed by a simple sine wave. The sine terms add nothing to the area under the function f(x) since the positive half cycle cancels the negative half cycle. This is also true for the cosine terms.

The area under f(x) is just the sum of the values ( ∑ f(x) ) over the period (T) of the function.

The area under a0, the constant, is just a0 * T .

That gives us:

∑ f(x) = a0 * T

therefore:

a0 = ∑ f(x) / T (which is the average value of f(x) )

for ( i = 0; i < T; i++ )

{

a0 += f(i);

}

a0 = a0 / T;

So we have

f(x) * sine = bi * T/2; or

bi = 2 * f(x) * sine /T;

Similarly for the cosine term:

f(x) * cosine = ai * T/2; or

ai = 2 * f(x) * cosine /T.

for( i = 1; i <= T / 2; i++)

{

for(t = 0; t <= T-1;t++)

{

a[i] += f[t] * Math.cos( i * t * 2 * Math.PI / T);

b[i] += f[t] * Math.sin( i * t * 2 * Math.PI / T);

}

a[i] = 2 * a[i] / T;

b[i] = 2 * b[i] / T;

}

for( i = 0; i <= T/2;i++)

{

p[i] = Math.sqrt( a[i] * a[i] + b[i] * b[i] );

}

for (i = 0; i < T; i++)

{

j = 0.5 * ( 1 - Math.cos( 2 * Math.PI * i / ( T-1) ) );

f[i] = j * f[i];

}

In this graph we are trying to determine if there is a regularly repeating dimming of the star which would indicate a body passing in front of the star (actually we are hoping to find the footprint of a planet).

It is obvious at a mere glance that there is a regularly repeating reduction of the brightness of this star occurring with an interval of a little less than a day. So we conclude that this may be a planet orbiting the star and wait for it to be verified by other means.

Mathematics can help analyze this data but you have to admire the amazing ability of the eye and brain to do it's own digital signal processing.

We simply IGNORE things.

## THE FAST FOURIER TRANSFORM ( FFT )

The FFT (fast Fourier transform) is a method for computing the DFT extremely fast given some constraints on the range of the data (the period must be a power of 2.). For example your data must consists of 512, 1024, 2048, etc points. The technique takes advantage of the symmetrical properties of the DFT to reduce the calculations significantly. Many books have been written on this computation method and one of the best I have read is E. Oran Brigham's "FAST FOURIER TRANSFORM AND IT'S APPLICATIONS" .