# Fast Fourier Transform (FFT)

The functions in the Frequency Domain subclass are based on the discrete implementation and optimization of the Fourier Transform integral. The functions obtain the Discrete Fourier Transform (DFT) of a complex sequence X that contains n elements using the following formula:

for i = 0, 1, . . ., n – 1

where Yi is the element of the DFT of X and

The DFT of X also results in a complex sequence Y of n elements. Similarly, the functions obtain the Inverse Discrete Fourier Transform (IDFT) of a complex sequence Y that contains n elements using the following formula:

for i = 0, 1, . . ., n – 1

where Xi is the element of the IDFT of Y and

The discrete implementation of the DFT is a numerically intense process. However, it is possible to implement a fast algorithm when the size of the sequence is a power of two. These algorithms are known as FFTs and can be found in many introductory texts about digital signal processing (DSP).

The current algorithm implemented in the LabWindows/CVI Advanced Analysis Library is known as the split-radix algorithm. This algorithm is highly efficient because it minimizes the number of multiplications and has the form of the Radix-4 algorithm and the efficiency of the Radix-8 algorithm. The resulting complex FFT sequence has the conventional DSP format as described in the following paragraphs.

If there are n elements in the complex sequence and Yk = Xk θ Wk, the output of the FFT is organized as follows:

Y0 DC component

Y1 Positive first harmonic

Yk – 1 Positive second harmonic

.

.

.

Y2 Positive k – 1 harmonic

Yk Nyquist frequency

Yk + 1 Negative k – 1 harmonic

.

.

.

Yn – 2 Negative second harmonic

Yn – 1 Negative first harmonic

The following conventions and restrictions apply to the functions in the Frequency Domain subclass.

- Arrays for FHT and InvFHT must be a power of two: n = 2m, for m = 1, 2, 3, . . ., 12.
- The functions manipulate complex sequences using two arrays. One array contains the real elements. The other array contains the imaginary elements.

This help uses the following notation to describe the FFT operations the functions in the Frequency Domain subclass perform.

- Y = FFT(X), the sequence Y is the FFT of the sequence X.
- Y = FFT-1(X), the sequence Y is the inverse FFT of the sequence X.

X is usually a complex array but can be treated as a real array.