Differences in FFT Types?

Question

I just want to clarify the difference between some of the "FFT implementations." Ive read that there is a 1D FFT, and then there are 2D FFT and others.

Can I find out what are the differences between them (for example, entry, exit, etc.). For example, what FFT measurement uses the input arr [n * 2] = real and arr [n * 2 + 1] = imaginary?

In addition, what is the use of the complex [] for some FFT algorithms? I noticed that they use X and Y during the FFT algorithm. What is real and imaginary?

Thanks!

Answer 1

The sine and cosine functions have a phase difference of 90 degrees, and since these frequencies can have any phase, the full FFT result should report both sinusoidal and cosine components. The FFT math can be “simplified” by describing these 2 components as one complex phasor. And these complex numbers can be represented by a two-dimensional quantity (we call one dimension I and the other Q, or X and Y, or U and V, etc.). Some FFT routines alternate 2 components (cosine and sine, or real and imaginary), some store them in separate arrays or vectors.

Since the FFT has an inverse, which is pretty much identical to the calculation, this means that the input can also be complex, which may be useful or may not be useful. You can either feed FFTs with zeros if your data does not have a second or “imaginary” component, or use a slightly modified FFT algorithm that reduces all multiplications by implicit zeros. The result of the FFT with real data will have some excess symmetry, so the result can also be shortened.

Answer 2

FFT can have any number of measurements, but 1D FFT is usually used for data that is essentially one-dimensional, for example. Audio and 2D FFTs are used for 2D data such as images.

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

Depending on the implementation of the FFT, the input / output data can be simply alternating arrays where the real components are in 2 * i and the imaginary components are at the index 2 * i + 1 or they can use some complex data type, or sometimes real and imaginary components can be in separate arrays. This is just an API part, but the basic algorithm is still the same.

Answer 3

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