40.6  Fast Fourier Transforms

A “fast Fourier transform” (often shortened to “FFT”) is not a new type of transform, it is just a faster way of computing either of the discrete transforms we’ve been discussing. To be more precise, a fast Fourier transform is an implementation (usually on a computer!) of a particularly efficient algorithm for computing a discrete Fourier transform. With the development of these algorithms, it became practical to program computers to calculate and manipulate, in a reasonable amount of time, discrete Fourier transforms of extremely large samplings.

To achieve their efficiency, fast Fourier transforms take advantage of certain relations between various components of the discrete transforms. We will describe that ...

Get Principles of Fourier Analysis, 2nd Edition now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.