Fourier Analysis (FFT)
June 2, 2021
Back to: Fundamentals of Signal Processing
The fast Fourier transform (FFT) transforms time-domain data into the frequency domain. It takes apart a single data waveform into many sine and cosine waves. This operation helps to reveal oscillations hidden in the original time data.
The FFT is a computational algorithm that efficiently implements a mathematical operation called the discrete-time Fourier transform (DTFT).
The DTFT transforms time-domain data into the frequency domain. More specifically, it projects a time data sequence of N length onto sinusoids at N frequencies. The FFT performs the same mathematical operation as the DTFT in a computationally efficient manner.
For example, suppose a data sequence has a length N=1,024. A DTFT operation would require about N2=1,048,576 operations, whereas the FFT would require about Nlog2N = 10,240 operations (about one-tenth as many).
However, this efficiency has a constraint—the FFT requires the length N to be a power of 2. As such, all analysis line values are a power of 2.
FFT & Fourier Analysis
The FFT is one of several Fourier analysis methods. In turn, Fourier analysis is one of many analysis methods that take apart time-domain data x(t). These components are typically projections of the data onto a set of basis functions.
For Fourier analysis, the Fourier transform operator takes apart data using projections. The resulting set of components is the Fourier transform of x(t).
A Fourier transform basis function is any function ϕ(ω)=e-iωt, where ω can be any real number (any element in ℝ).
By Euler’s identity, each basis function ϕ(ω) has a real and an imaginary sinusoidal part: ϕ(ω) = e-iωt = cos(ωt) + i sin(ωt).
There are several Fourier operators, including:
- Fourier Transform (FT): maps from continuous to continuous
- Discrete Time Fourier Transform (DTFT): maps from discrete to continuous
- Discrete Fourier Transform (DFT): maps from discrete to discrete
- Bracewell, Ronald N., The Fourier Transform and Its Applications, 2nd ed. McGraw-Hill, 1978.
- Greenhoe, Daniel J., Wavelet Structure and Design. Self-published, 2018.