Introduction

Fourier transform is a method for expressing a function as a weighted sum of sinusoids. Fourier transforms are computed on a time domain signal to check its components in the frequency domain. Fourier transform has vast applications including signal, noise, image, and audio processing.

When both the function and its Fourier transform are replaced with their discretized counterparts, it is called the discrete Fourier transform (DFT). The fftpack module in SciPy helps the user compute the DFT using the algorithm Fast Fourier Transform (FFT).

The FFT $y[k]$ (length $N$) of sequence $x[n]$ (length $N$) is defined as:

...