The Discrete Fourier Transform

To compute the frequency spectrum of a signal, I have created a component which performs the Discrete Fourier Transform (DFT) of a dataset. The DFT is the discrete form (i.e. for sampled data) of the continuous Fourier transform. However, there are important differences between the continuous and the discrete cases. Please see the transform page for a more detailed comparison between the two Fourier transforms, and between the Laplace and Z transforms.

The formula I am using to compute the DFT is the following:

F(W) = a sum( x(t) exp( -i W t ) )

where:

```   F(W)          == the value of the DFT for a specific W.
W             == usually 0 to Pi for a real function (can be -Pi to Pi for a general complex function).
x(t)          == the input dataset (t = 0 to N-1).
exp(-i W t)   == a point on the unit circle of the complex plane.
a             == optional scale factor (often some power of Pi, or 1/N, etc...).
```
I will not attempt to describe the DFT or its uses here. Please see just about any text on signal processing for an explanation of this transform. Note that I am not performing the Fast Fourier Transform (FFT). Although the FFT may be faster to compute, it is not as general a transform as the DFT, and is often implemented as a "black box" which cannot be inspected or modified by the user. While I may create an FFT component eventually (I have several different versions of FFT code, which is part of the problem with that transform), at present the DFT is more versatile, and is quite fast enough for my purposes.

Here is an image of data acquisition and the DFT of a 10 Hz sine signal. The samping rate is 256/sec, sampled for 1 sec epochs. The DFT has 256 points, with W from 0 to Pi. The scale factor is 1. The DFT is shown both in real/imaginary, and in magnitude/phase plots. The last coefficient of the DFT (far right) corresponds to the Nyquist frequency of 128 Hz for this sampling rate:

(Click for larger image)

Here is a chart of sine signals and their spectra for 1-200 Hz:

(Click for larger image)

Note that the Nyquist limit for this sampling rate is 128 Hz. Thus, as the frequency of the signal is ramped from 1-128 Hz, the peak of the spectrum moves from left to right. As the frequency of the signal exceeds 128 Hz, however, the spectrum peak moves back into the plot from right to left. This phenomenon is known as "aliasing", and it is explained in just about any book on signal processing, or you may see the transform page for an explanation. Note that unless the input signal is band-limited by the external electronics to frequencies below 128 Hz, those frequencies above 128 Hz will masquerade as lower-frequency components and will corrupt the rest of the spectrum.

Also note that while the visual appearance of the signal deteriorates well below the Nyquist limit, in theory it still contains the correct and necessary information to produce an accurate spectrum (or an interpolated waveform at higher resolution). Finally, note that a signal well above the Nyquist limit (e.g. 200 Hz) may visually appear to be a valid signal, while in fact it is almost completely an artifact of the DAQ system.

Without getting into a long discussion, I do want to emphasize that the phase information of the spectrum is important. While the phase may (at first) seem to show little time correlation within the spectrum of a single signal, it often does show considerable spacial correlation between multiple signals: