# FFT Analysis

The Fast Fourier Transform (FFT) transforms “time-domain” data into the “frequency-domain”. That is, the FFT “takes apart” a single data waveform into many sine and cosine waves.

### Fast Fourier Transform (FFT)

The FFT transforms “time-domain” data into the “frequency-domain”. That is, the FFT “takes apart” a single data waveform into many sine and cosine waves. This is useful for revealing oscillations (harmonics) that may be hidden in the original time data. Note that your ear can act as a simple FFT — such as when you might hear a “60 Hertz buzz” from an electrical circuit in music from a home stereo system. When using the FFT and examining the resulting “frequency domain”, we might say some data has a “large 1000 Hz component” if there is a “spike” at 1000 Hertz.

The FFT is actually a computational algorithm that very efficiently implements a mathematical operation called the Discrete Time Fourier Transform (DTFT). As in the previous description, the DTFT transforms “time-domain” data into the “frequency-domain”. Said more precisely, the DTFT “projects” a length N time data sequence onto sinusoids at N different frequencies. Note that the FFT performs the exact same mathematical operation as the DTFT, howbeit in a very computationally efficient manner.

### Fourier Analysis Methods

The operation that “takes apart” data using projections is the Fourier Transform operator. 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 as in ϕ(ω) = e-iωt = cos(ωt) + i sin(ωt)

### Three Common Fourier operators

Fourier Transform (FT)

X(ω) = ∫t∈ℝ x(t) e-iωt dt (maps from continuous to continuous)

Discrete Time Fourier Transform (DTFT)

X(ω) = ∑n∈ℤ x(n) e-iωn (maps from discrete to continuous)

Discrete Fourier Transform (DFT)

X(k) = ∑n=0…N-1 x(n) e-i2πkn/N (maps from discrete to discrete)