An efficient algorithm for computing the DFT of a sequence. Runs in O(n log(n)) time

Carleton College

Approximation of the Fourier Series on a finite interval. Converts the signal from the time domain to the frequency domain

Input: windowed signal $x[n]... x[m]$ 

Output (for each frequency band): a complex number $X[k]$ representing the magnitude and phase of that frequency component in the original signal


We compute $X[k]$ with:


$X[k] = \sum_{n=0}^{N-1} x[n]e^{-j\frac{2\pi}{N}kn} $

Discrete Fourier Transform (DFT)

https://mathworld.wolfram.com/FastFourierTransform.html

Fast Fourier Transform (Wolfram MathWorld)

When we plot the magnitude of each frequency from the DFT, we can visualize the spectrum of the given signal

Plotting a spectrum from DFT

Fast Fourier Transform (FFT)

Spectral information is extracted on a mel scale, rather than equally across all frequency bands. We do this because humans hearing is more sensitive at lower frequencies than higher ones, so modeling speech recognition the same way helps performance.

Learn Before

Related