Fourier Transform, Fft, Fast Fourier Transform, Algorithms, Mathematics.
observe that: Thus Assuming that T is divisible by 2, we can decompose the DFT into 2 equal parts as follows: The left summation corresponds to even points and right summation corresponds to odd points. Rewriting the above, we get: Let us denote the left and right summations separately as follows: