Terminology » FPGA-DSP » FFT: Understanding the Fast Fourier Transform

FFT: Understanding the Fast Fourier Transform

fft

dft

signal processing

algorithm

frequency domain

This page provides an overview of FFT, which stands for Fast Fourier Transform, and its relation to DFT, the Discrete Fourier Transform. Essentially, FFT is a highly efficient algorithm for calculating the DFT.

There are multiple ways to compute the DFT, and FFT is one such method. The FFT algorithm relies on a decomposition approach. This involves breaking down an N-point signal until each signal represents a single point in the time domain.

These N time-domain points are then transformed into a frequency domain signal spectrum. As mentioned, the Fast Fourier Transform is a DFT algorithm that significantly reduces the computational effort.

Instead of requiring 2N² calculations for N points, FFT brings it down to approximately 2N*log(N). This converts a sampled complex-valued function of time into a sampled complex-valued function of frequency much faster.

A DFT can be efficiently computed using an FFT if the number of points (N) is a power of two. This principle is based on the Danielson-Lanczos lemma, which further suggests that a transform can be applied to sets of points that correspond to the prime factors of N, although this might slightly decrease speed.

The DFT of length N (where N is even) can be expressed as the sum of two DFTs, each with a length of N/2. One is created from the even-numbered points, and the other from the odd-numbered points. If we denote the kth point of the DFT as F_n, the equation is:

FFT equation

How FFT Works: Divide and Conquer

The foundation of the FFT algorithm is a divide-and-conquer strategy. The original N-point sample is divided into two N/2 sequences. This division continues until sequences contain only two sample points.

The DFT of these smaller sequences are calculated, and their results are then combined to produce the final FFT outcome.