Comparing Discrete Fourier Transforms and Fast Fourier Transforms

Discrete Fourier Transform (DFT)

The samples of a signal obtained from a DAQ board constitute the time domain representation of the signal. This representation gives the amplitudes of the signal at the instants of time during which it had been sampled. However, in many cases you want to know the frequency content of a signal rather than the amplitudes of the individual samples. The representation of a signal in terms of its individual frequency components is known as the frequency domain representation of the signal. The frequency domain representation could give more insight about the signal and the system from which it was generated.

The algorithm used to transform samples of the data from the time domain into the frequency domain is known as the discrete Fourier transform or DFT. The DFT establishes the relationship between the samples of a signal in the time domain and their representation in the frequency domain. The DFT is widely used in the fields of spectral analysis, applied mechanics, acoustics, medical imaging, numerical analysis, instrumentation, and telecommunications.

Suppose you have obtained N samples of a signal from a DAQ board. If you apply the DFT to N samples of this time domain representation of the signal, the result is also of length N samples, but the information it contains is of the frequency domain representation. The relationship between the N samples in the time domain and the N samples in the frequency domain is explained below.

If the signal is sampled at a sampling rate of Hz, then the time interval between the samples, that is, the sampling interval, is t, where

The sample signals are denoted by x[i], 0 i N–1, that is, you have a total of N samples. When the discrete Fourier transform, given by

for k = 0, 1, 2, …, N-1

is applied to these N samples, the resulting output (X[k],0k N-1) is the frequency domain representation of x[i]. Notice that both the time domain x and the frequency domain X have a total of N samples. Analogous to the time spacing of t between the samples of x in the time domain, you have a frequency spacing of

between the components of X in the frequency domain. f is also known as the frequency resolution. To increase the frequency resolution (smaller f) you must either increase the number of samples N, with constant, or decrease the sampling frequency , with N constant.

Fast Fourier Transform (FFT)

Direct implementation of the DFT on N data samples requires approximately complex operations and is a time-consuming process. However, when the size of the sequence is a power of 2,

,

you can implement the computation of the DFT with approximately N log2(N) operations. This makes the calculation of the DFT much faster, and DSP literature refers to these algorithms as fast Fourier transforms (FFTs). The FFT is nothing but a fast algorithm for calculating the DFT when the number of samples (N) is a power of 2.

The advantages of the FFT include speed and memory efficiency, because the VI can compute the FFT in place, that is, no additional memory buffers are needed to compute the output. The size of the input sequence, however, must be a power of 2. The DFT can efficiently process any size sequence, but the DFT is slower than the FFT and uses more memory, because it must allocate additional buffers for storing intermediate results during processing.

Refer to DFT Calculation or Magnitude and Phase Information for more information about fast Fourier transforms.