FFT 类型的差异？
我只是想澄清某些“FFT 实现”之间的区别。我读过有 1D FFT，还有 2D FFT 等等。
我可以知道这些有什么区别（例如输入、输出等）。例如，什么维度的 FFT 使用 arr[n*2] = real 和 arr[n*2+1] = imaginary 的输入？
另外，Complex[] 对于某些 FFT 算法有什么用？我注意到他们在 FFT 算法中使用了 X 和 Y。真实的和想象的哪个？
谢谢！
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!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
正弦和余弦函数具有 90 度相位差，并且由于频率数据可以具有任何相位，因此完整的 FFT 结果必须报告正弦和余弦分量。通过将这 2 个分量描述为 1 个复相量，可以“简化”FFT 的数学运算。而这些复数可以用一个二维量来表示（称一维为I，另一维为Q，或X和Y，或U和V等）。一些 FFT 例程将 2 个分量（余弦和正弦，或实数和虚数）交错，一些将它们保存在单独的数组或向量中。
由于 FFT 具有几乎相同的计算逆运算，这意味着输入数据也可能很复杂，这可能有用也可能没用。如果您的数据没有第二个或“虚数”分量，您可以向 FFT 提供零，或者使用稍微修改的 FFT 算法，该算法通过隐式零修剪所有乘法。仅实数据 FFT 的结果将具有一些冗余对称性，因此该结果也可能被修剪。
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.
FFT 可以具有任意数量的维度，但 1D FFT 通常用于固有一维的数据（例如音频），而 2D FFT 用于 2D 数据（例如图像）。
在一般情况下，输入数据和输出数据都是复数，即每个输入/输出值中都存在实部和虚部。然而，对于大多数“现实世界”，即物理数据，输入数据的虚部将为零。然而，即使对于纯实数输入数据，FFT 的输出也将同时具有实部和虚部。
根据 FFT 实现，输入/输出数据可能只是交错数组，其中实部位于 2*i 处，虚部位于索引 2*i+1 处，或者它们可能使用一些复杂的数据类型，或者有时实部和虚部可能位于不同的数组中。虽然这只是 API 细节，但底层算法仍然相同。
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.
2D FFT 只是首先应用于阵列的每一行，然后应用于每一列的 1D FFT。
The 2D FFT is simply the 1D FFT applied first to each row and then to each column of an array.