Differences in types of FFT?

I just want to clarify on the difference between certain 'implementat开发者_运维技巧ions 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!

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.

The FFT can have any number of dimensions, but 1D FFTs are commonly used for data that is inherently one dimensional, e.g. audio, and 2D FFTs are used for 2D data such as images.

In the general case both the input data and output data are complex, i.e. there are real and imaginary components in each input/output value. However for most "real world", i.e. physical, data the imaginary part of the input data will be zero. The output of the FFT though, even for purely real input data, will have both real and imaginary components.

Depending on the FFT implementation, the input/output data may just be interleaved arrays, where the real components are at 2*i and the imaginary components are at index 2*i+1, or they may use some complex data type, or sometimes the real and imaginary components may be in separate arrays. This is just an API detail though, the underlying algorithm is still the same.

The 2D FFT is simply the 1D FFT applied first to each row and then to each column of an array.