The Fast Fourier Transform (FFT) is an efficient O(NlogN)
algorithm for calculating DFTs
The FFT exploits symmetries
in the
Inside Collection (Course): ECE 454 and ECE 554 Supplemental reading
Summary: This module describes the fast Fourier Transform (FFT).
The Fast Fourier Transform (FFT) is an efficient O(NlogN)
algorithm for calculating DFTs
The FFT exploits symmetries
in the
To derive the FFT, we assume that the signal's duration is a
power of two:
Each term in square brackets has the form of a
Now for the fun. Because
Length8 DFT decomposition  


Doing an example will make computational savings more obvious. Let's look at the details of a length8 DFT. As shown on Figure 1, we first decompose the DFT into two length4 DFTs, with the outputs added and subtracted together in pairs. Considering Figure 1 as the frequency index goes from 0 through 7, we recycle values from the length4 DFTs into the final calculation because of the periodicity of the DFT output. Examining how pairs of outputs are collected together, we create the basic computational element known as a butterfly (Figure 2).
Butterfly 

By considering together the computations involving common output
frequencies from the two halflength DFTs, we see that the two
complex multiplies are related to each other, and we can reduce
our computational work even further. By further decomposing the
length4 DFTs into two length2 DFTs and combining their
outputs, we arrive at the diagram summarizing the length8 fast
Fourier transform (Figure 1).
Although most of the complex multiplies are quite simple
(multiplying by
Note that the ordering of the input sequence in the two parts of Figure 1 aren't quite the same. Why not? How is the ordering determined?
The upper panel has not used the FFT algorithm to compute the length4 DFTs while the lower one has. The ordering is determined by the algorithm.
We now have a way of computing the spectrum for an
arbitrary signal: The Discrete Fourier Transform (DFT)
computes the spectrum at
For example, consider the formula for the discrete Fourier
transform. For each frequency we chose, we must multiply each
signal value by a complex number and add together the
results. For a realvalued signal, each realtimescomplex
multiplication requires two real multiplications, meaning we
have
In complexity calculations, we only worry about what happens as
the data lengths increase, and take the dominant
term—here the
In making the complexity evaluation for
the DFT, we assumed the data to be real. Three questions
emerge. First of all, the spectra of such signals have
conjugate symmetry, meaning that negative frequency components
(
Secondly, suppose the data are complexvalued; what is the DFT's complexity now?
Finally, a less important but interesting
question is suppose we want
When the signal is realvalued, we may only need
half the spectral values, but the complexity remains
unchanged. If the data are complexvalued, which demands
retaining all frequency values, the complexity is again the
same. When only
How much better is O(NlogN) than O(








100 










Say you have a 1 MFLOP machine (a million "floating point"
operations per second). Let
An O(
An O(
3 megapixel digital camera spits out
taking FFTs  O(NlogN)
multiplying FFTs  O(N)
inverse FFTs  O(NlogN).
the total complexity is O(NlogN).
Other "fast" algorithms have been discovered, most of which make use
of how many common factors the transform length N has. In
number theory, the number of prime factors a given integer has
measures how composite it is. The numbers 16 and
81 are highly composite (equaling
"My introduction to signal processing course at Rice University."