Finite Fourier Series

In equations (3.63-3.65) we are assuming that F(t) is a continuous function of t. Equations (3.64) and (3.65) dictate that to calculate the kth constants, and in the Fourier series (eq. (3.63)), we substitute F(t) into the previous equations and integrate. In experiments with digitized data, the signal we actually work with is an equally spaced discrete set of points, , measured at the set of times (Fig. 3.25).

  
Figure 3.25: Digitized time series.

Therefore, we need to develop a discrete analog to the Fourier series, the finite Fourier series .

Let us consider an even number of points per period, 2N. Then the 2N sample points are measured at

or more succinctly,

 

The finite Fourier series for a function sampled at is

 

where

 

and

 

In the above formulas, we assumed that the function is sampled at 2N points, that the value at the point 2N +1 is L, and that the endpoints 0 and L satisfy the periodic boundary condition,

If the latter assumption does not hold, the convention is to average the values at the endpoints so that the value at F(0) is taken to be

In this case the formulas for the coefficients are

 

and

 

Equations (3.68 and 3.69) can be viewed as a transform or mapping. That is, given a set of numbers , these relations generate two new sets of numbers, A(k) and B(k). It is easy to program this transform. The code to calculate the discrete Fourier transform of involves a double loop (see eqs. (3.68 and 3.69)): the inner loop cycles through the index k, and the outer loop covers the index p. Each loop has order N steps, so the total number of computations is of order . The discrete Fourier transform is, therefore, quite slow for large N (say N ;SPMgt; 500) (see Appendix D for programs to calculate discrete Fourier transforms). Fortunately, there exists an alternative method for calculating the Fourier transform called the fast Fourier transform  or FFT . The FFT is an computation, which is much faster than the discrete Fourier for large data sets. A detailed explanation of the FFT along with C code examples is found in Numerical Recipes [28].