Numerit: The Fourier Transform

Demos

Output Document of fft.num

Code

The Fourier Transform
A signal h(t) in the time domain may be represented by its spectrum H(f ) in the frequency domain. The function H(f ) (which is generally a complex function) gives the amplitude and phase of the spectral components of the signal. The relations between h(t) and H(f ) are given by:

and are called the Fourier transform equations.
In many situations the signal h(t) is sampled at evenly spaced intervals. There is an equivalent transform for sampled signals called the discrete Fourier transform which describes the relations between a sampled signal with a finite number of points in the time domain and a sampled spectrum with a finite number of points in the frequency domain. This transform is given by:

where N is the number of sampled points.
The fast Fourier transform (FFT) suggested by J.W. Cooley and J.W. Tukey in the mid-1960s is the best known algorithm for computing the discrete Fourier transform. While the number of operations in a straightforward summation is of the order of N ², the number of operations in the FFT algorithm is of the order of N log₂N, which for a large number of points yields a huge difference in computation time.
The following graphs present a signal and its spectrum as computed by the function ffts. This function computes the discrete Fourier transform and also shifts the result so that the zero frequency component appears at the center (the FFT algorithm returns the transform with the zero frequency component as the first element in the array; the function fft returns the transform without a shift).


Figure 1. Input Signal: a sine wave	Figure 2. Absolute value of transform

Figure 1 shows the input signal. This is a sine wave whose frequency is given by the parameter k. We have added a constant term to the sine (the dc parameter) so that the signal will also have a zero frequency component. Figure 2 shows the absolute value of the transform. As we can see, there is a central peak representing the zero frequency, and two peaks representing the frequency of the sine, at +k and -k.
You may change the value of k in the program from 5 to 10 (or to any other value) and re-run the program to see how the transform changes. Note what happens when the frequency becomes too high (>=16).
When the frequency is greater than some critical value (the Nyquist frequency) the signal is under-sampled and the transform is no longer accurate. See E.O. Brigham's book "The Fast Fourier Transform" for details.

In the following graphs we see a more complex signal - a sum of the first signal with a sine wave of frequency k+3 and a smaller amplitude.


Figure 3. Input Signal: a sum of two sines	Figure 4. Absolute value of transform

Figure 3 shows the signal and Figure 4 shows the absolute value of its transform. We can see the added frequencies with the smaller weight.

The following graphs show a sine wave, which is modulated by a decaying exponent, and the absolute value of its transform:


Figure 5. A modulated sine	Figure 6. Absolute value of transform

As we can see, the decaying exponent adds many more frequency components to the signal.
Change the value of the decay coefficient a, re-run the program, and watch the effect it has on the transform.

Demos

Code