CoursesCertificatesBack to VR.com

MENU

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.

Example

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).

Fourier Operators

There are several Fourier operators, including:

  • Fourier Transform (FT): maps from continuous to continuous

(1)   \begin{equation*} \text{X}(\omega)=\int\nolimit_{t\in\mathbb{R}}x(t)e^{-i\omega t}dt \end{equation*}

  • Discrete Time Fourier Transform (DTFT): maps from discrete to continuous

(2)   \begin{equation*} \text{X}(\omega)=\sum\nolimits_{n\in\mathbb{Z}}x(n)e^{-i\omega n} \end{equation*}

  • Discrete Fourier Transform (DFT): maps from discrete to discrete

(3)   \begin{equation*} \text{X}(k)=\sum\nolimits_{n=0…N-1}x(n)e^{-i2\pi kn/N} \end{equation*}