# 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 N^{2}=1,048,576 operations, whereas the FFT would require about Nlog_{2}N = 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)

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

(2)

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

(3)