# FFT Fundamentals

Directly implementing the Discrete Fourier Transform (DFT) on N data samples requires approximately N2 complex operations and is a time-consuming process. The Fast Fourier Transform (FFT) is a fast algorithm for calculating the DFT. The following equation defines the DFT.

The following measurements comprise the basic functions for FFT-based signal analysis:

- FFT
- Power spectrum
- Cross power spectrum

You can use the basic functions as the building blocks for creating additional measurement functions, such as the frequency response, impulse response, coherence, amplitude spectrum, and phase spectrum.

The FFT and the power spectrum are useful for measuring the frequency content of stationary or transient signals. The FFT produces the average frequency content of a signal over the total acquisition. Therefore, use the FFT for stationary signal analysis or in cases where you need only the average energy at each frequency line.

An FFT is equivalent to a set of parallel filters of bandwidth Δf centered at each frequency increment from DC to (Fs/2) – (Fs/N). Therefore, frequency lines also are known as frequency bins or FFT bins.

## Computing Frequency Components

Each frequency component is the result of a dot product of the time-domain signal with the complex exponential at that frequency and is given by the following equation.

The DC component is the dot product of x(n) with [cos(0) – jsin(0)], or with 1.0.

The first bin, or frequency component, is the dot product of x(n) with cos(2πn/N) – jsin(2πn/N). Here, cos(2πn/N) is a single cycle of the cosine wave, and sin(2πn/N) is a single cycle of a sine wave.

In general, bin k is the dot product of x(n) with k cycles of the cosine wave for the real part of X(k) and the sine wave for the imaginary part of X(k).

The use of the FFT for frequency analysis implies two important relationships.

The first relationship links the highest frequency that can be analyzed to the sampling frequency and is given by the following equation.

Fmax = fs/2 | (A)

where Fmax is the highest frequency that can be analyzed and fs is the sampling frequency.

The second relationship links the frequency resolution to the total acquisition time, which is related to the sampling frequency and the block size of the FFT and is given by the following equation.

Δf = 1/T = fs/N | (B)

where Δf is the frequency resolution, T is the acquisition time, fs is the sampling frequency, and N is the block size of the FFT.

## Fast FFT Sizes

When the size of the input sequence is a power of two, N = 2m, you can implement the computation of the DFT with approximately Nlog2(N) operations, which makes the calculation of the DFT much faster. DSP literature refers to the algorithms for faster DFT calculation as Fast Fourier Transforms (FFTs). Common input sequence sizes that are a power of two include 512, 1,024, and 2,048.

When the size of the input sequence is not a power of two but is factorable as the product of small prime numbers, the FFT-based functions use a mixed radix Cooley-Tukey algorithm to efficiently compute the DFT of the input sequence. For example, Equation C defines an input sequence size N as the product of small prime numbers.

N = 2m3k5j | (C)

for m, k, j = 0, 1, 2, 3, …

For the input sequence size defined by Equation C, the FFT-based functions can compute the DFT with speeds comparable to an FFT whose input sequence size is a power of two. Common input sequence sizes that are factorable as the product of small prime numbers include 480, 640, 1,000, and 2,000.

## Zero Padding

Zero padding is a technique typically employed to make the size of the input sequence equal to a power of two. In zero padding, you add zeros to the end of the input sequence so that the total number of samples is equal to the next higher power of two. For example, if you have 10 samples of a signal, you can add six zeros to make the total number of samples equal to 16, or 24, which is a power of two. The following figure illustrates padding 10 samples of a signal with zeros to make the total number of samples equal 16.

The addition of zeros to the end of the time-domain waveform does not improve the underlying frequency resolution associated with the time-domain signal. The only way to improve the frequency resolution of the time-domain signal is to increase the acquisition time and acquire longer time records.

In addition to making the total number of samples a power of two so that faster computation is made possible by using the FFT, zero padding can lead to an interpolated FFT result, which can produce a higher display resolution.

## FFT Functions

You can use the LabWindows/CVI functions to compute the real FFT, complex FFT, 2D real FFT, and 2D complex FFT.

The real instances compute the FFT of a real-valued signal, whereas the complex instances compute the FFT of a complex-valued signal. However, the outputs of all instances are complex.

Most real-world signals are real valued. Therefore, you can use the real FFT function for most applications. You also can use the complex FFT function by setting the imaginary part of the signal to zero. An example of an application where you use the complex FFT function is when the signal consists of both a real and an imaginary component. A signal consisting of a real and an imaginary component occurs frequently in the field of telecommunications, where you modulate a waveform by a complex exponential. The process of modulation by a complex exponential results in a complex signal, as shown in the following figure: