# Fast Fourier Transform

Fast Fourier Transform (FFT) is an algorithm to simplify the calculation of the Discrete Fourier Transform (DFT). In the traditional method, the calculation of the DFT is complicated and costs much memory of the computer. In the digital signal processing area, the superposition principle is important to deal with the problem and FFT use this principle well. FFT decompose the original DFT series into much smaller length DFT which can combine to original DFT after calculation. After decomposing, these smaller length DFTs may be calculated by using the direct methods or further decomposed into even smaller length DFTs. It can help the calculation of the DFT faster and easier. There are two basic classes of the FFT algorithms. One is decimation-in-time FFT and another is decimation-in-frequency FFT. In the following part, the basic principle of these two type FFTs will be discussed.

The principle of Decimation-in-time FFT is easy to understand. The basic operation is to divide the N-point DFT series into odd-numbered and even-numbered points series. After calculation, they can be easily recovered to original DFT by re-interleaving the two sequences. Using an example to illustrate this process can be understood easily. The mathematic equation does not present in this article, but the flow graph of 8-point DFT using the butterfly computation will be shown.  That figure shows the process of FFT. The decimation-in-time FFT algorithm was divided the input sequence into a smaller sequence. Further, the output sequence also can be divided into small subsequence.  The difference between these two methods is which part is divided into the smaller sequence.