FFT的类型有哪些区别？

Question

我想澄清一下FFT的不同实现之间的区别。我读到有1D FFT、2D FFT和其他类型的FFT。

请问这些之间有何差异（例如输入、输出等）？例如，什么样的FFT使用 arr[n*2] = 实数 和 arr[n*2+1] = 虚数 作为输入？

此外，对于某些FFT算法，Complex[]的用途是什么？我注意到它们在FFT算法中使用了X和Y。哪个是实部？哪个是虚部？

谢谢！

- user488792

Answer 1

正弦和余弦函数相差90度，由于频率数据可以具有任何相位，因此完整的FFT结果必须报告正弦和余弦分量。通过将这2个分量描述为1个复数相量，可以“简化”FFT的数学。这些复数可以用2维量（称一个维度为I，另一个维度为Q，或X和Y，或U和V等）表示。一些FFT例程交错这2个分量（余弦和正弦，或实数和虚数），而一些则将它们保留在单独的数组或向量中。

由于FFT具有几乎相同的反演计算，这意味着输入数据也可以是复杂的，这可能有用，也可能没有用。如果您的数据没有第二个或“虚数”分量，则可以使用零来馈送FFT，或者使用稍微修改过的FFT算法，该算法修剪了所有隐式零的乘积。仅包含实数据的FFT的结果将具有一些冗余对称性，因此该结果也可能被修剪。

- hotpaw2

Answer 2

FFT可以有任意数量的维度，但1D FFT通常用于本质上是一维的数据，例如音频，2D FFT用于2D数据，如图像。

在一般情况下，输入数据和输出数据都是复数，即每个输入/输出值中都有实部和虚部。然而，对于大多数“现实世界”即物理数据，输入数据的虚部将为零。FFT的输出，即使对于纯实数输入数据，也将具有实部和虚部。

根据FFT实现的不同，输入/输出数据可能只是交错数组，其中实部位于2 * i处，虚部位于索引2 * i + 1处，或者它们可能使用某些复杂的数据类型，有时实部和虚部可能在单独的数组中。这只是API细节，底层算法仍然是相同的。

- Paul R

Answer 3

2D FFT 简单来说就是先对数组的每一行进行 1D FFT，然后再对每一列进行 1D FFT。

- nibot