08-08-2012, 03:35 PM
Computing the DFT
Computing the DFT.pdf (Size: 262.66 KB / Downloads: 145)
The FFT
!Algorithms for computing the DFT which
are more computationally efficient than the
direct method (better than proportional to
N2) are called Fast Fourier Transforms.
!Generally, we use FFT to refer to
algorithms which work by breaking the
DFT of a long sequence into smaller and
smaller chunks.
Resulting Improvement
Basic Underlying Idea:
Use 2 half-size DFTs instead of 1 full-size DFT.
!Continuing the idea: We could split the half-size
DFTs in half again, and keep splitting the pieces in
half until the number of points left in each block is
down to 2. (Then we just do those directly.)
Side note: We could just as easily split into 3 pieces
instead of 2 the math works out to break a DFT
into any set of equal-size pieces.
In-place computation
Each stage of the FFT process has N inputs and N
outputs, so we need exactly N storage locations at
any one point in the calculations.
!It is possible to re-use the same storage locations at
each stage to reduce memory overhead.
"Any algorithm which uses the same memory to store
successive iterations of a calculation is called an
in-place algorithm.
"Computation must be done in a specific order.