what is fast fourier transform?

Question

in simple terms with regards to digital signal processing

Answer 1

A fourier transform takes a mathematical function that describes a signal and transforms it into a mathematical function that describes the signal's frequency components. Typically, the input is a time signal, however, it can also be used in other domains, such as spacially, a common use of the fourier transform in graphics or physics.

A discrete fourier transform (DFT) is a fourier transform on a discrete signal (a signal consisting of a sequence of samples taken at regular intervals). Discrete signals introduce additional constraints, the main one being a limit on the highest frequency component of the sampled signal (Nyquist frequency, see sources).

A fast fourier transform (FFT) is an efficient algorithm for calculating a DFT.

Answer 2

Give that first guy best answer, but the basic idea of a Fourier Transform is to decompose a signal into its component frequencies. For example, you might hear a chord coming from a piano, and if you took a waveform of it in time, it would be a wiggly mess. But after applying a Fourier transform to it, you would see a graph of the relative strength of various frequencies present. For example, that graph might have peaks around the notes C, E, and G. Actually, since the piano notes are not pure sine waves, you would see other frequencies present, too, at varying strengths. You can digitally compute a Discrete Fourier transform on a computer, but it took a long time at first, because of all the calculations involved. Then someone found out that you can save the intermediate computations and re-use them, saving a tremendous amount of time. If you have data to analyze, don't bother trying to write your own Fast Fourier Transform. There are already free packages available to do it for you. You pass the array of time-domain data (the waveform), and it returns an array of frequency-domain data.

Answer 3

The fast Fourier transform (FFT) is a factorisation of the discrete Fourier transform, which allows the transform to be calculated in fewer mathematical operations, typically of the order of N*logN operations rather than N*N for the discrete transform, where N is the number of points and logs are base 2. A typical value for N might be 1024 points so the FFT reduces the number of operations from about a million operations to about 10,000, a speed-up factor of 100.

Answer 4

The Fourier transform mathematically expresses a signal in terms of its frequency components (usually time frequency, but sometimes spatial frequency is of interest). Its direct calculation on large arrays of data is very laborious. In the days when computing power was more limited than it is today, and time on big computers was expensive, a great advance was made when J.W. Tukey and John Cooley found a way of calculating it which greatly reduced the number of calculations for large arrays, and hence reduced the computing time. This became known as the fast Fourier transform.
Amongst other applications, it was used to process data from radio telescopes that used aperture synthesis to form high-resolution images.
The mathematics of it is not easily explained, you'd have to refer to the original paper or specialist textbooks.

Answer 5

A Fast Fourier Transform (FFT) is an efficient algorithm to compute the discrete Fourier transform (DFT) and its inverse. FFTs are of great importance to a wide variety of applications, from digital signal processing to solving partial differential equations to algorithms for quickly multiplying large integers. This article describes the algorithms, of which there are many; see discrete Fourier transform for properties and applications of the transform.
http://en.wikipedia.org/wiki/Fast_Fourier_transform

Answer 6

Ther are no simple terms to explain the FFT. You need a lot of math to understand it,