 Fast Fourier transform

A fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT).Fourier analysis converts a signal from its original domain (often time or space) to a representation in the frequency domain and vice versa.