22-05-2013, 04:49 PM
Fast Fourier Transform (FFT) (Theory and Implementation)
Fast Fourier.ppt (Size: 922 KB / Downloads: 139)
Performance of the DFT Algorithm
The DFT requires N2 (NxN) complex multiplications:
Each X(k) requires N complex multiplications.
Therefore to evaluate all the values of the DFT ( X(0) to X(N-1) ) N2 multiplications are required.
The DFT also requires (N-1)*N complex additions:
Each X(k) requires N-1 additions.
Therefore to evaluate all the values of the DFT (N-1)*N additions are required.
FFT Implementation
To efficiently implement the FFT algorithm a few observations are made:
Each stage has the same number of butterflies (number of butterflies = N/2, N is number of points).
The number of DFT groups per stage is equal to (N/2stage).
The difference between the upper and lower leg is equal to 2stage-1.
The number of butterflies in the group is equal to 2stage-1.