HTML5header
blackline

The intuitively obvious is the most difficult to learn, precisely because it is not taught.

Joesph Fourier is credited with the discovery that any arbitrary periodic function is the sum of many simple waves: equation
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).
blackline

To compute the DFT we first need to determine the value for a0

Since cosine(0) = 1 and sine(0) = 0, a0 is just a constant.
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) )
In javascript that would be:
   for ( i = 0; i < T; i++ )
   {
       a0 += f(i);
    }
   a0 = a0 / T;
blackline

Next we need to determine the coefficients for ai and bi.

The first half cycle of the sine wave is positive and the second negative. The question is, what could we multiply the sine by which has the first half cycle positive and the second half negative which would create two positive half cycles (this is the "intuitively obvious" part). As is shown in figure 3, it is a sine wave of the same frequency.
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.
In javascript that would be:
   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;
   }
blackline

Finally we can generate the power spectra.

The power spectra is computed from the coefficients of each term and displayed as the frequency domain of the result.
In javascript that would be:
   for( i = 0; i <= T/2;i++)
   {
       p[i] = Math.sqrt( a[i] * a[i] + b[i] * b[i] );
   }
blackline

HANN WINDOW

The Hann window is just one of the digital signal processing techniques available to modify the raw data, tapering it to zero at the end points, to achieve clearer results.
In javascript that would be:
   for (i = 0; i < T; i++)
    {
       j = 0.5 * ( 1 - Math.cos( 2 * Math.PI * i / ( T-1) ) );
       f[i] = j * f[i];
   }
blackline

Other Results.

Start Frequency End Frequency
Hann Window
blackline

A REAL OUT OF THIS WORLD EXAMPLE

Figure 8 is a sample of data from the Kepler project. The graph shows the brightness of a star in our galaxy over time. Like most real world data it has noise, gaps in the data, long term trends and the occasional unexplained error. If it did NOT have these problems you should suspect that it is NOT real world data.
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.
1. We visually ignore the long term trend by just following it.
       ----IGNORE - Trends
2. We mentally ignore the upper bright data points (we are looking for dimming !)
       ----IGNORE - Positives
5. We ignore small short term variability ( noise).
       ----IGNORE - Noise
3. We ignore gaps and just pass over them.
4. We ignore precise intervals of time between dimming and just see if it is a "regular" pattern.
blackline

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" .
blackline