Introduction - If you have any usage issues, please Google them yourself
FFT is not a new transformation, it is the discrete Fourier transform (DFT) of a fast algorithm. Since we have a complex multiplication when calculating DFT Xuyong four real multiplications and real additions secondary a complex quadratic addition Zexu real addition. Each operator of a X (k) requires 4N times complex multiplication and 2N+2 (N-1) = 2 (2N-1) times the real number addition. Therefore, the DFT computation requires 4N ^ 2 times in total real multiplications and N* 2 (2N-1) = 2N (2N-1) times the real number addition. Thus, when calculating the number of multiplications and additions and are proportional to N ^ 2, when N is large, the computation is considerable and, therefore, need to improve on the DFT algorithm to reduce computational speed.