Differences in types of FFT?

Question

I just want to clarify on the difference between certain 'implementations of FFT'. Ive read that there are 1D FFTs and then there are 2D FFTs and others.

May I know what are the differences regarding these (e.g. input, output, etc.). For example, what dimension FFT uses the input of arr[n*2] = real and arr[n*2+1] = imaginary?

Also, what is the use of the Complex[] for some FFT algorithms? I noticed that they use X and Y during the FFT algorithm. Which is the real and imaginary?

Thanks!

Answer 1

The sine and cosine functions have a 90 degree phase difference, and since frequency data can have any phase, a complete FFT result has to report both sine and cosine components. The math for an FFT can be "simplified" by describing these 2 components as 1 complex phasor. And these complex numbers can be represented by a 2 dimensional quantity (call one dimension I and another Q, or X and Y, or U and V, etc.). Some FFT routines interleave the 2 components (cosine and sine, or real and imaginary), some keep them in separate arrays or vectors.

Since the FFT has an inverse that is pretty much the identical computation, that means the input data can also be complex, which may or may not be useful. You can either feed an FFT with zeros if your data has no 2nd or "imaginary" component, or use a slightly modified FFT algorithm which prunes all the multiplies by implicit zeros. The result of a real-data-only FFT will have some redundant symmetry, so that result might be pruned as well.