F.2.1 [Numerical Algorithms and Problems]: Computation of transforms, algorithms, theory, Fast Fourier transform, Pascal algorithms
This tutorial discusses the fast Fourier transform, which has numerous applications in signal and image processing. The FFT computes the frequency components of a signal that has been sampled at n points in O( n log n) time. We explain the FFT and illustrate it by examples and Pascal algorithms. We assume that you are familiar with elementary calculus.
Hansen, Per Brinch, "The Fast Fourier Transform" (1991). Electrical Engineering and Computer Science - Technical Reports. 130.